[Java] UVa 11089 Fi-binary Number

題目連結

題意:
Fi-binary number
是指沒有相鄰 1 的二進位數字
由小到大前 10 個為
1, 10, 100, 101, 1000
1001, 1010, 10000, 10001, 10010

給定一個數字 N
輸出第 N 個 Fi-binary number

解法:
這題的關鍵是費氏數列
題目要求的
恰好是 N 的費氏進制

關於費氏位數
第一位為 1
第二位為 2
第三位為 3
第四位為 5
第五位為 8
...

如:
10 = 8 + 2 = 10010 (fib)
20 = 13 + 5 + 2 = 101010 (fib)

費氏進制分解的做法
可以參考
UVa 948 Fibonaccimal Base

找到最高位元後，往下判斷
fib(i) >= N就補 1，否則補 0

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int fib[] = new int[46];
	int index = 2;
	fib[0] = 1;
	fib[1] = 2;
	for (; index < 45; index++)
	fib[index] = fib[index-1] + fib[index-2];
	int T = sc.nextInt();
	while (T-- > 0) {
	int n = sc.nextInt();
	StringBuffer sb = new StringBuffer("");
	index = 44;
	while (fib[index] > n)
	index--;
	while (index >= 0) {
	if (n >= fib[index]) {
	sb.append("1");
	n -= fib[index];
	}
	else
	sb.append("0");
	index--;
	}
	System.out.println(sb.toString());
	}
	}
	}

view raw UVa11089.java hosted with ❤ by GitHub