思路
-
问题分析：给定一个 N 进制数 M（字符串形式，最多 100 位），通过不断将其与它的反转数进行 N 进制加法，直到得到回文数。如果在 30 步内得到回文数，输出步数；否则输出 "Impossible!"。
-
关键步骤：
-
判断回文：检查字符串是否从左到右和从右到左读相同。
-
字符串反转：获取当前字符串的反转形式。
-
N 进制加法：模拟加法过程，处理进位和进制转换（注意 16 进制时使用大写字母）。
-
-
算法流程：
-
检查初始数是否回文，若是则输出 0 步。
-
循环最多 30 步：
-
将当前数与其反转进行 N 进制加法。
-
检查结果是否回文，若是则输出当前步数。
-
-
若 30 步内未得到回文数，输出 "Impossible!"。
-
代码
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;
// 字符转数字（支持小写和大写字母）
int charToDigit(char c) {
if (c >= '0' && c <= '9')
return c - '0';
else if (c >= 'A' && c <= 'F')
return c - 'A' + 10;
else if (c >= 'a' && c <= 'f')
return c - 'a' + 10;
else
return -1; // 无效字符
}
// 数字转字符（输出大写字母）
char digitToChar(int num) {
if (num < 10)
return '0' + num;
else
return 'A' + num - 10;
}
// 判断字符串是否为回文
bool isPalindrome(string s) {
int n = s.size();
for (int i = 0; i < n / 2; i++) {
if (s[i] != s[n - 1 - i])
return false;
}
return true;
}
// 反转字符串
string reverseString(string s) {
string t = s;
reverse(t.begin(), t.end());
return t;
}
// N进制加法（两个字符串长度必须相同）
string add(string a, string b, int base) {
int len = a.size();
string result = "";
int carry = 0;
for (int i = len - 1; i >= 0; i--) {
int num1 = charToDigit(a[i]);
int num2 = charToDigit(b[i]);
int sum = num1 + num2 + carry;
carry = sum / base;
int digit = sum % base;
result.push_back(digitToChar(digit));
}
if (carry > 0) {
result.push_back(digitToChar(carry));
}
reverse(result.begin(), result.end());
return result;
}
int main() {
int N;
string M;
cin >> N >> M;
// 检查初始数是否回文
if (isPalindrome(M)) {
cout << "STEP=0" << endl;
return 0;
}
string current = M;
int step = 0;
while (step < 30) {
step++;
string rev = reverseString(current);
current = add(current, rev, N);
if (isPalindrome(current)) {
cout << "STEP=" << step << endl;
return 0;
}
}
cout << "Impossible!" << endl;
return 0;
}