【问题描述】
若一个数（首位不为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题解： 本题略水，本人感觉是简单的模拟，就是按照题目的规则，只不过需要高精度，呵呵，高精加法相信大牛们都敲得很熟了，不多说了，上程序！ 原程：C++语言: made by PaulInsider!
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n,lq,m[100]={0},f[6]={10,11,12,13,14,15};
int ji,answer=1,step=1;
char s[21],fa[6]={'a','b','c','d','e','f'};
bool check();
void jia();
int main()
{
freopen ("huiwen.in","r",stdin);
freopen ("huiwen.out","w",stdout);
cin>>n>>s;
lq=strlen(s);
ji=lq;
for (int p=0;p<lq;p++)
{
if (s[p]-'0'<10)
{
m[p]=s[p]-'0';
}
else
{
m[p]=f[(s[p]-'0')-49];
}
}
while (answer&&step<30)
{
jia();
if (check())
{
answer=0;
}
else
{
step++;
}
}
if (answer==1)
{
cout<<"impossible";
return 0;
}
for (int p=0;p<ji;p++)
{
if (m[p]<10)
{
cout<<m[p];
}
else
{
cout<<fa[m[p]-10];
}
}
cout<<endl<<step;
return 0;
}
void jia()
{
int q[100]={0};
for (int p=0;p<ji;p++)
{
q[ji-p-1]=m[p];
}
for (int i=0;i<ji;i++)
{
m[i]+=q[i];
if (m[i]>=n)
{
m[i+1]++;
m[i]=m[i]%n;
if (i==ji-1)
{
ji++;
}
}
}
}
bool check()
{
int l=0,r;
r=ji-1;
while (l<=r)
{
if (m[l]!=m[r])
{
return false;
}
l++;
r--;
}
return true;
}
神牛飘过，水牛留步！
|