给斐波那契函数加个缓存

算兔子：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

import java.util.HashMap;

public class a{
    private static HashMap<Integer,Double> map = new HashMap<Integer,Double>();
    
	public static double f(int month){
		//System.out.println("month:"+month+ "   0");
		if (month < 3){
		//	System.out.println("1");
			return 2;
		}
		if ( map.get(month-1) == null){
			//System.out.println("month："+(month-1));
			map.put(new Integer(month-1), f(month-1));
		}
		if ( map.get(month-2) == null){
			//System.out.println("month："+(month-2));
			map.put(new Integer(month-2), f(month-2));
		}
		
		
		double p = map.get(new Integer(month-1)).doubleValue()+map.get(new Integer((month-2))).doubleValue();
		//System.out.println("month : "+month+" p:"+p+"  2");
		return p;
	}
	
	
	public static long ff(long month){
	//	System.out.println("month:"+month+ "   0");
		if (month < 3){
		//	System.out.println("1");
			return 2;
		}
		
		long p = ff(month-1)+ff(month-2);
		//System.out.println("month : "+month+" p:"+p+"  2");
		return p;
	}
	public static void main(String args[]){
		
		System.out.println(""+"  "+f(700));
		
	}
	

}

评论

3 楼 darren_nizna 2010-03-11  

lenozhi 写道

darren_nizna 写道

斐波那契数列的求法更好的方法是用矩阵快速乘法
F[n]= F[n-1]+ F[n-2]
可以构造矩阵：
(F[n], F[n-1])= ( F[n-1], F[n-2] )* ( 1 1 )
                                      1 0
得到 F[n]= ( F[1], F[0] )* ( 1 1 )^ (n- 1)
                            1 0

速度能提升多少倍？

递推方法是 O(n)，用矩阵可以 log(n)
http://dngc.iteye.com/blog/612817

2 楼 lenozhi 2010-03-11  

darren_nizna 写道

斐波那契数列的求法更好的方法是用矩阵快速乘法
F[n]= F[n-1]+ F[n-2]
可以构造矩阵：
(F[n], F[n-1])= ( F[n-1], F[n-2] )* ( 1 1 )
                                      1 0
得到 F[n]= ( F[1], F[0] )* ( 1 1 )^ (n- 1)
                            1 0

速度能提升多少倍？

1 楼 darren_nizna 2010-03-10  

斐波那契数列的求法更好的方法是用矩阵快速乘法
F[n]= F[n-1]+ F[n-2]
可以构造矩阵：
(F[n], F[n-1])= ( F[n-1], F[n-2] )* ( 1 1 )
                                      1 0
得到 F[n]= ( F[1], F[0] )* ( 1 1 )^ (n- 1)
                            1 0