基础练习之特殊回文数——BASIC-9
最后更新于：2022-04-01 14:53:01
## 基础练习 特殊回文数
时间限制：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;
}
~~~