今天一樣來講解一星的Fibonaccimal Base

附上程式碼
import static java.lang.System.*;
public class main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNextInt()){
int n=sc.nextInt();
if(n>500) break;
int N[]=new int[n];
int a=0, b, c=0;
String B="";
int X[]=new int[41];
int Y[]=new int[45];
X[0]=0;
X[1]=1;
X[2]=1;

	for(int i=3;i<41;i++){
		X[i]=X[i-1]+X[i-2];
	}
	
	for(int i=0;i<n;i++){
		b=sc.nextInt();
		c=b;
		if(b>100000000) break;
		for(int x=39;x>0;x--){
			if(b>=X[x]){
				b=b-X[x];
				Y[x]=1;
			}else if(b==0) break;
		}
		for(int x=0;x<40;x++)
			if(Y[x]==1) a=x;
		
		for(int x=2;x<a+1;x++)
			B=""+Y[x]+B;
		
		System.out.println(c+" = "+B+" (fib)");
		for(int x=0;x<41;x++)
			Y[x]=0;
			
		B="";
	}
}

}
};

題目要求範圍在500個內 ，給定數字 N(b N不會超過1億 大概是fib(41)，分解成費氏數列的組成(費氏進制)，
EX: 17 = 13 + 3 + 1
=100101 (13,8,5,3,2,1)、
6的話就是1001(5,3,2,1)，使用二進制來表示費氏數列，所以首先要先建立費氏數列(X[]，接下來從最大的費氏數列(X[]開始往下找可以減的就給Y[]+1，使Y[]裡面的值等於1(等於1的就代表二進制的1)並讓a等於Y陣列裡面值是1的最後一個1的位置，最後一定分解出費氏數列的組成，之後只需要把迴圈把Y[]裡面的0或1加成字串即可以完成，題目要求的答案不管是數字還是字串，只要答案一模一樣就可以了。
這題算是數學裡比較常會看到的題目，就算沒寫過這題，多少也會有看過或是聽過費氏數列，這題也算是比較常見的題目之一。
今天就講解到這裡。