[UVA]Fibonaccimal Base

CPE10401、UVA 948 程式解題。

 

解題觀念 :


這題是費式數列的應用。所以一開始就要先把費式數列建立起來。

將數字拆解成可以用費式數列中的數字做相加，EX : 17 = 1 + 3 + 13。

然後再將這個組合，轉換成只用0和1來表示，費式數列中有用到的數字就印出1，沒有用到就印出0。(看題目中的 Figure2 。)

題目中有特別說明，數字大小不會超過100000000，所以費式數列的大小設定到38就夠了。



解題步驟 :

宣告整數陣列 f ，大小39格，存放費式數列。

宣告整數 n ， 存放測資個數；整數 m ，存放測試資料；整數 index ，設定陣列起始位置。

由於測試資料 1<= n <= 500，所以不用考慮0的狀況，直接設定f[0] = 1、f[1] = 1。

之後建立費式數列。((看註解部分。

接下來就是演算法的部分。先輸入測資個數存放到n，for迴圈的次數限定為 n。

輸入測試資料 m ，設定index的位置為陣列最後一格開始。

while迴圈部分，是要設定測試資料 m 要從哪一格陣列開始計算。
(EX : 17，陣列起始位置不能大於17，所以從13開始。)

所以如果 m 大於等於 目前陣列位置的數字，則要繼續往下遞減，一直找到小於m為止。

找到之後，將那一個陣列位置設為起始位置，存放到 index。

之後設定for迴圈，從 index為止，去跑費式數列中的每一格數字。

如果 m 大於等於 目前陣列位置的數字，則計算 m - f[j]，並印出1。

else，就印出0。

＊要注意的是，for迴圈的中止條件為 <=1 。因為f[0]也是等於1，如果跑到0才停止的話，會多印出一個0。


EX :

1
10

n =1。進入for迴圈，m = 10；index = 39 -1 = 38。

進入while，while(10<=f[38])，成立，index - -。
(中間省略......)

一直計算到 while(10<=f[5])，不成立，跳出while迴圈，此時 index = 5。

 (先將 m 和等號印出，後面跑 for迴圈就可以直接印出1或0。)

進入for迴圈。

進入判斷式， if(10 >= f[5] )成立，印出1，m = 10 - 8 = 2。

進入判斷式， if(2 >= f[4] )不成立，印出0。

進入判斷式， if(2 >= f[3] )不成立，印出0。

進入判斷式， if(2 >= f[2] )成立，印出1， m = 2 - 2 = 0。

進入判斷式， if(0 >= f[1] )不成立，印出0。

最後印出(fib)。

10 = 10010 (fib)


By   小K