斐波那契数列——台阶问题实现

旧城等待， 2021-11-24 01:06 221阅读 0赞

问题：有个n阶台阶，一次可以走一个台阶，也可以走两个台阶，走到n阶台阶有多少种走法。

分析：遇到这种问题我们很容易想到递归的方法，但是这些数据的之间的关系还需要我们找到一个通项公式。可以采用归纳总结方法找出规律，不难发现这里的规律是a(n)=a(n-1)+a(n-2),算法的背后都有数学理论支撑，所以这里的数学理论就是斐波那契数列。斐波那契数列（

sequence），又称[黄金分割][Link 1]数列、因[数学家][Link 2]列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“[兔子数列][Link 3]”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以[递推][Link 4]的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N\*）

下面介绍两种斐波那契的代码实现：递归和循环

通过递归实现：

private static int func2(int i) {
    	// TODO Auto-generated method stub
    	if(i == 1) {
    		return 1;
    	}
    	if(i == 2) {
    		return 2;
    	}
    	int res = func2(i-1) + func2(i-2);
    	return res;
    }

通过循环实现：

private static int func(int i) {
    	// TODO Auto-generated method stub
    	int a=1,b=2;
    	if(i == 1) {
    		return a;
    	}
    	if(i == 2) {
    		return b;
    	}
    	for (int j = 3; j <= i; j++) {
    		b = a+b;
    		a = b-a;
    	}
    	return b;
    }

总结：

算法是程序员的必备技能，有简单的，有复杂的，我们可以不创建算法，不去推导算法的实现过程，但是一定要通过代码实现算法，这样才能提高自身的技能素养。

[Link 1]: https://baike.baidu.com/item/%E9%BB%84%E9%87%91%E5%88%86%E5%89%B2/115896
[Link 2]: https://baike.baidu.com/item/%E6%95%B0%E5%AD%A6%E5%AE%B6/1210991
[Link 3]: https://baike.baidu.com/item/%E5%85%94%E5%AD%90%E6%95%B0%E5%88%97/6849441
[Link 4]: https://baike.baidu.com/item/%E9%80%92%E6%8E%A8/1740695