26. Fibonaccimal Base (CPE10401, UVA948) - CPE一顆星解答與說明
CPE一顆星49題解答 - pdf 電子檔，售價 199 元，
購買電子檔可將筆記與完整解答帶著走，
坐車、上課時皆可隨時複習，
不受網路或廣告影響，
若有需要請來信購買 greens2314@gmail.com
題目
- 任一正整數可用費式數表達
- 例如：17 = 1 + 3 + 13
- 不可以連續使用費氏數列中的數字
- 0 代表沒有用到的項目，1 代表有用到的項目
- 17 = 100101
輸入說明
- 第一行的數字 N 是宣告接下來有幾筆數字
- 每筆數字小於 100000000，不照順序
輸出說明
- 一行為一筆輸出資料
- 輸出格式為 原始數字 = 費式表達式(fib)
解題技巧
- 產生費式數列
- 計算費式表達式
- 認識費式數列
- 數列有 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...，除了最前面的兩個數值 0 與 1 之外，其他數值皆為前兩個的相加
- 例如 8 = 5 + 3
- 要注意題目並沒有使用費式數列的 Fib(0) 與 Fib(1) ，費式表達式從 Fib(2) 開始使用
解題過程
取得輸入
- 取得資料筆數，使用 nextInt()
- 根據資料筆數，使用 for 迴圈讀取資料
- 讀取數字 nextInt()
新增初始的費式數列
- 使用串列儲存多筆費式數
- ArrayList<Integer> fibList = new ArrayList<Integer>();
- 此處的類別不能放基本資料型別，要放參考資料類別
- 串列不用指定串列大小，方便新增費式數
- 新增費式數，呼叫 List 類別提供的 add() 方法
- 新增 Fib(2) = 1，與 Fib(3) = 2
- 新的費式數 = 前面第一個費式數 + 前面第兩個費式數
- 只要有兩個費式數，就可以一直擴增
- 例如： 3 = 2 + 1
產生夠用的費式數列
- 使用 while 迴圈判斷
- 若原始數字大於串列中最大的費式數(串列最後一個)
- 須產生新的費式數，直到原始數字小於串列中最大的費式數，這樣才能計算出此原始數字的費式表達式
- 取得費式數的數量，呼叫 List 類別提供的 size() 方法，找出最後1,2個的位置
- 取得特定位置的費式數，呼叫 List 類別提供的 get() 方法，找出最大的費式數
- 某一個費式數 = 前面第一個費式數 + 前面第兩個費式數
計算測試資料的費式表達式
- 根據題目要求，使用 0 與 1 表示
- 費式表達式最左邊為 1，不可為 0
- 宣告 boolean isPrintZero = false 來控管是否可印出 0
- 使用 for 迴圈，從最大的費式數開始檢查，逐次遞減
- 判斷數字是否大於特定的費式數
- 大於：
- 找到可表達的費式數，印出 1 ，可開始印出 0，將 isPrintZero 更新為 true
- 將數字更新為數字減掉此費式數
- 小於
- 找不到可表達的費式數，若可開始印出 0，則印出 0
留言
張貼留言