`
bo_hai
  • 浏览: 564551 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

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

 
阅读更多

一、先要回答一个问题:什么是婓波那契数列?答案在这里: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;
    }

 

 

4
1
分享到:
评论
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) ;

相关推荐

    Fibonacci数列斐波那契数列PPT学习教案.pptx

    "Fibonacci数列斐波那契数列PPT学习教案.pptx" Fibonacci数列是一种非常重要的数学概念,它的应用非常广泛,包括生物学、经济学、计算机科学等领域。下面我们将详细介绍Fibonacci数列的概念、性质和应用。 1. ...

    java实现Fibonacci数列

    通过上述代码示例,我们不仅实现了Fibonacci数列的基本功能,还对比了递归和迭代两种不同的实现方式。递归方法虽然简单易懂,但在实际应用中往往因为效率问题而不被推荐使用。相比之下,迭代方法则更加高效,尤其是...

    Fibonacci_VERILOGfibonacci_实现斐波拉切数列_

    斐波那契数列是一种经典的数学序列,定义如下:序列中的第一个数字是0,第二个数字是1,之后的每一个数字都是前两个数字之和。斐波那契数列的前几个数字是0, 1, 1, 2, 3, 5, 8, 13...。在计算机科学中,特别是硬件...

    汇编语言,计算斐波那契数列的前22项,斐波那契数列,分别用两种方法:递归调用,普通循环加法

    在给定的压缩包中,有两个文件:`08LXY_8_2.asm`和`08LXY_8_1.asm`,分别对应这两种实现方式。我们可以打开这些文件,研究它们的代码结构,了解如何在实际汇编程序中实现递归和循环加法。例如,`08LXY_8_1.asm`很...

    斐波那契数列(前100项).rar

    - **递归方法**:递归是最直观的实现方式,但效率较低,因为它会重复计算很多次相同的值。例如,用C语言编写递归函数可以这样表示: ```c int fibonacci(int n) { if (n ) return n; else return (fibonacci...

    递归方法实现斐波那契数列_递归方法实现斐波那契数列_python_源码

    递归方法是实现斐波那契数列的一种常见方式。在编程中,递归是指函数调用自身来解决问题的方法。在这个场景下,我们可以编写一个函数,它会根据斐波那契数列的定义来计算第n项的值。 Python中递归实现斐波那契数列...

    (新课标)2020年高考数学 题型全归纳 斐波那契数列.doc

    同样,走楼梯问题也可以用斐波那契数列解决,每步可以走一级或两级,计算走n级楼梯的不同方式数,与斐波那契数列的计算方式相似。 此外,斐波那契数列还与黄金矩形、黄金螺旋、黄金角等几何形状紧密关联。这些形状...

    利用Matlab程序计算斐波那契数列的前一百项

    以下是一种可能的实现方式: ```matlab % 初始化斐波那契数列的前两项 fibonacci = [1, 2]; % 循环计算剩余的斐波那契数列项 for k = 3:100 % 将当前项设置为前两项之和 fibonacci(k) = fibonacci(k-1) + ...

    mips汇编语言实现斐波那契数列的排列

    2. 斐波那契数列的概念:斐波那契数列是一个数学概念,指的是一个无限的整数序列,每个数字都是前两个数字的和,通常用来描述生物体的生长模式和自然界中的自相似现象。本资源使用斐波那契数列作为示例,展示了...

    Fibonacci(斐波那契)数列的JAVA解法

    输出Fibonacci数列是一种使用循环来输出斐波那契数列的方法。该方法的思想是使用循环来输出斐波那契数列的每个数字。下面是一个输出Fibonacci数列的JAVA代码: public class Fib{ public static void main(String ...

    python 斐波那契数列 三种方法实现

    Python 斐波那契数列三种方法实现 Python 斐波那契数列是一种常见的数列,定义如下:第一个数是 0,第二个数是 1,接下来的数是前两个数的和。该数列有多种实现方法,下面将介绍三种常见的方法:循环方法、递归方法...

    斐波那契数列.pdf

    斐波那契数列(Fibonacci sequence)是数学中一个非常著名的数列,其特点是每一项数值都是前两项数值的和。通常情况下,斐波那契数列的第一项为0或1,第二项也为1,后续各项则根据定义递推得到。 **基本形式:** \...

    两种方法计算斐波那契数列

    本文档提供了两种计算斐波那契的C++代码函数,供网友使用,。主要讲cpp添加到新建项目中运行

    斐波那契数列毕业设计论文斐波那契数列的应用本科论文.doc

    黄金分割是一种数学概念,它是指一条线段被分割成两部分,使得长的部分与短的部分之比等于长的部分与整个线段之比。在图形设计、建筑设计、艺术设计等领域中,黄金分割都是非常重要的概念,它可以使设计更加美观和...

    Fibonacci数列(非递归的函数调用)

    在编程中,特别是C++中,有多种方法可以实现计算斐波那契数列的第n项。非递归的函数调用方式通常比递归更有效率,因为它避免了重复计算和堆栈调用的开销。以下是一种使用循环的非递归方法: ```cpp #include using...

    斐波那契数列及其性质

    爬楼梯问题,一个人爬楼梯可以选择一步一阶或一步两阶,求解不同爬楼方式的数量同样可以用斐波那契数列的加法规则来解决。0-1序列问题,寻找特定条件下的0-1序列数量,也可以通过斐波那契数列的构造性证明得到解答。...

    斐波那契数列c++.pdf

    3. **自然科学**:斐波那契数列能够描述某些生物生长繁殖的过程,如松果、向日葵种子排列等现象,这些排列方式遵循斐波那契数列的规律。 4. **美学与艺术**:斐波那契螺旋曲线被应用于绘画、设计等领域,为作品...

    算法-数论- 斐波那契数列(Fibonacci).rar

    - 在数据结构中,斐波那契堆是一种高效的优先队列实现。 - 在编码理论中,斐波那契数列出现在某些编码算法中,如Fibonacci编码。 - 在图形学中,斐波那契螺旋被用于创建自然和有机形状的模拟。 8. **数论上的...

    Fibonacci数列三种求和方式

    递归是最直观的方式来表示斐波那契数列,但也是效率最低的方法。递归函数通常定义为: ```python def fib_recursive(n): if n return n else: return fib_recursive(n-1) + fib_recursive(n-2) ``` 求和可以...

Global site tag (gtag.js) - Google Analytics