## 基础练习 特殊回文数   时间限制：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; } ~~~