104年地方特考四等程式設計概要
|
三、定義一個函數如下： int f(int n) { if(n == 0) return 0; if(n == 1) return 1; if(n == 2) return 2; return f(n-1)+f(n-2)+f(n-3); } 請問計算 f(6) 時，共呼叫 f(n) 幾次？（8分） |
答：
|
#include <stdio.h> int count = 0; int f(int n) { count++; if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return 2; return f(n - 1) + f(n - 2) + f(n - 3); } int main( ) { f(6); printf("呼叫 f(6) 次數 = %d", count); return 0; } |
執行結果：
呼叫 f(6) 次數 = 25
說明：
呼叫 f(n) 幾次：
int f(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
if(n == 2) return 2;
return f(n-1)+f(n-2)+f(n-3);
}
f(0) 呼叫1次
f(1) 呼叫1次
f(2) 呼叫1次
f(3) 呼叫1+f(2)+f(1)+f(0)，總共1+1+1+1 = 4次
f(4) 呼叫1+f(3)+f(2)+f(1)，總共1+4+1+1 = 7次
f(5) 呼叫1+f(4)+f(3)+f(2)，總共1+7+4+1 = 13次
f(6) 呼叫1+f(5)+f(4)+f(3)，總共1+13+7+4 = 25次
...
f(n) 呼叫1+f(n-1)+f(n-2)+f(n-3)，導出公式：
|
f(0) |
f(1) |
f(2) |
f(3) |
f(4) |
f(5) |
f(6) |
f(7) |
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
1+1+1+1=4 |
|
|
|
|
|
|
|
|
|
1+1+1+4=7 |
|
|
|
|
|
|
|
|
|
1+1+4+7=13 |
|
|
|
|
|
|
|
|
|
1+4+7+13=25 |
|
|
|
|
|
|
|
|
|
1+7+13+25=46 |
留言列表
國考資訊處理解答 (7)
