## 基礎練習 特殊回文數 ? 時間限制：1.0s ? 內存限制：512.0MB ? 問題描述 　　123321是一個非常特殊的數，它從左邊讀和從右邊讀是一樣的。 　　輸入一個正整數n， 編程求所有這樣的五位和六位十進制數，滿足各位數字之和等于n 。 輸入格式 　　輸入一行，包含一個正整數n。 輸出格式 　　按從小到大的順序輸出滿足條件的整數，每個整數占一行。 樣例輸入 52 樣例輸出 899998 989989 998899 數據規模和約定 　　1<=n<=54。 直觀一點的，這個多加了一條剪枝，如果是五位數，在第一位數確定后 n-第一位數差不得大于 36，因為后面四位數最大為9999 所以不能大于36，其他幾位數如是 ~~~ // 特殊回文數 #include <iostream> using namespace std; int n; int f[5],s[6]; bool judge(int ws,int no) { int i,sum=0; if(ws==5) { if(no==1) { if(n-f[0]>36 || n-f[0]<0) return 0; } else if(no==2) { for(i=0;i<no;++i) sum+=f[i]; if(n-sum>27 || n-sum<0) return 0; } else if(no==3) { for(i=0;i<no;++i) sum+=f[i]; if(n-sum>18 || n-sum<0) return 0; } else if(no==4) { if(f[3]!=f[1]) return 0; for(i=0;i<no;++i) sum+=f[i]; if(n-sum>9 || n-sum<0) return 0; } else { if(f[4]!=f[0]) return 0; for(i=0;i<no;++i) sum+=f[i]; if(sum!=n) return 0; } } else { if(no==1) { if(n-s[0]>45 || n-s[0]<0) return 0; } else if(no==2) { for(i=0;i<no;++i) sum+=s[i]; if(n-sum>36 || n-sum<0) return 0; } else if(no==3) { for(i=0;i<no;++i) sum+=s[i]; if(n-sum>27 || n-sum<0) return 0; } else if(no==4) { if(s[3]!=s[2]) return 0; for(i=0;i<no;++i) sum+=s[i]; if(n-sum>18 || n-sum<0) return 0; } else if(no==5) { if(s[4]!=s[1]) return 0; for(i=0;i<no;++i) sum+=s[i]; if(n-sum>9 || n-sum<0) return 0; } else { if(s[5]!=s[0]) return 0; for(i=0;i<no;++i) sum+=s[i]; if(sum!=n) return 0; } } } int main() { int i,j,k; while(cin>>n) { for(f[0]=1;f[0]<10;++f[0]) { if(!judge(5,1)) continue; for(f[1]=0;f[1]<10;++f[1]) { if(!judge(5,2)) continue; for(f[2]=0;f[2]<10;++f[2]) { if(!judge(5,3)) continue; for(f[3]=0;f[3]<10;++f[3]) { if(!judge(5,4)) continue; for(f[4]=0;f[4]<10;++f[4]) { if(!judge(5,5)) continue; for(i=0;i<5;++i) cout<<f[i]; cout<<endl; } } } } } for(s[0]=1;s[0]<10;++s[0]) { if(!judge(6,1)) continue; for(s[1]=0;s[1]<10;++s[1]) { if(!judge(6,2)) continue; for(s[2]=0;s[2]<10;++s[2]) { if(!judge(6,3)) continue; for(s[3]=0;s[3]<10;++s[3]) { if(!judge(6,4)) continue; for(s[4]=0;s[4]<10;++s[4]) { if(!judge(6,5)) continue; for(s[5]=0;s[5]<10;++s[5]) { if(!judge(6,6)) continue; for(i=0;i<6;++i) cout<<s[i]; cout<<endl; } } } } } } } return 0; } ~~~ 優化后的： ~~~ #include <iostream> using namespace std; int arr[7],i; bool isreturn(int num) { // 判斷它是五位還是六位 if(i%2==0) { if(arr[0]==arr[4] && arr[1]==arr[3]) return 1; return 0; } else { if(arr[0]==arr[5] && arr[1]==arr[4] && arr[2]==arr[3]) return 1; return 0; } } bool isequal(int num,int n) { int s=0; // 數分別存儲 i=0; while(num/10>0) { arr[i]=num%10; num/=10; s+=arr[i]; ++i; } arr[i]=num; s+=num; return n==s; } int main() { int num,n; while(cin>>n) { for(num=10000;num<1000000;++num) if(isequal(num,n)) if(isreturn(num)) cout<<num<<endl; } return 0; } ~~~