当前位置:首页 » Project Euler » 详细页

Pandigital Fibonacci ends 题号:104 难度: 25 中英对照

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

It turns out that F541, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F2749, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

Solution

直接暴力: 用两个数组$f$和$g$来储存斐波那契数组的后$9$位和前$18$位。 实际计算时: 1. 对于后$9$位而言,直接相加取模即可(对$1000000000$取模)。 2. 对于前$18$位而言,当超过$18$位时进行除以%10%的操作,此时应注意下一次计算时会产生错位,需要补救,如下所示: 设第某个斐波那契数的前$18$位为$a$,后一个斐波那契数的前$18$位为$b$,满足$a+b$超过$18$位,则再后一个斐波那契数的前$18$位为$c$,$c=\frac{a+b}{10}$。 再往后计算一位,应当为$b$和$\frac{a+b}{10}$,此时它们表示的实际位数并不对齐,而差错了一位(因为除以了$10$),为了判别这一情况,考虑如下判断: $$a< b$$ $$\frac{a+b}{2}< b$$ $$5 \times \frac{a+b}{10} < b$$ $$5 \times c < b$$ 于是当上式成立时,说明前一次计算时出现了除法操作产生错位,应当正确的计算为: $$c+\frac{b}{10}$$

Code

import java.util.Arrays;

public final class p104 {
    
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
    
    public static String run() {
    	long f[]=new long[1000000];
    	long g[]=new long[1000000];
		f[0]=g[0]=0;
		f[1]=g[1]=1;
    	for(int i=2;i<1000000;i++){
    		f[i]=(f[i-1]+f[i-2])%1000000000;
    		if(g[i-1]*5<g[i-2])
    			g[i]=g[i-1]+g[i-2]/10;
    		else if(g[i-1]+g[i-2]>=1000000000000000000L)
    			g[i]=(g[i-1]+g[i-2])/10;
    		else
    			g[i]=g[i-1]+g[i-2];
    		String a=Long.toString(f[i]);
    		if(!check(a)) continue;
    		String b=Long.toString(g[i]).substring(0,9);
    		if(!check(b)) continue;
    		return Integer.toString(i);
    	}
    	return "NULL";
    } 
    static private boolean check(String a){
		if(a.length()!=9) return false;
		boolean flag[]=new boolean[9];
		for(int j=0;j<9;j++)flag[j]=false;
		for(int j=0;j<9;j++)
			if(a.charAt(j)=='0')
				return false;
			else if(flag[a.charAt(j)-'1'])
				return false;
			else
				flag[a.charAt(j)-'1']=true;
		return true;
    }
}
329468
85ms