【題目鏈接】

ybt 1309：【例1.6】回文數(Noip1999)
洛谷 P1015 [NOIP1999 普及組] 回文數
注：兩OJ上的問題考察內容相同，但輸出要求不同

【題目考點】

1.高精度 n進制運算

數字數組每個元素保存n進制數字的1位

例：16進制數字A5F，
用數字數組表示為：a[0]:3, a[1]:15, a[2]:5, a[3]:10
十進制高精度計算函數中出現10的位置，都用n來代替，即為n進制計算。

【解題思路】

根據題目描述，先讀入高精度數字。
循環進行：判斷該數字是不是回文數字，如果是則輸出結果，程序結束。如果不是，則循環構造其逆向的數字，然后二者加和。循環此過程。
如果到最后也沒有找到回文數字，輸出Impossible。

【題解代碼】

兩個OJ上的輸出要求不同，因而輸出部分代碼有差異。其它部分都是相同的。

ybt 1309：【例1.6】回文數(Noip1999)：

#include<bits/stdc++.h> using namespace std; #define N 105 int n, a[N]; char s[N]; void tonum(char s[], int a[])//轉為數字數組 {int len = strlen(s);for(int i = 1; i <= len; ++i){if(s[len-i] >= '0' && s[len-i] <= '9')a[i] = s[len-i] - '0';elsea[i] = s[len-i] - 'A' + 10;}a[0] = len; } void genOpp(int a[], int b[])//生成a的逆向數字b {for(int i = 1; i <= a[0]; ++i)//生成a的逆向數字b b[i] = a[a[0]+1-i];b[0] = a[0]; } void addToA(int a[], int b[])//n進制高精度加法 a += b {int c = 0; for(int i = 1; i <= a[0] || i <= b[0]; ++i){a[i] += b[i] + c; c = a[i] / n;//n進制 a[i] %= n;}if(c > 0)a[++a[0]] = c; } bool isPalin(int a[])//判斷數字a是否是回文的 {for(int i = 1; i <= a[0]/2; ++i)//遍歷一半數組 {if(a[i] != a[a[0]-i+1])return false;}return true; } int main() {int b[N] = {};//b:a的逆向數字 cin >> n >> s;tonum(s, a);for(int i = 0; i <= 30; ++i){if(isPalin(a)){cout << i;return 0;}genOpp(a, b);//生成a的逆向數字baddToA(a, b);//a+=b}cout << "Impossible";return 0; }

洛谷 P1015 [NOIP1999 普及組] 回文數：

#include<bits/stdc++.h> using namespace std; #define N 105 int n, a[N]; char s[N]; void tonum(char s[], int a[])//轉為數字數組 {int len = strlen(s);for(int i = 1; i <= len; ++i){if(s[len-i] >= '0' && s[len-i] <= '9')a[i] = s[len-i] - '0';elsea[i] = s[len-i] - 'A' + 10;}a[0] = len; } void genOpp(int a[], int b[])//生成a的逆向數字b {for(int i = 1; i <= a[0]; ++i)//生成a的逆向數字b b[i] = a[a[0]+1-i];b[0] = a[0]; } void addToA(int a[], int b[])//n進制高精度加法 a += b {int c = 0; for(int i = 1; i <= a[0] || i <= b[0]; ++i){a[i] += b[i] + c; c = a[i] / n;//n進制 a[i] %= n;}if(c > 0)a[++a[0]] = c; } bool isPalin(int a[])//判斷數字a是否是回文的 {for(int i = 1; i <= a[0]/2; ++i)//遍歷一半數組 {if(a[i] != a[a[0]-i+1])return false;}return true; } int main() {int b[N] = {};//b:a的逆向數字 cin >> n >> s;tonum(s, a);for(int i = 0; i <= 30; ++i){if(isPalin(a)){cout << "STEP=" << i;return 0;}genOpp(a, b);//生成a的逆向數字baddToA(a, b);//a+=b}cout << "Impossible!";return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1309：【例1.6】回文数(Noip1999) | 洛谷 P1015 [NOIP1999 普及组] 回文数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。