斐波那契数列 的两种实现方式

一、先要回答一个问题：什么是婓波那契数列？答案在这里：http://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97

二、看代码：

1）第一方法：递归实现：

public static void main(String[] args) {
	for (int i = 0; i <= 10; i++) {
		System.out.print(fibonacci(i));
		System.out.print('\t');
	}
}

public static int fibonacci(int i) {
	if (i == 0) {
		return 0;
	} else if (i == 1) {
		return 1;
	}
	return fibonacci(i - 2) + fibonacci(i - 1) ;
}

 2）第二种方法：循环实现：

public static void main(String[] args) {
	
	int[] arr = {0,0};
	for (int i = 0; i <= 10; i++) {
		int result = 0;
		if (i == 0) {
			arr[0] = 0;
			result = 0;
		} else if (i == 1){
			arr[1] = 1;
			result = 1;
		} else {
			result = arr[0] + arr[1];
			arr[0] = arr[1];
			arr[1] = result;
		}
		System.out.print(result);
		System.out.print('\t');
	}
}

 大家还有更好的实现方法吗？

再更新一种实现方式：面试时，要求输入一个数n，打印出婓波那契数列第n个数的值，要求空间复杂度是：O(1)，时间复杂复没有限制。代码如下：

    private static long sampleFib(long n) {
        long min = 0 ,max = 1,result = 0;
        if (n <= 1) {
            result = min;
        } else if (n == 2) {
            result = max;
        } else {
            for (int i = 3; i <= n; i++) {
                result = min + max;
                min = max;
                max = result;
            }
        }
        return result;
    }

 

 

评论

7 楼 bo_hai 2013-12-29  

循环实现的代码也可以进行优化：

public static void main(String[] args) {
	int[] arr = {0,0};
	for (int i = 0; i <= 10; i++) {
		int result = 0;
		if (i <= 1) {
			arr[i] = i;
			result = i;
		} else {
			result = arr[0] + arr[1];
			arr[0] = arr[1];
			arr[1] = result;
		}
		System.out.print(result);
		System.out.print('\t');
	}
}

6 楼 bo_hai 2013-12-29  

使用递归实现的方法可以优化，优化后代码如下：

public static int fibonacci(int i) {
	if (i <= 1) {
		return i;
	}
	return fibonacci(i - 2) + fibonacci(i - 1) ;
}

5 楼 hailongshih 2013-12-24  

Good,support

4 楼 bo_hai 2013-12-24  

skillful 写道

showArr(i - 2) + showArr(i - 1) ;估计是笔误，不过也说明了LZ的代码只是写出来的，并没有编译与运行过！

编译与运行时， 方法名是：showArr。发布blog时，发现这个方法名不对，只修改了方法名。抱歉。谢谢指正。一并感谢一楼的同仁。

3 楼 skillful 2013-12-24  

showArr(i - 2) + showArr(i - 1) ;估计是笔误，不过也说明了LZ的代码只是写出来的，并没有编译与运行过！

2 楼 bo_hai 2013-12-24  

Mr_WangB 写道

showArr(i - 2) + showArr(i - 1) ;

你这是想说啥呢？

1 楼 Mr_WangB 2013-12-23  

showArr(i - 2) + showArr(i - 1) ;