若一個數（首位不爲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;
}
#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;
}
