【例78.3】回文数(Noip1999) 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 64MB，其他语言 128MB 难度：提高 分数：100 OI排行榜得分：18(0.1*分数+2*难度) 出题人： 描述 若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个 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．求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible” 。 输入描述 第1行，给定一个N（2＜N≤10或N=16）表示进制； 第2行，一个N进制数M。 输出描述 最少几步。如果

```cpp #include <iostream> #include <string> #include <algorithm> // 将字符转换为对应的数值 int charToNum(char c) { if (c >= '0' && c <= '9') { return c - '0'; } return c - 'A' + 10; } // 将数值转换为对应的字符 char numToChar(int num) { if (num < 10) { return num + '0'; } return num - 10 + 'A'; } // 实现N进制加法 std::string add(std::string a, std::string b, int n) { std::string result; int carry = 0; int i = a.size() - 1, j = b.size() - 1; while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) { sum += charToNum(a[i]); i--; } if (j >= 0) { sum += charToNum(b[j]); j--; } result.push_back(numToChar(sum % n)); carry = sum / n; } std::reverse(result.begin(), result.end()); return result; } // 判断一个字符串是否是回文串 bool isPalindrome(std::string s) { int left = 0, right = s.size() - 1; while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; } // 反转字符串 std::string reverseStr(std::string s) { std::string reversed = s; std::reverse(reversed.begin(), reversed.end()); return reversed; } int main() { int n; std::string m; std::cin >> n >> m; int steps = 0; while (steps <= 30) { if (isPalindrome(m)) { std::cout << steps << std::endl; return 0; } std::string reversed = reverseStr(m); m = add(m, reversed, n); steps++; } std::cout << "Impossible" << std::endl; return 0; } ``` 代码说明： 1. `charToNum`函数：将字符转换为对应的数值，对于数字字符，直接转换为对应的整数；对于字母字符，转换为对应的十六进制数值。 2. `numToChar`函数：将数值转换为对应的字符，对于小于10的数值，转换为对应的数字字符；对于大于等于10的数值，转换为对应的十六进制字母字符。 3. `add`函数：实现N进制加法，从低位到高位逐位相加，并处理进位。 4. `isPalindrome`函数：判断一个字符串是否是回文串，通过双指针法比较字符串的首尾字符。 5. `reverseStr`函数：反转字符串。 6. `main`函数：读取输入的进制`n`和N进制数`m`，在30步内不断进行加法操作，直到得到回文数或超过30步。如果在30步内得到回文数，输出步数；否则输出`Impossible`。 [2026-02-02 17:44:17 | AI问答 | 811点数解答]