当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

求第n个斐波那契数

发表于: 2014-06-19   作者:BrokenDreams   来源:转载   浏览:
摘要:         今天看到群友发的一个问题:写一个小程序打印第n个斐波那契数。         自己试了下,搞了好久。。。基础要加强了。           &nbs
        今天看到群友发的一个问题:写一个小程序打印第n个斐波那契数。
        自己试了下,搞了好久。。。基础要加强了。
       
        进入正题,什么是斐波那契数列就不说了,拿到这个题目,直接写出如下代码:
public static long findFibonacci(int n){
		if(n <= 2){
			return 1;
		}else{
			return findFibonacci(n - 1) + findFibonacci(n - 2);
		}
	}

        运行一下,输入n分别为:1,2,3,4,5 输出分别为1,1,2,3,5。貌似是正确的,看看有什么问题,如果我们输入n为45。
public static void main(String[] args) {
		long s = System.currentTimeMillis();
		System.out.println(findFibonacci(45));
		long e = System.currentTimeMillis();
		System.out.println("程序运行耗时["+(e-s)+"]毫秒!");
	}

        输出如下:
1134903170
程序运行耗时[4875]毫秒!

        如果输入100的话,就一直在运行。。。。。
        上面程序的问题在于,计算第n个f数时需要计算第n-1和第n-2个f数,但是计算第n+1个f数的时候又要重新计算第n个f数,如此反复,要处理的子问题的数量爆炸式增长。我们加点输出看看。
public static long findFibonacci(int n){
		if(n <= 2){
			System.out.println("计算第["+n+"]个斐波那契数[1]");
			return 1;
		}else{
			long fb = findFibonacci(n - 1) + findFibonacci(n - 2);
			System.out.println("计算第["+n+"]个斐波那契数["+fb+"]");
			return fb;
		}
	}

        n输入为5,输出如下:
计算第[2]个斐波那契数[1]
计算第[1]个斐波那契数[1]
计算第[3]个斐波那契数[2]
计算第[2]个斐波那契数[1]
计算第[4]个斐波那契数[3]
计算第[2]个斐波那契数[1]
计算第[1]个斐波那契数[1]
计算第[3]个斐波那契数[2]
计算第[5]个斐波那契数[5]
5
程序运行耗时[0]毫秒!


        如何解决这个问题呢,如果我们能重复利用子问题的结果,而不是每次去重新求解子问题,这样程序就会快很多,这种处理问题的方式也叫做动态规划。
        针对这个问题,假设我们要求第n个斐波那契数,我们可以建立一个长度为n(为n-1就可以,但为了编码方便)的数组用来保存子问题结果,代码如下:
private static long findFibonacci1(int n, long[] c){
		int index = n - 1;
		if(c[index] != 0){
			return c[index];
		}
		if(n <= 2){
			c[index] = 1;
		}else{
			c[index] = findFibonacci1(n - 1,c) + findFibonacci1(n - 2,c);
		}
		return c[index];
	}
	
	public static long findFibonacci1(int n){
		long c[] = new long[n];
		return findFibonacci1(n,c);
	}

        这次输入45,看看结果:
1134903170
程序运行耗时[0]毫秒!


        这次没问题了。再想想,其实每次求第n个f数只需要重用第n-1和第n-2个f数就可以了,而且依据代码,问题的解决是自底向上的,所以每次保存2个就够了,我们先搞点日志看看。
private static long findFibonacci1(int n, long[] c){
		int index = n - 1;
		if(c[index] != 0){
			System.out.println("从数组下标["+index+"]中获取数据["+c[index]+"]");
			return c[index];
		}
		if(n <= 2){
			c[index] = 1;
		}else{
			c[index] = findFibonacci1(n - 1,c) + findFibonacci1(n - 2,c);
		}
		return c[index];
	}

        输入7,看输出:
从数组下标[1]中获取数据[1]
从数组下标[2]中获取数据[2]
从数组下标[3]中获取数据[3]
从数组下标[4]中获取数据[5]
13
程序运行耗时[0]毫秒!

        可以看到,会从小到大从数组中取数据。继续看看能不能每次只保存2个子问题结果。看代码:
private static long findFibonacci2(int n, long[] c){
		int index = n % 2;
		if(c[index] != 0){
			System.out.println("从数组下标["+index+"]中获取数据["+c[index]+"]");
			return c[index];
		}
		if(n <= 2){
			c[index] = 1;
		}else{
			c[index] = findFibonacci2(n - 1,c) + findFibonacci2(n - 2,c);
		}
		return c[index];
	}
	
	public static long findFibonacci2(int n){
		long c[] = new long[2];
		return findFibonacci2(n,c);
	}

        输出8,看看输出:
从数组下标[0]中获取数据[1]
从数组下标[1]中获取数据[2]
从数组下标[0]中获取数据[3]
从数组下标[1]中获取数据[5]
从数组下标[0]中获取数据[8]
21
程序运行耗时[0]毫秒!


        嗯,果然可以。去掉打印语句,输出1000,看看输出:
817770325994397771
程序运行耗时[0]毫秒!

        ok,嘎嘎。不过这道题直接用循环貌似更简单。。。。
        再来个更短的(无聊)
private static long f(int n, long[] a){
		return a[n & 1] == 0 ? (n <= 2 ? (a[n & 1] = 1)
				:(a[n & 1] = f(n - 1, a) + f(n - 2, a))) : a[n & 1];
	}
	
	public static long findNthFibonacci(int n){
		return f(n, new long[2]);
	}

求第n个斐波那契数

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
 众所周知斐波那契数在数学和计算机中有着广泛的应用 斐波那契数的原理是第一个数是 1,第二个
用递归的方式求斐波那契数列的第n个数。 用非递归的方式求斐波那契数列的第n个数。 定义: 斐波那契
问题描述:斐波那契数列是指如下数列: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).数列的前10个数如下: 0,
Problem Description A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A *
斐波那契数计算的方法一般采用递归的方法,返回类型一般采用int或者long类型。在这种条件下会产生两
这个学期开了一门叫算法的课,为了今天的ITAT复赛,这两天研究了一下这门课。感觉算法真的是太
骨牌铺方格 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) T
在计算机科学中,斐波那契堆是由树的集合所组成的堆数据结构。它比二项堆的平摊运行时间更好。斐波
斐波纳契堆(Fibonacci Heap)于 1984 年由 Michael L. Fredman 与 Robert E. Tarjan 提出,1987 年
斐波那契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号