题目描述

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。
又如：对于10进制数87：
STEP1：                  STEP2：
STEP3：           STEP4：
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
写一个程序，给定一个进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”

输入描述:

两行，分别是N，M。

输出描述:

STEP=ans(ans表示答案)

示例1

输入
9
87
输出
STEP=6

解答

对于16进制的处理可以使用-'A'+10而不必一个个判断。这份代码里面使用的是字符串操作，可以不必这样做，应该会方便一些。进位的时候数组resize一下，扩大一位（我扩大了两位）。然后输出的Impossible!的叹号是半角的。 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
string KaitenKapatsu(int n, string ipt0);
bool isKaiten(string ipt);
void solve(int n, string ipt);
int main()
{
    int n;
    string ipt;
    cin >> n >> ipt;
    solve(n, ipt);
    getchar(); getchar();
    return 0;
}
string KaitenKapatsu(int n, string ipt0) {
    for (int i = 0; i < ipt0.size(); i++) {                //读入数据并转为char[]
        if (ipt0[i] > 57)                                //十六进制的处理
            ipt0[i] -= 7;
        ipt0[i] -= '0';
    }
    string ipt = ipt0;
    for (int i = 0; i < ipt0.size(); i++)                //倒序
        ipt[i] = ipt0[ipt0.size() - i - 1];
    string ipt2 = ipt;
    for (int i = 0; i < ipt.size(); i++) {                //倒序相加
        ipt2[i] += ipt0[i];
    }
    ipt2.resize(ipt2.size() + 2);
    for (int i = 0; i < ipt2.size() - 1; i++) {            //进位
        ipt2[i + 1] += ipt2[i] / n;
        ipt2[i] %= n;
    }
    for (int i = 0; i < ipt2.size(); i++) {                //还原为stirng
        if (ipt2[i] >= 10)                                //十六进制的还原
            ipt2[i] += 7;
        ipt2[i] += '0';
    }
    bool judge = 0;
    for (int i = ipt2.size()-1; i >= 0; i--)             //去除前导零
        if (ipt2[i] == '0'&&judge == 0) { ipt2.erase(i, 1); }
        else { judge = 1; }
    ipt.resize(ipt2.size());                            //返回值resize预备输出
    for (int i = 0; i < ipt2.size(); i++)                //倒序
        ipt[i] = ipt2[ipt.size() - 1 - i];
    return ipt;
}
void solve(int n,string ipt){                            //统计步数
    int cnt = 0;
    while (isKaiten(ipt) == 0 && cnt<31) {
        ipt = KaitenKapatsu(n, ipt);
        cnt++;
    }
    if (cnt > 30){cout << "Impossible!";}
    else { cout << "STEP=" << cnt; }
}
bool isKaiten(string ipt) {                                //判断是不是回文
    for (int i = 0; i < ipt.size(); i++) 
        if (ipt[i] != ipt[ipt.size() - i - 1])return 0;
    return 1;
}


来源：Rika