UVA948：Fibonaccimal Base [JAVA]

Online Judge

Loading…

Taking too long?

Reload document

| Open in new tab

題目概要

費氏數列(費波那契數)頭15個數：(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610。即前兩數相加等於第三數，以此類推。

• 利用費氏數列將數值轉換為二進位。
• 首先輸入共 N 筆資料。
• 找出數值 X 的費氏數列並轉換為二進制，如 X: 17 = 13 + 3 + 1
  • 13 8 5 3 2 1
  • 1 0 0 1 0 1
  • 因此 17 = 13 + 3 + 1 = 100101

解題技巧

• 首先建立費氏數列表 (用遞迴寫很簡潔，但效能沒有迴圈來的好，看個人選擇)
• 測資數值不是很大，所以先建個長度為 40 的 array 就行。
• 找到距離 X 最相近的費氏數列索引再慢慢往回推，若 X 比該索引在費氏數列的值還大那就輸出 1，並且將 X 減去該費氏數列值，反之則輸出 0。

程式碼

import java.util.*;
import static java.lang.System.*;
public class main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int cases = sc.nextInt();
    // 獲得費氏數列前四十個的值
    int[] arr = new int[40];
    for (int i = 0; i <= 39; i++) {
        arr[i] = fib(i);
    }

    while (cases-- > 0) {
        int number = sc.nextInt();
        int index = arr.length - 1;

        // 找到距離該數最相近的費氏數列的索引
        while (number < arr[index]) {
            index--;
        }
        System.out.print(number + " = ");
        // 從最相近的索引開始往回找
        for (int j = index; j >= 1; j--) {
            // 若該數比費氏數列的數值大則輸出 1 並減去該費氏數列值
            if (number >= arr[j]) {
                System.out.print('1');
                number -= arr[j];
            } else { // 相反則輸出 0
                System.out.print('0');
            }
        }
        System.out.println(" (fib)");
    }
  }
  // 建立費氏數列
  public static int fib(int n) {
      if(n == 0) return 1;
      else if (n == 1) return 1;
      else return fib(n - 2) + fib(n - 1);
  }
};

• About
• Latest Posts

pluto

懶癌末期患者，正以經營博客治癒。

Latest posts by pluto (see all)

• React 那些好看、有趣、實用的函式庫、組件庫推薦(2) - 2022 年 6 月 26 日
• 解決 preact 資源請求路徑錯誤的問題 - 2022 年 6 月 24 日
• [楓之谷私服] 潮流轉蛋機 NPC 腳本優化 - 2022 年 6 月 19 日

相關文章:

[楓之谷私服]小遊戲系列NPC腳本(2) – BJ、GEMS、OX遊戲、Mastermind、猜數字 工作時經常用到的 JS 知識點及技巧(3)－陣列的處理 [楓之谷私服]小遊戲系列NPC腳本(1) – 21點、寶石連線、排列組合、踩地雷、老虎機 Golang學習筆記：陣列(Array)與切片(Slice) [楓之谷私服]v120 點裝附魔系統