9 其它算法

1 青蛙跳台阶

1.1 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法？

算法思想 当 n = 1，只有 1 中跳法；当 n = 2 时，有 2 种跳法；当 n = 3 时，有 3 种跳法；当 n = 4 时，有 5 种跳法；当 n = 5 时，有 8 种跳法；.......规律类似于 Fibonacci 数列：

1 public static int fib(int n)
2 {
3     if(n <= 2)
4         return n;
5     return fib(n - 1) + fib(n - 2);
6 }

递归代码

我们对递归代码进行优化，因为递归代码中有太多的重复运算。所以，我们考虑使用变量保存住中间结果。

 1 public static int floor(int n)
 2 {
 3     if(n <= 2)
 4         return n;
 5     int n1 = 1;
 6     int n2 = 2;
 7     int sum = 0;
 8     for(int i = 3; i <= n; i++)
 9     {
10         sum = n1 + n2;
11         n1 = n2;
12         n2 = sum;
13     }
14     return sum;
15 }

算法描述

1.2 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

在第 n - 1 级一步跳到n级，有f(n-1)种；
在第 n - 2 级一步跳到n级，有f(n-2)种；
在第 n - 3 级一步跳到n级，有f(n-3)种；
。。。。。。
在第 1 级一步跳到n级，有f(1)种；
f(n)=f(n-1)+f(n-2)+f(n-3)+···+f(1)
f(n-1)=f(n-2)+f(n-3)+···+f(1)
推出f(n)=2*f(n-1)

 1 public static int floor(int n)
 2 {
 3     if(n <= 2)
 4         return n;
 5     int n = 2;
 6     int sum = 0;
 7     for(int i = 3; i <= n; i++)
 8     {
 9         sum = 2 * n;
10         n = sum;
11     }
12     return sum;
13 }

算法描述