問題:
? ??古典問題:有一對兔子峰搪,從出生后3個月起每個月都生一對兔子橄镜,小兔子長到第三個月后每個月又生一對兔子绩脆,加入兔子都不死,問每個月的兔子總數(shù)是多少阎毅?
? ? 分析:
? ????1,兔子的規(guī)律:1,1,2,3,5,8,13,21...
? ? ? 2点弯,第一個月和第二個月的都是1扇调,后面的每個月的兔子數(shù)都符合前一個月的加再前一個月的
? ? ? 3,可以使用遞歸來做抢肛,時間復(fù)雜度是O()
? ? ? 4狼钮,可以采用循環(huán)來做,時間復(fù)雜度是O(n)
代碼1:O(n),循環(huán)來做
main(){
? ? int i,f1=1,f2=1;
? ? ? ? for(i=0;i<10;i++){
? ? ? ? ? ? printf("%d %d ",f1,f2);
? ? ? ? ? ? f1=f1+f2;
? ? ? ? ? ? f2=f1+f2;
? ? ? ? }
}
結(jié)果:
? ? 代碼2:遞歸
int f(int n){
? ? if(n==1||n==2){
? ? ? ? return 1;
? ? }else{
? ? ? ? return f(n-1)+f(n-2);
? ? }
}
main(){
? ??for(i=1;i<21;i++){
? ? ? ? ? ? printf("%d ",f(i));
? ? ? ? }
}
結(jié)果: