一、提出背景
一只青蛙一次最少可以跳 1层 台阶，一次最多可以跳 2层 台阶，求：该青蛙跳上n 层 的台阶总共有多少种跳法？
二、分析问题
如上图分析：
一层台阶：1种跳法
两层台阶：2种跳法
三层台阶：3种跳法
四层台阶：5种跳法
…
那么我们可以列一个数列：
1 2 3 5 8 13 21 34…
对这些数字是不是很熟悉？没错，问题其实就是隐含了斐波那契数列的思想
三、搜寻规律
- F(1) = 1，F(2) = 2
- 当 n >= 3 时， F(n) = F(n - 1) + F(n - 2)
程序清单1（递归法）：
public class Test1 { public static void main(String[] args) { int n = 10; for (int i = 1; i <= n; i++) { System.out.println(fib(i)); } } public static int fib(int n){ if(n==1 || n==2){ return n; } else{ return fib(n-1)+ fib(n-2); } } } //输出 1 2 3 5 8 13 21 34 55 89
程序清单2（迭代法）：
public class Test2 { public static void main(String[] args) { int n = 10; fib(n); } public static void fib(int n){ int a = 1; int b = 2; for (int i = 1; i <= n; i++) { if (i == 1 || i == 2) { System.out.println(i); } else { int c = a + b; a = b; b = c; System.out.println(c); } } } } //输出 1 2 3 5 8 13 21 34 55 89
迭代法分析：
总结
- 经典问题都是有其对应的规律的，通过画图实验一次，两次，三次…找到规律，就能得出结果，不必深挖，否则会陷入问题本身的死循环
- 下一篇博客，十七为大家分享汉诺塔的问题
Over. 谢谢观看哟~
