高中生程式解題系統:a134: 00948 - Fibonaccimal Base

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

題目連結 https://zerojudge.tw/ShowProblem?problemid=a134

此題和 c121: 00495 - Fibonacci Freeze 、LintCode: Fibonacci 費布那西數列很接近,都是與費波那契數列有關

程式碼是先建立好Fibonacci數列,也知道N最大值為500,所以就建立前40項的Fibonacci數列。從小於N的最大Fibonacci數開始找起,就可以唯一的表示法。

程式碼:
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)")

沒有留言: