Day20-非遞迴方式
那上一篇我們最後教到了遞迴函式,那在範例中我們做了一題n!的計算程式,那天我們要教的是非遞迴的方式
範例:
#include<stdio.h>
#include<stdlib.h>
int factorial(int);
int main(void){
int n;
printf("Input n:");
scanf("%d",&n);
printf("%d!=%d",n,factorial(n));
system("pause");
}
int factorial(int n){
int i,fac=1;
for(i=1;i<=n;i++)
fac=fac*i;
return fac;
}
印出:
那這個印出來你會發現和上一篇最後一個範例相同
那我們可以發現在用這個非遞迴的方式寫編譯時會比遞迴執行時速度有明顯差異,非遞迴的方式,他的執行效率較高
遞迴的方式:
非遞迴的方式:
那我稍微解釋一下費式數列
費式數列(f(n)=f(n-1)+f(n-2)),當呼叫f(n)時,會計算f(n-1)和f(n-2),當呼叫f(n-1)時會計算出f(n-2)和 f(n-3),過程中f(n-1)會重複計算一次
範例:費式數列(遞迴版)
公式:f(n)=f(n-1)+f(n-2)
#include<stdio.h>
#include<stdlib.h>
int f(int);
int main(void){
int n;
printf("Input n:");
scanf("%d",&n);
printf("f(%d)=%d\n",n,f(n));
system("pause");
}
int f(int n){
if(n==1||n==2)
return 1;
return f(n-1)+f(n-2);
}
印出:
解釋:第12行if判斷式就是遞迴含是的中止條件
範例:費式數列(非遞迴版)
#include<stdio.h>
#include<stdlib.h>
int f(int);
int main(void){
int n;
printf("Input n:");
scanf("%d",&n);
printf("f(%d)=%d\n",n,f(n));
system("pause");
}
int f(int n){
int i,sum,pre,fi;
pre=0;
fi=1;
for(i=1;i<n;i++){
sum=pre+fi;
pre=fi;
fi=sum;
}
return fi;
}
印出:
那這一題是用for迴圈來做的
那今天教先到這了阿
謝謝大家今天的閱讀