▼

Python 費氏數列

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

筆者在高中生解題系統上選出一些關於費氏數列的題目：
針對這幾個題目要如何解題呢？首先要了解什麼是費氏數列，我們可從Wikipedia費氏數列的說明知道(底下文字節錄自Wikipedia費氏數列)：
在數學上，費波那契數列是以遞迴的方法來定義：
  • （n≧2）
用文字來說，就是費波那契數列由0和1開始，之後的費波那契系數就是由之前的兩數相加而得出。首幾個費波那契系數是：
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=', ')

 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解題程式碼：
 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())

沒有留言:

張貼留言