[高精度計算]OI練習題 ：回文數 huiwen 解題報告

【問題描述】

若一個數（首位不爲0）從左到右讀與從右到左讀都是一樣，這個數就叫做迴文數，例如12512就是一個迴文數。

給定一個N進制正整數，把它的各位數字上數字倒過來排列組成一個新數，然後與原數相加，如果是迴文數則停止，如果不是，則重複這個操作，直到和爲迴文數爲止。例如：10進制87則有：

STEP1: 87+78=165

STEP2: 165+561=726

STEP3: 726+627=1353

STEP4: 1353+3531=4884

任務：寫一個程序，給定一個N（2≤N≤10，N=16）進制數m（10~15用小寫字母a~f表示），m的位數上限爲20。求最少經過幾步可以得到迴文數。如果在30步以內（包括30步）不可能得到迴文數，則輸出“impossible”，否則輸出該迴文數及生成該迴文數的最少步數。

【輸入格式】

文件有兩行，每行一個數，即N和N進制整數m

【輸出格式】

如果輸入文件給定的數據在30步以內（包括30步）不可能得到迴文數，則輸出文件只有一行，即輸出“impossible”。

否則輸出文件爲兩行。第一行是由輸入文件給定數據生成的迴文數，第二行是生成該迴文數的最少步數。

【輸入輸出樣例】

輸入

10

87

輸出

4884

4

【分析】

這題屬於基本練習類題目，需要用到高精度計算。

每次把數組翻過來，進行比對，如果相同則輸出step，否則這個數加上它的“相反數”。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int N;
int T=0;

class hugeint
{
public:
    int len;
    int num[500];
    hugeint()
    {
        len=0;
        memset(num,0,sizeof(num));
    }
};

hugeint ans;
hugeint tmp;

hugeint add()
{
    int i;
    hugeint Ans;
    hugeint a=ans;
    hugeint b=tmp;
   
    if (a.len>b.len)
        Ans.len=a.len;
    else
        Ans.len=b.len;
    for (i=1;i<=Ans.len;i++)
    {
        Ans.num[i]+=(a.num[i]+b.num[i]);
        Ans.num[i+1]+=Ans.num[i]/N;
        Ans.num[i]%=N;
    }
    if (Ans.num[Ans.len+1]>0)
        Ans.len++;
    return Ans;
}

bool check()
{
    memset(tmp.num,0,sizeof(tmp.num));
    tmp.len=ans.len;
    int top=tmp.len;
    for (int i=1;i<=ans.len;i++)
    {
        tmp.num[top]=ans.num[i];
        top--;
    }
   
    for(int i=1;i<=ans.len;i++)
    {
        if(tmp.num[i]!=ans.num[i])
            return false;
        top--;
    }
    return true;
}

void init()
{
    scanf("%d\n",&N);
    string str;
    cin>>str;
   
    ans.len=str.length();
    for (int i=1;i<=ans.len;i++)
    {
        if(str[ans.len-i]>='0' && str[ans.len-i]<='9')
            ans.num[i]=str[ans.len-i]-'0';
        else
            ans.num[i]=str[ans.len-i]-'a'+10;
    }
    return;
}

void works()
{
    while(T<=30)
    {
        if(check())
        {
            for (int i=ans.len;i>=1;i--)
            {
                if(ans.num[i]<=9)
                    cout<<ans.num[i];
                else
                    cout<<char(ans.num[i]-10+'a');
            }
            printf("\n%d\n",T);
            return;
        }
        ans=add();
        T++;
    }
    cout<<"impossible"<<endl;
}

int main()
{
    freopen("huiwen.in","r",stdin);
    freopen("huiwen.out","w",stdout);
    init();
    works();
    return 0;
}