[Day4]Fibonaccimal Base

今天一样来讲解一星的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加成字串即可以完成，题目要求的答案不管是数字还是字串，只要答案一模一样就可以了。
这题算是数学里比较常会看到的题目，就算没写过这题，多少也会有看过或是听过费氏数列，这题也算是比较常见的题目之一。
今天就讲解到这里。