筆者在高中生解題系統上選出一些關於費氏數列的題目:
- a134: 00948 - Fibonaccimal Base:https://zerojudge.tw/ShowProblem?problemid=a134
- b837: 104北二1費氏數列:https://zerojudge.tw/ShowProblem?problemid=b837
- d486: Fibonacci 's computation process:https://zerojudge.tw/ShowProblem?problemid=d486
在數學上,費波那契數列是以遞迴的方法來定義:
用文字來說,就是費波那契數列由0和1開始,之後的費波那契系數就是由之前的兩數相加而得出。首幾個費波那契系數是:
- (n≧2)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……(OEIS中的數列A000045)
特別指出:0不是第一項,而是第零項。
根據此數學定義,所以我們可以寫出底下遞迴版本 Python 程式:
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=', ') |
或是用動態規劃版本 Python 程式:
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=', ') |
註:上頭兩個程式在效能上還可以提升,那要怎麼做呢?
了解後,就可以開始試著解這三題了。
a134: 00948 - Fibonaccimal Base:https://zerojudge.tw/ShowProblem?problemid=a134
這一題筆者採取動態規劃的方式,因為第40項費氏數為102,334,155大於題目的最大值100,000,000,所以先求出前39項的費氏數列,再做輸出的運算就可以了。
Python解題程式碼:
a134: 00948 - Fibonaccimal Base:https://zerojudge.tw/ShowProblem?problemid=a134
這一題筆者採取動態規劃的方式,因為第40項費氏數為102,334,155大於題目的最大值100,000,000,所以先求出前39項的費氏數列,再做輸出的運算就可以了。
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 | 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解題程式碼:
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解題程式碼:
這一題筆者採取動態規劃的方式,因為第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()) |
沒有留言:
張貼留言