問題描述
　　若一個數（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數。
　　例如：給定一個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（其中16進制數字為0-9與A-F），求最少經過幾步可以得到回文數。
　　如果在30步以內（包含30步）不可能得到回文數，則輸出“Impossible!”
輸入格式
　　兩行，N與M
輸出格式
　　如果能在30步以內得到回文數，輸出“STEP=xx”（不含引號），其中xx是步數；否則輸出一行”Impossible!”（不含引號）
樣例輸入
9
87
樣例輸出

STEP=6

解析：回文數我們應該都可以懂是什么意思。理一下解題思路：判斷是不是回文數->如果是，輸出第一步；如果不是，按照題目要求進行加法，同時記錄步數->每做一步，進行一次判斷看是不是回文數，直到找到或者不可能為止。

理清了思路之后，我們就比較好寫代碼了：

#include<iostream> #include<string.h> using namespace std; char a[100]; int b[100]={0}; int result[102]={0}; int sum = 0; void trans_num(char judge[])//將字符型轉化成數字型 {for(int i = 0; i < sum; i++){if(judge[i]>='a'&&judge[i]<='z') b[i] = judge[i]-'a'+10;else if(judge[i]>='A'&&judge[i]<='Z')b[i] = judge[i]-'A'+10;elseb[i] = judge[i]-'0';} } void add(int judge[],int n)//實行加法運算 ,n表示n進制 {result[0] = 0;//手動初始化 for(int i = 0; i < sum; i++){result[i] += judge[i] + judge[sum-1-i];result[i+1] = result[i]/n;//進位 result[i] = result[i]%n;//本位 } if(result[sum]!=0)//產生進位 {sum = sum + 1;} } void trans_result_to_b(int judge[])//將add結果放入到b數組中 {int j = 0;for(int i = sum-1; i >= 0; i--){b[j] = judge[i];j++;} } bool isPalindrome(int judge[]) {int flag = 1;int i = 0; int j = sum-1;while(1){if(judge[i]!=judge[j]){flag = 0;break;}else{if(i==j || i+1==j) break;i++;j--;}}if(flag==0) return false;else return true; } int main() {int N; //N進制 int step = 1;//記錄步數 int flag = 0;//記錄是否能找到回文數 cin>>N;getchar();//吃回車 gets(a);//獲得數組 sum = strlen(a);//數組的長度 trans_num(a);//將字符型數組轉化成數字型數組 add(b,N);//進行加法運算 trans_result_to_b(result);//將結果數組放到b數組中 if(isPalindrome(b)){cout<<"STEP=0"<<endl;}else{while(1){if(isPalindrome(b)){flag = 1;//找到回文數 break;}else if(step>30){flag = 0;//沒有找到回文數 break;} else{add(b,N);//進行加法運算 trans_result_to_b(result);//將結果數組放到b數組中 step++;} } if(flag==1)cout<<"STEP="<<step<<endl;elsecout<<"Impossible!"<<endl;} return 0; }
tips：在對數組進行處理，尤其是進行加法運算的時候，注意一下這里數據的特殊性——回文數，這就意味著數組從低位到高位元素分別為167或者761都是一樣的。意識到這一點，就給我們計算帶來了很大方便，不需要去考慮什么低位的數字權重高什么的。。。

最初的時候，進行進制轉化時，我沒有考慮到十六進制字母的轉化，所以沒有一次過，看來思維嚴密性還是有待提高。加油！

總結

以上是生活随笔為你收集整理的算法训练_ALGO14_回文数的全部內容，希望文章能夠幫你解決所遇到的問題。

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