[普及-]P1015 回文数

题目链接：https://www.luogu.com.cn/problem/P1015

思路分析

根据题中的意思，运算的过程就是求该数与其位倒置后的数的和，这涉及到了数的位置问题；再者，输入的数据M的位数可能会接近100位，不可能直接用int、long long来直接存放数据，这也涉及到了高精度的问题，所以我们能想到用数组来存放数据的每一位。

用了数组来存放数据后，做加法时已经不能用 “+” 号直接来求和了，考虑到数组的每一格存放着数据的一位数，在做加法时可以分解成将两个数的对应位（对应的数组位）分别做加法，同时考虑进位、取余等等，简单来说原理其实就是小学所学的加法，如图所示：

图中的数据采用的都是十进制，所以是逢十进一、除十取余的，对于N进制数来说，就是逢N进一、除N取余。不管多少进制，算法实现过程原理一模一样。

知道了数组加法后，问题也差不多可以解决了。做了加法后得到了一个新的数，并将其同样也以数组形式表示，判断该数是不是回文数，根据回文数的特征：从左向右和从右向左读来都一样，也就是判断该数是不是一个左右对称的数，即数组左右两边存放的数据是否对应相等。

综上所述，其实就是一个 字符串+大整数相加 的问题。

代码

#include<cstdio>
#include <iostream>
#include<string>
using namespace std;
const int maxn = 1003;
char M[maxn];       //用于存放输入的数
int mid1[maxn];
int mid2[maxn];
int N, step = 0;
int main() {
    void pluss(int m1[], int m2[], int n);
    cin >> N;
    cin >> M;
    if(N!=16)       //对于十六进制的数，某个位置上可能不是数字，而是字母，所以需要单独处理转换为具体的数字。
        for (int i = 0; i < strlen(M); i++) mid1[i] = M[i] - '0';
    else for(int i=0;i<strlen(M);i++){
        if(M[i]>='0'&&M[i]<='9') mid1[i]=M[i]-'0';
        else mid1[i]=M[i]-'A'+10;               //转换字母为具体数字
    }
    int okk = 1;
    for (int i = 0; i < strlen(M) / 2; i++)
        if (mid1[i] != mid1[strlen(M)-1 - i]) {     //判断输入的数是否本身就是回文数
            okk = 0;                            //判断标志
            break;
        }
    if (okk == 1) {
        cout << "STEP=0";
        return 0;
    }
    pluss(mid1, mid2, strlen(M));
    if (step == 30) cout << "Impossible!";
    else cout << "STEP=" << step;
    return 0;
}
/*递归函数，在30步以内，若没有出现回文数，继续进行相同的相加操作。
参数中的 n 表示数的位数的多少，用于控制循环次数*/
void pluss(int m1[], int m2[], int n) {
    step++;
    for (int i = 0; i < n; i++) {
        m2[i + 1] += (m2[i]+m1[i] + m1[n - 1 - i]) / N;
        m2[i] = (m2[i]+m1[i] + m1[n - 1 - i]) % N;
    }
    if (m2[n] != 0) n++;
    int ok = 1;
    for (int i = 0; i < n; i++)
        if (m2[i] != m2[n - 1 - i]) {
            ok = 0;
            break;
        }
    memset(m1, 0,4*n);
    if (!ok && step < 30) {
        pluss(m2, m1,n);
    }
}

因为水平有限，写出来的代码可能有点繁琐，不够简洁，这题肯定还有更为简单的方法，部分内容还可以进一步优化，比如递归的过程，可以不定义递归函数，在主函数中用类似形式的for循环语句就可以解决，可能脑子不太好使，就只能写这种相对易懂的递归了啊。。。毕竟我只是个菜鸡！！！还得多多请教大佬啊！