andy6804tw
5/3/2017 - 12:44 PM

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=889 這題簡單來說10 費事數列: 1 2 3 5 8

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=889

這題簡單來說10 費事數列: 1 2 3 5 8 0 1 0 0 1 Ans:10010 題目有說過最大值為100000000所以建立該區間的費事數列

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scn=new Scanner(System.in);
		ArrayList<Integer>fabList=new ArrayList<Integer>();
		fabList.add(1);fabList.add(2);
		int f=3;
		while(f<=100000000){
			fabList.add(f);
			int i=fabList.size();
			f=fabList.get(i-2)+fabList.get(i-1);
		}
		int n=scn.nextInt();
		while(n--!=0){
			int num=scn.nextInt(),lab=0,tot=0;
			String ans="";
			for(int i=fabList.size()-1;i>=0;i--){
				if(fabList.get(i)<=num){
					lab=i;
					break;
				}
			}
			for(int i=lab;i>=0;i--){
				if(tot+fabList.get(i)>num){
					ans+="0";
				}else{
					tot+=fabList.get(i);
					ans+="1";
				}
			}
			System.out.printf("%d = %s (fib)\n",num,ans);
		}
	}
	/*題目:948 - Fibonaccimal Base
    作者:1010
    時間:西元 2017 年 5 月 */
}