[问题描述]
若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65(即把56从右向左读)，得到121是一个回文数。又如，对于10进制数87，
STEP1: 87+78=165 STEP2: 165+561=726
STEP3: 726+627=1353 STEP4: 1353+3531=4884
在这里的一步是指进行了一次n进制的加法，上例最少用了4步得到回文数4884。
写一个程序，给定一个n(2<n<=10或n=16)进制数m.求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出"Impossible"。
[输入样例] 9 87
[输出样例] 6
[算法分析]
n进制运算
1、当前位规范由改为%n
2、进位处理由/10改为/n
3、其他运算规则不变
[参考程序]
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,a[101],b[101],ans,i; void init(int a[]) {string s; cin>>n>>s; // 输入进制，及需测试的数 a[0]=s.length(); //用a[0]存放字符串s的位数 for(i=1;i<=a[0];i++) if(s[a[0]-i]>='0'&&s[a[0]-i]<='9')a[i]=s[a[0]-i]-'0';//十进制以内的数的转化 else a[i]=s[s[0]-i]-'A'+10;//16进制数的字符转化为整数 } bool check(int a[]) //测试是否是回文数 {for(i=1;i<=a[0];i++) if (a[i]!=a[a[0]-i+1]) return false; return true; } void jia(int a[]) {int i,k; for(i=1;i<=a[0];i++)b[i]=a[a[0]-i+1];//反序数b for(i=1;i<=a[0];i++)a[i]+=b[i]; //逐位相加 for(i=1;i<=a[0];i++) {a[i+1]+=a[i]/n; a[i]%=n; } if(a[a[0]+1]>0)a[0]++;//修正新的a的位数（a+b最多只能进一位） } int main() //主程序先写，把解题思路表现出来，然后细化子程序 {init(a); if(check(a)){cout<<0<<endl;return 0;} ans=0; while(ans<=30) {ans++; jia(a); if(check(a)) {cout<<ans<<endl;return 0; } } cout<<"Imapossible";//输出无解信息 return 0; }
