awesq123的部落格

費氏數列

Fib(0) = 0

Fib(1) = 1

Fib(2) = 1

Fib(3) = 2

......

題目要求：

給你一個正整數，要你用Fibonacci Base to represent.

從大的開始挑，挑了之後扣掉，就可以得到結果。

--------

package uva948;

import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author awesq
 */
public class UVa948 {

    private static final int FIBO_MAX = 44;
    private static final int[] fibo = new int[FIBO_MAX];

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // fibo(45) > 1,000,000,000; from fibo(0) = 0
        fibo[0] = 1; // start from 0, 1, "1", 2
        fibo[1] = 2;
        for (int i = 2; i < FIBO_MAX; i++) {
            fibo[i] = fibo[i - 2] + fibo[i - 1];
        }

        try (Scanner sc = new Scanner(System.in)) {
            int cases = sc.nextInt();
            while (cases-- > 0) {
                int num = sc.nextInt();
                System.out.println(num + " = " + pick(num) + " (fib)");
            }
        } catch (Exception e) {
        }
    }

    public static String pick(int num) {
        // Convert the number from decimal into Fibonacci base.
        String str = "";
        for (int i = (FIBO_MAX - 1); i >= 0; i--) { // Pick from larger number to smaller number.
            if ((num - fibo[i]) > -1) { // Pickable
                str += "1";
                num -= fibo[i];
            } else {
                str += "0";
            }
        }

        // Delete the leading '0'
        String res = "";
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                res = str.substring(i, str.length());
                break;
            }
        }
        return res;
    }
}