#39247: 如何把一個數字拆成幾個費氏數的加總


n12603579table@gmail.com (施智皓)

學校 : 不指定學校
編號 : 145648
來源 : [36.234.171.196]
最後登入時間 :
2024-04-04 21:19:31
a134. 00948 - Fibonaccimal Base -- UVa948 | From: [36.234.167.137] | 發表日期 : 2024-01-27 14:36

給定數字N,找小於它的費氏數之中最大的那一個數字(叫做a1),

接著,拿N減去a1,得到的數字就可以重複前面的過程,找小於它的費氏數之中最大的那一個(叫做a2),

需要注意a2這個數字不可以是a1隔壁的數,你可以寫一個flag來協助判定有沒有在隔壁。

照這樣依此類推 可以找出 N = a1 + a2 +a3 +a4 +.....

直到減到剛好為0為止(一定可以,這很奇異)。

 

例子:

費氏數列 1,2,3,5,8,13,21,34,55,....(略)

N = 17

最靠近17的數是13 >> 17-13=4

最靠近4的數字是3,且3不在13隔壁 >>4-3=1

最靠近1的數字是1>>1-1=0

所以,17 = 13 + 3 +1

 

 
ZeroJudge Forum