[Java] UVa 948 Fibonaccimal Base

題目連結

題意:
已知費氏數列:
fib(1) = 1
fib(2) = 2
fib(3) = fib(1) + fib(2) = 3
fib(4) = fib(2) + fib(3) = 5
...

給定數字 N
分解成費氏數列的組成(費氏進制)
如: 17 = 13 + 3 + 1
寫成 100101 (13,8,5,3,2,1)

解法:
注意輸出是由高位元到低位元
先求出範圍內最大的費氏
此處 N 可以到 1 億，大概是 fib(43)

然後從最大的判斷回來
若 fib(i) <= N，就是最高位元的 1

令 N = N - fib(i) 後繼續做
fib(i) <= N 補 1
fib(i) > N要補 0

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int times = sc.nextInt();
	int A = 0;
	//建費氏數列表
	int arr[] = new int[50];
	arr[0] = 1;
	arr[1] = 2;
	for (int i = 2; i < 43; i++)
	arr[i] = arr[i - 1] + arr[i - 2];
	while (times-- > 0) {
	A = sc.nextInt();
	StringBuilder sb = new StringBuilder(A + " = ");
	int i = 42;
	while (A < arr[i])
	i--;
	while (i >= 0) {
	if (A >= arr[i]) {
	A -= arr[i];
	sb.append("1");
	}
	else
	sb.append("0");
	i--;
	}
	sb.append(" (fib)");
	System.out.println(sb.toString());
	}
	}
	}

view raw UVa948.java hosted with ❤ by GitHub