阿摩線上測驗
題組內容
四、有一費氏(Fibonacci)數學函式如下：（3 題，每題 5 分，共 15 分）
F(n) = F(n – 1) + F(n – 2)，n ＞ 0
F(1) = 1、F(0) = 0
F(1) = 1、F(0) = 0
(二)請以非遞迴(Non- Recursive)方式寫出上列函式程式碼。
詳解 (共 2 筆)
詳解
int F0=0;
int F1=1;
void main()
{
int n=0;
scanf("%d",&n);
int Fn=0;
Fn=F2(n,Fn);
printf("F%d=%d",n,Fn);
}
int F2(int n,int Fn)
{
int F_1,F_2;
F_1=F1;
F_2=F0;
if(n>1)
{
for(int x=2;x<=n;++x)
{
Fn=F_1+F_2;
F_2=F_1;
F_1=Fn;
}
return Fn;
}
else if(n<=1 && n>=0)
{
return n;
}
else
{
printf("數值小於0!超過範圍!");
return -1;
}
}
詳解
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
fib_prev = 0
fib_curr = 1
for _ in range(2, n + 1):
fib_next = fib_prev + fib_curr
fib_prev = fib_curr
fib_curr = fib_next
return fib_curr
if n == 0:
return 0
elif n == 1:
return 1
fib_prev = 0
fib_curr = 1
for _ in range(2, n + 1):
fib_next = fib_prev + fib_curr
fib_prev = fib_curr
fib_curr = fib_next
return fib_curr
# 測試範例
for i in range(10):
print(f"F({i}) = {fibonacci(i)}")
解釋
基本情況 (Base Cases)：
for i in range(10):
print(f"F({i}) = {fibonacci(i)}")
解釋
基本情況 (Base Cases)：
當 n 等於 0 時，返回 0。
當 n 等於 1 時，返回 1。
迭代步驟 (Iterative Step)：
當 n 等於 1 時，返回 1。
迭代步驟 (Iterative Step)：
初始化兩個變數 fib_prev 和 fib_curr 分別為 0 和 1，表示費氏數列的前兩個值。
使用一個 for 迴圈從 2 遍歷到 n，計算後續的費氏數列值。
在每次迭代中，計算下一個費氏數列值 fib_next，將 fib_prev 更新為 fib_curr，將 fib_curr 更新為 fib_next。
迴圈結束後，fib_curr 即為所求的 F(n) 值。
這個函式使用迭代方法計算費氏數列，避免了遞迴帶來的重複計算和性能問題，適合較大的 n 值。
使用一個 for 迴圈從 2 遍歷到 n，計算後續的費氏數列值。
在每次迭代中，計算下一個費氏數列值 fib_next，將 fib_prev 更新為 fib_curr，將 fib_curr 更新為 fib_next。
迴圈結束後，fib_curr 即為所求的 F(n) 值。
這個函式使用迭代方法計算費氏數列，避免了遞迴帶來的重複計算和性能問題，適合較大的 n 值。