回文数题解

说明

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加56（即把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，每组的第一行输入N，第二行输入M。

输出格式

对于每组输入数据，输出最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出"Impossible!"。

样例

9
87

STEP=6

c语言版：

#include <stdio.h>
#include <string.h>#define MAX 5000 // 定义字符数组的最大长度int len, d, lim = 30; // len表示字符串长度，d表示进制，lim表示最多进行30次操作
char str[MAX], rts[MAX]; // str用于存储原始字符串，rts用于存储反转后的字符串// 将字符串b反转，并存入字符串a中
void fz(char a[MAX], char b[MAX]) {// 从b的末尾依次赋值到a的前面，实现反转for (int i = 0; i < len; ++i) {a[i] = b[len - 1 - i];}a[len] = '\0'; // 确保字符串末尾是'\0'结束符
}// 实现字符串str和rts的按进制d的加法，并存入rts
void add() {int carry = 0; // carry用于存储进位for (int i = 0; i < len; ++i) {// 将str和rts对应位相加，并加上进位carryrts[i] += str[i] - '0' + carry;carry = (rts[i] - '0') / d; // 计算进位值rts[i] = (rts[i] - '0') % d + '0'; // 当前位取模，重新变成字符}// 如果有进位，处理进位部分if (carry) {rts[len] = '0' + carry;rts[++len] = '\0'; // 增加新的一位，并确保字符串以'\0'结尾}
}// 判断当前字符串rts是否为回文
int judge() {// 从两端向中间逐位比较字符for (int i = 0; i < len; ++i) {if (rts[i] != rts[len - 1 - i]) {return 0; // 如果存在不相等的字符，返回0表示不是回文}}return 1; // 如果所有字符都相等，返回1表示是回文
}int main() {// 输入进制d和字符串strscanf("%d %s", &d, str);// 将输入字符串中的大写字母转换为相应的数字for (int i = 0; i < strlen(str); ++i) {if ('A' <= str[i] && str[i] <= 'Z') {str[i] = str[i] - 'A' + '9' + 1; // 将'A'-'Z' 转换为 10-35}}// 最多进行lim（30次）的操作，寻找回文数for (int i = 0; i <= lim; ++i) {len = strlen(str); // 获取当前字符串长度fz(rts, str); // 将str反转存入rts中// 判断rts是否为回文，如果是则退出循环if (judge()) {printf("STEP=%d\n", i); // 输出找到回文的步骤数return 0;}// 如果不是回文，则将str和rts相加，并存入rts中add();fz(str, rts); // 将rts反转后重新存入str，进行下一次循环}// 如果超过30次仍然没有找到回文，则输出"Impossible!"printf("Impossible!\n");return 0;
}

解释：

主函数：
- 输入进制 d 和字符串 str。
- 将输入字符串中的大写字母转换为对应的数字（A 转换为 10，B 转换为 11，依次类推）。
- 循环最多进行 lim 次操作，每次检查是否为回文，如果是回文则输出操作步数 STEP=n，如果超过 lim 次仍未找到回文则输出 Impossible!。

C 语言版本的关键点：

C 语言中数组操作需要手动管理字符数组的末尾 \0，这是与 C++ 中 string 的区别之一。
输入与输出使用 scanf 和 printf，比 C++ 更为低级，但更加高效

