筆者在高中生解題系統上選出一些關於費氏數列的題目：
針對這幾個題目要如何解題呢？首先要了解什麼是費氏數列，我們可從
Wikipedia費氏數列的說明知道(底下文字節錄自
Wikipedia費氏數列)：
在數學上，費波那契數列是以遞迴的方法來定義：
（n≧2）
用文字來說，就是費波那契數列由0和1開始，之後的費波那契系數就是由之前的兩數相加而得出。首幾個費波那契系數是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……（OEIS中的數列A000045）
特別指出：0不是第一項，而是第零項。
1
2
3
4
5
6
7
8
9
10
11
| def fibon(n):
# 檢查 n 是否為整數
if(type(n) == int):
if n < 2:
return n
else:
return fibon(n-1) + fibon(n-2)
fibon(3.3) # 測試浮點數
for i in range(10):
print(fibon(i), end=', ')
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def dp_fib(n):
if n < 2:
return n
n0 = 0
n1 = 1
fib = 0
for i in range(n-1):
fib = n1 + n0
n0 = n1
n1 = fib
return fib
# 輸出前 9 項
for i in range(10):
print(dp_fib(i), end=', ')
|
註：上頭兩個程式在效能上還可以提升，那要怎麼做呢？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import sys
fibs = list(range(40))
fibs[0] = 0
fibs[1] = 1
for i in range(2, 40):
fibs[i] = fibs[i-1] + fibs[i-2]
#print(fibs)
n = int(input())
for x in range(n):
d = int(input())
print(str(d) + " = ", end="")
isPut = False
for i in range(39, 1, -1):
if d >= fibs[i]:
d = d - fibs[i]
isPut = True
print("1", end="")
elif isPut == True:
print("0", end="")
print(" (fib)")
|
b837: 104北二1費氏數列：https://zerojudge.tw/ShowProblem?problemid=b837
這一題筆者採取動態規劃的方式，因為第31項費氏數為1,346,269大於題目的最大值1,000,000，所以先求出前30項的費氏數列，並使用
bisect找出 lower and upper bounds的費氏數做輸出的運算就可以了。
Python解題程式碼：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| from bisect import bisect_left
from bisect import bisect_right
fibs = list(range(31))
fibs[0] = 0
fibs[1] = 1
for i in range(2, 31):
fibs[i] = fibs[i-1] + fibs[i-2]
# print(fibs)
t = int(input())
for x in range(t):
a, b = input().split()
a = int(a)
b = int(b)
# b = int(input())
low = 0
high = 0
if(a >= b):
low = bisect_left(fibs, b)
high = bisect_right(fibs, a)
else:
low = bisect_left(fibs, a)
high = bisect_right(fibs, b)
# print("Low = ", low, " High = ", high)
# print("Starting = ", fibs[low], " Ending = ", fibs[high])
count = high - low
i = low
while i < high:
print(fibs[i])
i = i + 1
print(count)
if x < t - 1:
print("------")
|
d486: Fibonacci 's computation process：https://zerojudge.tw/ShowProblem?problemid=d486
和前兩題一樣，用動態規劃算出前15項的和，但是 f(0) 的值改為 1，接著將 n 當成串列 g，演算法如下：
當串列 g 的某一元素大於或等於 2 時
{
r 為空串列
若 g 的元素大於或等於2時
{
將此元素減 1，放到 r
將此元素減 2，放到 r
}
否則 { 將此元素放到 r }
g = r
輸出 r 的結果
}
Python解題程式碼：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| fibs = list(range(16))
fibs[0] = 1
fibs[1] = 1
for i in range(2, 16):
fibs[i] = fibs[i-1] + fibs[i-2]
n = int(input())
while n != 0:
g = [n]
print("f(" + str(n) + ") ")
while any( i >= 2 for i in g):
r = []
for t in g:
if t >= 2:
r.append(t - 1)
r.append(t - 2)
else:
r.append(t)
g = r
for t in r:
print("f(" + str(t) + ") ", end="")
print()
print("f(" + str(n) + ") = " + str(fibs[n]))
n = int(input())
|
若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。
If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.
留言