題目連結 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)")
沒有留言:
張貼留言