當初在學遞迴的結構時，一直對於遞迴該怎麼用很是不解。所以想藉由這篇文章做些練習讓我能更熟悉遞迴怎麼用。
這題可以用DP的概念去解，假設Kevin有7隻筷子1 2 3 4 5 6 7，先砍4，剩下1 2 3 0 1 2 3，而1 2 3又是另外一個問題。這正是DP的用小問題去推出大問題 的精神。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<iostream>
using namespace std;
long long cut(long long n){
if(n==2){return 2;}
else if(n==1){return 1;}
return cut(n/2)+1;
}
int main(){
long long n;
while(cin>>n){
cout<<cut(n)<<endl;
}
return 0;
}
|
在解的過程中，我發現了一個規律。當有1根筷子，只需切1次。當有2~3根筷子，需切2次。當有4~7根筷子，需切3次。也就是筷子的數量和切的次數有log2的關係。
1
2
3
4
5
6
7
8
9
10
11
| #include<iostream>
#include<cmath>
using namespace std;
int main(){
long long n;
while(cin>>n){
cout<<(int)log2(n)+1<<endl;
}
return 0;
}
|
在建表的時候發現了一個神奇的規律，這是我建表時寫的code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<stdio.h>
#include<time.h>
int f91(int n){
if(n<=100){
return f91(f91(n+11));
}
return n-10;
}
int main(){
clock_t start,end;
start = clock();
int i;
for(i=0;i<=100;i++){
if(i%5==0 && i!=0){printf("\n");}
printf("f(%3d) =%3d ",i,f91(i));
}
end = clock();
double diff = end-start;
printf("\n共花%lfs\n",diff / CLOCKS_PER_SEC);
return 0;
}
|
這是輸出結果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| f( 0) = 91 f( 1) = 91 f( 2) = 91 f( 3) = 91 f( 4) = 91
f( 5) = 91 f( 6) = 91 f( 7) = 91 f( 8) = 91 f( 9) = 91
f( 10) = 91 f( 11) = 91 f( 12) = 91 f( 13) = 91 f( 14) = 91
f( 15) = 91 f( 16) = 91 f( 17) = 91 f( 18) = 91 f( 19) = 91
f( 20) = 91 f( 21) = 91 f( 22) = 91 f( 23) = 91 f( 24) = 91
f( 25) = 91 f( 26) = 91 f( 27) = 91 f( 28) = 91 f( 29) = 91
f( 30) = 91 f( 31) = 91 f( 32) = 91 f( 33) = 91 f( 34) = 91
f( 35) = 91 f( 36) = 91 f( 37) = 91 f( 38) = 91 f( 39) = 91
f( 40) = 91 f( 41) = 91 f( 42) = 91 f( 43) = 91 f( 44) = 91
f( 45) = 91 f( 46) = 91 f( 47) = 91 f( 48) = 91 f( 49) = 91
f( 50) = 91 f( 51) = 91 f( 52) = 91 f( 53) = 91 f( 54) = 91
f( 55) = 91 f( 56) = 91 f( 57) = 91 f( 58) = 91 f( 59) = 91
f( 60) = 91 f( 61) = 91 f( 62) = 91 f( 63) = 91 f( 64) = 91
f( 65) = 91 f( 66) = 91 f( 67) = 91 f( 68) = 91 f( 69) = 91
f( 70) = 91 f( 71) = 91 f( 72) = 91 f( 73) = 91 f( 74) = 91
f( 75) = 91 f( 76) = 91 f( 77) = 91 f( 78) = 91 f( 79) = 91
f( 80) = 91 f( 81) = 91 f( 82) = 91 f( 83) = 91 f( 84) = 91
f( 85) = 91 f( 86) = 91 f( 87) = 91 f( 88) = 91 f( 89) = 91
f( 90) = 91 f( 91) = 91 f( 92) = 91 f( 93) = 91 f( 94) = 91
f( 95) = 91 f( 96) = 91 f( 97) = 91 f( 98) = 91 f( 99) = 91
f(100) = 91
共花0.000229s
|
只要輸入的n<=100，無論n是多少，最後的結果都是91 ！這下好辦了，只需要判斷輸入的n的大小，如果>100就輸出n-10，<=100就輸出91。這題要建表應該也沒問題，畢竟真的從0算到100也只花0.0002秒 ，只不過不建的話，程式碼就可以非常精簡。
1
2
3
4
5
6
7
8
9
10
| #include<stdio.h>
int main(){
int n;
while(scanf("%d",&n) && n){
if(n<=100){printf("f91(%d) = 91\n",n);}
else{printf("f91(%d) = %d\n",n,n-10);}
}
return 0;
}
|
封面圖源：AcFun
