本节继续上节内容：高精度数据处理。本节主题是回文数。
一、判断方法
什么是回文数：一个数字从左往右读与从右往左读是一样的，那么这个数就是回文数。例如：121，6226，3333、12121等。简单的判断回文数的方式有很多，第一种：字符串存储，逆置判断是否相等；第二种，求取数位，折半循环，每次将最左面与最右面的数值进行比较，如果有一次不等，那这就不是回文数。
代码如下：
将数字转化为字符串(利用现成的函数)，然后将逆置字符串与原字符串进行比较
//转成字符串
bool isHWS(int n){string st = to_string(n);string str=st;//将正序数据存下reverse(st.begin(),st.end());//逆序if(str==st)return true;//如果逆序后还与逆序前相等，就返回truereturn false;
}将数字的每一位放在数组中维护，后期设置左右指针(两个变量，表示相对位置)向中间逼近判断
//两边往中间夹判断
bool isHWS(int n){vector<int> v;while(n!=0){v.push_back(n%10);//取末尾存储n/10;//取掉的数位丢弃}int length=v.size();//代表数有多少位int i=0,j=length-1;for(;i<=j;i++,j--){if(v[i]!=v[j])return false;}return true;
}二、主讲内容
题目要求
本节题目： 信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
【题目描述】：
若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个 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” 。
【输入】：
第1行，给定一个N（2＜N≤10或N=16）表示进制；
第2行，一个N进制数M。
【输出】：
最少几步。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible”。
题目分析
进制：C语言的操作符-CSDN博客 （在这里，我曾经讲过进制的知识，大家可以回去看一下）。
这里，我们最多可以包含30步回文数化的操作，随着次数的增多，得到的数字对的位数也越多，如果只使用int和long long类型的数据恐怕有些不妥，而且为了培训大家对高精度数据的处理方法，本节要求使用数组维护数位进行解答（貌似用整型家族的数据类型存储都不能保证全部测试用例通过，没试过）。
来吧，正式编码来了，让我们进行编码四部曲
第一步：搭建主函数
将必要的变量维护在全局区，真的真的特别的方便。为了不让我们在一个数组内进行各种操作，我们建立一个镜像数组,用来代表数字逆置后，数字的数位情况。由于题意要求最多30步，我们定义一个变量记录步数。
我们的逻辑就是：初始化数据，按照题目要求输入数据，并根据合适的方法进行处理，放入合适的变量进行维护。然后进行循环，每次循环走一步回文化操作，操作结束我们需要判断当前数字是否是回文数字，如果是就输出当前的 步数，然后结束循环就ok了。如果外层循环30次还不是回文数，按照题意输出不可能就行了。
#include <bits/stdc++.h>
using namespace std;const long long limit = 1e9;
int X;//X代表进制数 2~10 / 16
int M_numbers[limit];//X进制数m
int Mirroring[limit];//镜像
int length;//当前数字位数-长度
int step_cnt;//记录步数int main() {init();while (step_cnt < 30) {step();//进行一次回文化操作if (isEnd()) {//如果成了，结束cout << step_cnt << endl;return 0;}}cout << "Impossible" << endl;return 0;
}第二步：初始化数据
之后我就把思路逻辑写到代码中了，方便大家对照理解。
void init() {cin >> X;//输入进制数string m; cin >> m;//先用字符串存下数字length = m.size();//计算初始长度for (int i = 0; i < length; i++) {//循环放入数位数组//考虑到题目中有说明，进制数可能是16进制//16进制的特点就是：0123456789ABCDEF代表0-15，也就是会存在字符代表数字的情况//为此需要进行条件判断if ('0' <= m[i] && m[i] <= '9')Mirroring[i + 1] = m[i] - '0';//如果是数字，那么就将将数字字符放入数组else Mirroring[i + 1] = m[i] - 'A' + 10;//如果是A，则‘A’-‘A’+10=10；如果是B，则‘B’-‘A’+10=11//悟了嘛M_numbers[length - i] = Mirroring[i + 1];//将镜像数组的存的数字倒着放到原数组中}
}第三步：判断回文数
为什么我们不先写核心过程，而是先写如何判断回文数。因为简单，哈哈，不管中间怎么变，我们前面的工作做完之后，就已经确定了判断的条件与方式了。
我们本题为了维护数位和逆置数位多建立了一个镜像数组，只要判断这两个数组元素是否相等就可以了。其实循环条件终止可以写成i<=length/2+1(+1是为了保险起见),如果中间遇到不相等的，返回false代表不是回文数，不结束。循环截止都没有返回说明各个位置都满足条件了，那么我就可以返回true，告诉主函数可以结束了。
bool isEnd() {//如果是回文数，true，结束for (int i = 1; i <= length; i++) {if (M_numbers[i] != Mirroring[i])return false;//不回文了已经}return true;
}第四步：写核心步骤
每次我们都要从第一位个位开始加起，初始时没有进位信息，设置为0即可，当前位置的数字也设为0，在循环内部进行更新即可。
当前位置应该留下的数字number=两个数各位相加后对进制X取余的结果
当前位置下一位的进位数Output=两个数各位相加后对进制数X相除的结果
将进位加到下一位中，进行过操作的数位信息在原数组中进行修改，依次进行。
完毕之后看看最高位的数字top是否还能进位，如果不能不要管，如果能，需要额外加一位有效空间存储数位。
然后将镜像数组进行更新。最后步骤走一步+1。
void step() {int cur_idx = 1;//从第一位开始加int Output = 0;//当前位进位信息int number = 0;//当前位取余数据while (cur_idx <= length) {number = (M_numbers[cur_idx] + Mirroring[cur_idx]) % X;//余位=(a+b+进位数)%XOutput = (M_numbers[cur_idx] + Mirroring[cur_idx]) / X;//进位数=(a+b)/进制数M_numbers[cur_idx + 1] += Output;M_numbers[cur_idx] = number;++cur_idx;//下一位}if (M_numbers[cur_idx] > 0)length++;//更新镜像数组：for (int i = 1; i <= length; i++) {Mirroring[i] = M_numbers[length + 1 - i];}++step_cnt;//步数加一
}
三、参考答案
#include <bits/stdc++.h>
using namespace std;
#define Long long longint X;//X代表进制数 2~10 / 16
int M_numbers[35];//X进制数m
int Mirroring[35];//镜像
int length;//当前数字位数-长度
int step_cnt;//记录步数void init() {cin >> X;string m; cin >> m;length = m.size();for (int i = 0; i < length; i++) {if ('0' <= m[i] && m[i] <= '9')Mirroring[i + 1] = m[i] - '0';else Mirroring[i + 1] = m[i] - 'A' + 10;M_numbers[length - i] = Mirroring[i + 1];}
}
void step() {int cur_idx = 1;//从第一位开始加int Output = 0;//当前位进位信息int number = 0;//当前位取余数据while (cur_idx <= length) {number = (M_numbers[cur_idx] + Mirroring[cur_idx]) % X;//余位=(a+b+进位数)%XOutput = (M_numbers[cur_idx] + Mirroring[cur_idx]) / X;//进位数=(a+b)/进制数M_numbers[cur_idx + 1] += Output;M_numbers[cur_idx] = number;++cur_idx;//下一位}if (M_numbers[cur_idx] > 0)length++;//更新镜像数组：for (int i = 1; i <= length; i++) {Mirroring[i] = M_numbers[length + 1 - i];}++step_cnt;//步数加一
}bool isEnd() {//如果是回文数，true，结束for (int i = 1; i <= length; i++) {if (M_numbers[i] != Mirroring[i])return false;//不回文了已经}return true;
}int main() {init();while (step_cnt < 30) {step();//进行一次回文化操作if (isEnd()) {//如果成了，结束cout << step_cnt << endl;return 0;}}cout << "Impossible" << endl;return 0;
}
难吗？没有吧。初始化数据不知道吗？也许你只是差一点思路，不知道怎么维护而已，但上节我们讲了，这节也讲了，下次你还不会吗？不能吧。如何判断回文数不会吗？这么简单的对称判断问题而已。核心步骤之所以称之为核心步骤，是因为最后的结果是由这个步骤进行决定的，每一次的数据变化都是有规律可以寻找的，我们习惯了十进制，我们写个X进制的，不管写没写出来，那这就是进步。你比那些只看不动手的人强多了。
