试题 算法训练 回文数
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个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（其中16进制数字为0-9与A-F），求最少经过几步可以得到回文数。
如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”
输入格式
两行，N与M
输出格式
如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是步数；否则输出一行”Impossible!”（不含引号）
样例输入
9
87
样例输出
STEP=6
提交代码：
/* 比较坑的地方：在N进制下是否为回文数 */ #include<iostream> #include<cstring> using namespace std; int a[10000],b[10000],s[10001]; bool huiwen(int s[], int l) { int i,k; k = (l - 1)/2; for(i = 0; i <= k; i++){ if(s[i] != s[l - i -1]) break; } if(i == k+1) return 1; else return 0; } void inverse(int s[], int l) { int i; memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); for(i = 0; i < l; i++){ a[i] = s[i]; b[l - i -1] = a[i]; } } int main() { int n,l,i,count = 0; string m; cin>>n>>m; l = m.size(); for(i = 0; i < l; i++){ if(m[i] >= 'A' && m[i] <= 'Z') a[i] = m[i] - 'A' + 10; else a[i] = m[i] - '0'; s[i] = a[i]; b[l - i -1] = a[i]; } while(!huiwen(s, l) && count <= 30){ count++; memset(s, 0, sizeof(s)); for(i = 0; i < l; i++){ s[i] += a[i] + b[i]; s[i+1] += s[i]/n; s[i] = s[i]%n; } if(s[l] != 0) l = l + 1; inverse(s, l); } if(count <= 30) cout<<"STEP="<<count<<endl; else cout<<"Impossible!"<<endl; return 0; }
