问题描述
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。 又如：对于10进制数87：
STEP1：+ = STEP2：+ =
STEP3：+ = STEP4：+ = 在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N（<=N<=10或N=）进制数M（其中16进制数字为0-9与A-F），求最少经过几步可以得到回文数。
如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”
输入格式
两行，N与M
输出格式
如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是步数；否则输出一行”Impossible!”（不含引号）
样例输入 样例输出
STEP=
记:
高精度计算，使用数组保存数据，防止溢出
AC代码:
#include <stdio.h>
#include <string.h>
#define MAX 10010 int n; /*进制数*/
char m[MAX+]; /*输入数*/
int len = ; /*输入数的长度*/
int use[MAX+] = {}; void init()
{
int i;
scanf("%d",&n);
scanf("%s",&m);
len = strlen(m);
for (i = ; i < len ; i ++)
{
if (m[i]>= && m[i]<=)
{
use[i] = m[i]-;
}
else
{
use[i] = m[i]-+;
}
}
return ;
} void find(int x)
{
int i = , j = len- , k = len/;
int tmp[MAX+] = {};
int carry = ; /*进制位*/ if (x > )
{
printf("Impossible!");
return ;
} /*回文判断*/
while (k)
{
if (use[i] != use[j])
{
break;
}
i ++,j --,k --;
} if (i >= j)
{
printf("STEP=%d",x);
}
else
{
carry = ;
for (i = ; i < len ; i ++)
{
k = use[i]+use[len--i]+carry;
tmp[i] = k%n;
carry = k/n;
}
while (carry)
{
k = carry;
tmp[len] = k%n;
carry = k/n;
len ++;
}
for (i = ; i < len ; i ++)
{
use[i] = tmp[i];
}
find(x+);
}
return ;
} int main(void)
{
init();
find();
return ;
}