算法训练 回文数

问题描述

　　若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个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（其中16进制数字为0-9与A-F），求最少经过几步可以得到回文数。
　　如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”

输入格式

　　两行，N与M

输出格式

　　如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是步数；否则输出一行”Impossible!”（不含引号）

样例输入

9
87

样例输出

STEP=6

思路

　　string字符串模拟，然后反向相加，注意可能在最高位进位，个人感觉这题的坑点应该包含16进制，坑在32-35行，因为字符A的ASCLL码表值是65，而9的ASCLL码表值是57，所以要先A-=7。。。

AC代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cctype>
using namespace std;
string a, b;
int judge()
{
    for (int i = 0; i<a.size() / 2; i++)
    {
        if (a[i] != a[a.size() - i - 1])
            return 0;
    }
    return 1;
}
int main()
{
    int flag, jinwei, i, j, k;
    cin >> flag >> a;
    for (k = 0; k <= 30; k++)
    {
        if (judge())
        {
            cout << "STEP=" << k;
            return 0;
        }
        jinwei = 0;
        b = a;
        reverse(b.begin(), b.end());
        for (i = 0; i<a.size(); i++)
        {
            if (isalpha(a[i]))
                a[i] -= 7;
            if (isalpha(b[i]))
                b[i] -= 7;
            a[i] = a[i] + b[i] + jinwei - '0';
            if (a[i]-'0' >= flag)
            {
                a[i] -= flag;
                jinwei = 1;
            }
            else
                jinwei = 0;
        }
        if (jinwei == 1)
            a = a + "1";
    }
    cout << "Impossible!";
}