C++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
#define endl '\n'
const ll MAXN = 2e5+10; // 定义最大数组长度
char letter[20] = "0123456789ABCDEF"; // 进制表示用到的字符表// 将字符转换为数字的函数
int char_to_int(char c) {// 如果是数字字符（0-9），则返回数字本身；如果是字母（A-F），则返回对应的数值return isdigit(c) ? c - '0' : c - 'A' + 10;
}// 将数字转换为字符的函数
char int_to_char(int n) {// 返回数字对应的进制字符return letter[n];
}// 反转字符串并进行两数相加的函数，返回相加后的字符串
string radd(string a, int k) {string b = a; reverse(b.begin(), b.end()); // 将字符串 a 反转，存储到 b 中string ans; // 用于存储最终的结果字符串vector<int> nums(a.length() + 1, 0); // 动态分配数组用于存储每一位的加和结果，并初始化为 0int aL = a.length(); // 获取字符串 a 的长度// 将字符转换为数字并进行对应位置的加法for (int i = 0; i < aL; i++) {int numa = char_to_int(a[i]); // 将 a[i] 转换为相应的数值int numb = char_to_int(b[i]); // 将 b[i] 转换为相应的数值nums[i] += numa + numb; // 对应位的两个数字相加}// 处理进位for (int i = 0; i < aL; i++) {if (nums[i] >= k) { // 如果当前位大于等于进制 k，则需要进位nums[i+1] += nums[i] / k; // 进位给下一位nums[i] %= k; // 当前位保留进制范围内的值}}if (nums[aL]) aL++;  // 如果最后有进位，则需要增加长度// 将结果转换回字符串for (int i = aL - 1; i >= 0; i--) {ans += int_to_char(nums[i]); // 将数字转换为字符并拼接到结果字符串中}return ans; // 返回相加后的字符串
}int main() {ios_base::sync_with_stdio(false); // 提高输入输出效率，关闭 C 风格的同步cin.tie(nullptr); // 取消 cin 和 cout 的绑定，进一步提升性能string M; // 用于存储输入的数字字符串int N, cnt = 1; // N 表示输入的进制，cnt 表示步骤计数，初始化为 1cin >> N >> M; // 输入进制 N 和数字字符串 Mstring temp = radd(M, N), s; // 调用 radd 函数将 M 和它的反转相加，存储到 temp 中s = temp; reverse(s.begin(), s.end()); // 将 temp 反转，存储到 s 中// 循环直到找到回文数或者超过 30 步while (temp != s) { // 当 temp 不是回文时cnt++; // 步骤计数器加 1if (cnt > 30) { // 如果步骤超过 30，则输出 "Impossible!"cout << "Impossible!" << endl;return 0; // 程序结束}temp = radd(temp, N); // 将当前字符串 temp 与它的反转相加s = temp; reverse(s.begin(), s.end()); // 将新的 temp 再次反转}// 如果找到回文数，输出步骤数cout << "STEP=" << cnt << endl;return 0; // 程序结束
}

#include<iostream>
#include<string.h>
using namespace std;const int Max = 5000; // 最大字符数组大小
int len, d, lim = 30; // len表示字符串长度，d表示进制，lim表示最多进行30次操作
char str[Max], rts[Max]; // str是原始字符串，rts是反转后的字符串// 将字符串b反转并存入字符串a中
void fz(char a[Max], char b[Max]) {// 遍历字符串b，将b的字符从末尾依次复制到a的前面，达到反转的效果for (int i = 0; i < len; ++i)a[i] = b[len - 1 - i];
}// 实现str和rts的加法，并存回rts中，按指定进制d进行进位
void add() {int c = 0; // 用于保存进位// 从低位开始将str和rts对应位置的数字相加for (int i = 0; i < len; ++i) {rts[i] += str[i] - '0' + c; // 当前位的相加结果存入rts[i]c = (rts[i] - '0') / d; // 计算进位，当前位的值除以进制drts[i] = (rts[i] - '0') % d + '0'; // 当前位的值取模进制d，并转回字符}// 如果最高位仍然有进位，则将进位存入rts的下一位if (c) rts[len] = '0' + c;
}// 判断当前字符串rts是否为回文
bool judge() {// 从两端开始向中间逐位比较，如果有不相等的字符则返回falsefor (int i = 0; i < len; ++i)if (rts[i] != rts[len - 1 - i]) return false;// 如果所有字符都相等，则返回true，表示是回文return true;
}int main() {// 输入进制d和字符串strcin >> d >> str;// 将输入字符串中的大写字母转换为对应的数字// 比如'A' 转换为 10，'B' 转换为 11，依次类推int i;for (i = 0; i < strlen(str); ++i) {if ('A' <= str[i] && str[i] <= 'Z') str[i] = str[i] - 'A' + '9' + 1; // 大写字母转换为数字字符}// 最多进行lim（即30）次的加法反转判断操作for (i = 0; i <= lim; ++i) {len = strlen(str); // 计算当前字符串长度fz(rts, str); // 将str反转并存入rts// 判断rts是否为回文字符串，如果是则退出循环if (judge() == true) break;add(); // 如果不是回文，则将str和rts相加，并将结果存入rts中len = strlen(rts); // 更新rts的长度// 将rts再反转存入str，继续下一轮循环fz(str, rts);}// 输出结果，如果在30步以内找到回文，则输出步骤数if (i <= lim) cout << "STEP=" << i << endl;// 如果超过30步仍未找到回文，则输出"Impossible!"else cout << "Impossible!" << endl;
}