【回文数(二)】 （C++代码）

解题思路:

1.此题用string类存储n进制数m，计算起来较为方便。

2.函数string sum(string str)是用来求数与该数逆序的和(string类型)，定义i=0,j=str.length()-1,str[i]-'0'是int型的值，i从前到后指向str,j从后到前指向str,通过for循环（详见代码）实现该数与它逆序数相加，通过sprintf函数将int型转换为char类型，拼接到string类型a中，由于是从低位到高位相加，所以a的反序串才是相加的和，将a反转过来。k表示有无进位。

3.函数bool f(string str)是用来判断是否是回文数。

4.求一次和，步数加一，判断是否是回文数，是，退出，否，继续求和。步数大于等于30，退出循环。

注意事项:sum函数中要将a反转表示数与逆序数的和。k表示进位，k=1有进位要加

参考代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
string  m;int  n;

//求数与逆序数之和结果存到字符串中

string sum(string str) {
 int temp, k = 0;char c[3];string a;
 for (int i = 0, j = str.length()-1;i < str.length() && j >= 0;i++, j--) {
  temp = (str[i] - '0') + (str[j] - '0');
  if (k == 1) {//k为1要加上进位1
   temp++;k = 0;
  }
  if (temp >= n) {//大于n要进位
   k = 1;temp = temp - n;
  }
  sprintf(c, "%d", temp);//将temp写到字符数组c中
  a = a + c;
 }
 if (k)
  a = a + "1";//如果最高位有进位不要忘记将1写到字符串中
 reverse(a.begin(), a.end());//之前计算的a是逆序的，反转过来
 return a;
}

//判断是否是回文串

bool f(string str) {
 for (int i = 0, j =str.length()-1;i < str.length() && j >= 0;i++, j--) {
  if (str[i] != str[j]) {
   return false;
  }
 }
 return true;
}

//主函数
int main() {
 int step;
 while (cin>>n>>m) {
  if (f(m)) {//判断m是否是回文数
   cout <<"STEP="<< 0 << endl;continue;
  }
  string p;
  p=sum(m);
  step = 1;
  if (f(p)) {
   cout << "STEP=" << step << endl;
   continue;
  }
  while (1) {
      p=sum(p);
   step++;
   if (f(p)) {
    cout <<"STEP="<< step << endl;
    break;
   }
   if (step >= 30) {
    cout << "Impossible" << endl;
    break;
   }
  }
 }
 return 0;
}