洛谷 P1015 回文数

0
8

题目描述

若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。
例如:给定一个十进制数56,将56加65(即把56从右向左读),得到121是一个回文数。
又如:对于十进制数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(100位之内),求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出Impossible!

输入格式

两行,分别是N,M.

输出格式

STEP=ans

样例输入输出

输入

10
87

输出

STEP=4

思路

① 考虑到题目可能使用16进制输入,因此使用字符数组s存储输入。
② 由于需要进行加法运算,因此将字符数组转换为整型数组;C++的STL(标准模板库)中有reverse()函数可以反转数组,因此使用vector类型来定义转换后的整型数组aInt。
③ 转换过程中,要注意对16进制中的字母作特殊处理:
非字母转换成数字:

if (s[i] >= '0' && s[i] <= '9') { aInt.push_back(s[i] - '0'); }

字母转换成数字:

else if (s[i] >= 'A' && s[i] <= 'Z') { aInt.push_back(s[i] - 'A' + 10); }
else if (s[i] >= 'a' && s[i] <= 'z') { aInt.push_back(s[i] - 'a' + 10); }

④ 接下来将aInt反转得到另一个加数vector bInt。
⑤ 用vector sumInt 来存储 aInt + bInt 的结果,若 sumInt 回文,则输出相加次数;否则将 sumInt 赋值给 aInt,将反转后的 sumInt 赋值给 bInt,再次相加得到新的 sumInt。再次对 sumInt 进行回文判断……重复步骤⑤直到 sumInt 回文,但如果相加次数>30则跳出循环,并输出"Impossible!"。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
 
using namespace std;
 
bool judge(vector<int> a)
{
    vector<int> b = a;
    reverse(b.begin(), b.end());
    return a == b;
}
 
int main()
{
    int sys = 0, r = 0;    //进制, 进位
    string s;
    vector<int> aInt, bInt, sumInt;
    cin >> sys >> s;
    
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9')    aInt.push_back(s[i] - '0');
        else if (s[i] >= 'A' && s[i] <= 'Z') aInt.push_back(s[i] - 'A' + 10);
        else if (s[i] >= 'a' && s[i] <= 'z') aInt.push_back(s[i] - 'a' + 10);
    }
    bInt = aInt;
    sumInt = aInt;
    reverse( bInt.begin(), bInt.end() );
    for (int ans = 0; ans <= 30; ans++) {        
        if (judge(sumInt)) {
            cout << "STEP=" << ans << endl;
            return 0;
        }
        r = 0;
        aInt = sumInt;
        bInt = sumInt;
        reverse(bInt.begin(), bInt.end());
        for (int i = 0; i < aInt.size(); i++) {
            sumInt[i] = (aInt[i] + bInt[i] + r) % sys;
            r = (aInt[i] + bInt[i] + r) / sys;
            if (i == aInt.size() - 1 && r != 0) sumInt.push_back(r);  //最高位进位处理
        }
    }
    cout << "Impossible!" << endl;
    return 0;
}

<

发布回复

请输入评论!
请输入你的名字