## 基礎練習 特殊回文數 ?
時間限制: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;
}
~~~
- 前言
- 入門訓練四道題
- 基礎練習之閏年判斷——BASIC-1
- 基礎練習之01字串——BASIC-2
- 基礎練習之字母圖形——BASIC-3
- 基礎練習之數列特征——BASIC-4
- 基礎練習之查找整除——BASIC-5
- 基礎練習之楊輝三角形——BASIC-6
- 基礎練習之特殊的數字——BASIC-7
- 基礎練習之回文數——BASIC-8
- 基礎練習之特殊回文數——BASIC-9
- 基礎練習之十進制轉十六進制——BASIC-10
- 基礎練習之十六進制轉十進制——BASIC-11
- 基礎練習之十六進制轉八進制——BASIC-12
- 基礎練習之數列排序——BASIC-13
- 算法訓練之區間K大數查詢——ALGO-1
- 算法訓練之最大最小公倍數——ALGO-2
- 藍橋杯-代碼填空之一
- 藍橋杯-代碼填空之二
- 藍橋杯-代碼填空之三
- 藍橋杯-代碼填空之精品
- 藍橋杯-歷屆試題之翻硬幣
- 藍橋杯-代碼填空之四
- 藍橋杯-結果填空題
- 藍橋杯-結果填空之排座位
- 藍橋杯-歷屆試題之大臣的旅費