題目請參考 https://zerojudge.tw/ShowProblem?problemid=h098.
這題我的想法很簡單, 就是把數字用從左到右的順序來試, 每一位都從0到9猜, 每猜一個數字就進入右一位. 這樣會有下面幾種情況.
狀況1.數字已超過20, 那後面位數也不用猜了, 回上一層換下一個數字繼續猜.
狀況2.剛好滿20, 那後面的位數都不用猜了, 一定都是0. 找到這一組答案後,回上一層換下一個數字繼續猜.
狀況3.猜了九位後,就不用再猜了, 回上一層換下一個數字繼續猜.
前面三個狀況都不是, 那從數字0到9猜一遍.
char number[20]="0 0 0 0 0 0 0 0 0";
char ascii[11]="0123456789";
void GetString(int index, int sum){
//狀況1
if(sum>20){
return;
}
//狀況2
if(sum==20){
for(int i=index;i<9;i++){
number[i<<1]='0';
}
printf("%s\n",number);
return;
}
//狀況3
if(index>=9){
return;
}
//從0到9猜
for(int i=0;i<10;i++){
number[index<<1]=ascii[i];
GetString(index+1, sum+i);
}
}以下為完整程式碼, 執行時間約0.5秒.
#include <iostream>
using namespace std;
char number[20]="0 0 0 0 0 0 0 0 0";
char ascii[11]="0123456789";
void GetString(int index, int sum){
//狀況1
if(sum>20){
return;
}
//狀況2
if(sum==20){
for(int i=index;i<9;i++){
number[i<<1]='0';
}
printf("%s\n",number);
return;
}
//狀況3
if(index>=9){
return;
}
//從0到9猜
for(int i=0;i<10;i++){
number[index<<1]=ascii[i];
GetString(index+1, sum+i);
}
}
int main()
{
GetString(0,0);
return 0;
}
