iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 20
1
自我挑戰組

從0開始,一起學C語言吧!系列 第 20

從0開始,一起學C語言吧!(Day20)

  • 分享至 

  • xImage
  •  

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;
}

印出:
https://ithelp.ithome.com.tw/upload/images/20190919/20119958Etv38USlIj.png
那這個印出來你會發現和上一篇最後一個範例相同
那我們可以發現在用這個非遞迴的方式寫編譯時會比遞迴執行時速度有明顯差異,非遞迴的方式,他的執行效率較高
遞迴的方式:
https://ithelp.ithome.com.tw/upload/images/20190919/20119958IAo2PuQurP.png
非遞迴的方式:
https://ithelp.ithome.com.tw/upload/images/20190919/201199580EH3BTRYnQ.png
那我稍微解釋一下費式數列
費式數列(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);
}

印出:
https://ithelp.ithome.com.tw/upload/images/20190919/201199581X0iNxGrJb.png
解釋:第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;
}

印出:
https://ithelp.ithome.com.tw/upload/images/20190919/20119958JoUKNJWJkl.png
那這一題是用for迴圈來做的
那今天教先到這了阿
謝謝大家今天的閱讀


上一篇
從0開始,一起學C語言吧!(Day19)
下一篇
從0開始,一起學C語言吧!(Day21)
系列文
從0開始,一起學C語言吧!30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言