题解 | #[NOIP1999]回文数#
[NOIP1999]回文数
https://www.nowcoder.com/practice/a432eb24b3534c27bdd1377869886ebb
/* 思路就是把字符 转换为该字符的数字 直接保存在数组中 然后除(进制数)和模(进制数) 得到的数字再按(进制数) 进位 后转换为字符 判断是否为回文 刚开始用这个思路写的时候 出现大量问题 比如想着一劳永逸直接用strlen() 求出长度 直接传值 后来发现再加减进位 的时候 长度也可能发生变化 导致运算错乱 可以把strlen() 直接放在循环体内 再传值 可以解决该问题 但刚开始已经忘记了 把所有形参删除并加上了strlen() 还有关于进位的问题 两个数相加不论这个两个数有多大 每次进位只可能进1 10进制下的 9 + 9 余 8 进 1 16进制下的 F + F 余 E 进 1 */ #include <stdio.h> #include <string.h> //转换为字符所需要加的基数 #define BASE(num) ((num) >= 10?'A' - 10:'0') //把第一个数组拷贝到第二个数组 翻转第二个数组 void Reversal(char* num, char* ch) { int left = 0; int right =strlen(num) - 1 ; strcpy(ch, num); while (left < right) { char tmp = ch[left]; ch[left] = ch[right]; ch[right] = tmp; left++; right--; } } //判断是否为回文数 int Palindrome(char* num) { int left = 0; int right = strlen(num) - 1;; while (left < right) { if (num[left++] != num[right--]) return 0; } return 1; } //把数字从字符转换为base进制的数字 void transform(char* num, int base) { if (base <= 10) { while (*num != '\0') { *num++ -= '0'; } } else { while (*num != '\0') { if (*num >= '0' && *num <= '9') { *num++ -= '0'; } else { *num++ = *num - 'A' + 10; } } } } //进位 把相加后的数 按base进制 进位 void Push(char* num, int base, int sz) { int i = sz; while (sz >= 0) { char tmp = 0; tmp = num[sz] / base; num[sz] = (num[sz] % base) + BASE(num[sz] % base); if (sz - 1 < 0 && tmp != 0) { while (i >= 0) { num[i + 1] = num[i]; i--; } num[0] = tmp + '0'; break; } sz--; num[sz] += tmp; } } //两个数字相加 void Add(char* add1, char* add2, int base) { int sz = strlen(add1) - 1; int i = strlen(add1) - 1; transform(add1, base); transform(add2, base); while (i >= 0) { add1[i] = add1[i] + add2[i]; i--; } Push(add1, base, sz); } int main() { int n = 16; int step = 0; char m[100] = { 0 }; char ch[100] = { 0 }; scanf("%d %s", &n, m); int sz = strlen(m) - 1; do { Reversal(m, ch); Add(m, ch, n); step++; } while (Palindrome(m) != 1 && step <= 30); if(step > 30) { printf("Impossible!"); }else { printf("STEP=%d", step); } return 0; }