David Aaronson
0%

青蛙跳台阶

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

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

思路

假设第一次跳了一阶，那么还剩 n-1 阶，有f(n-1)中跳法。 假设第一次跳了2阶，那么还剩 n-2 阶，有f(n-2)中跳法。所以，这是一个斐波那契数列。f(n) = f(n-1)+f(n-2)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * 
 * 思路：假设第一次跳了一阶，那么还剩 n-1 阶，有f(n-1)中跳法。
 * 
 * 假设第一次跳了2阶，那么还剩 n-2 阶，有f(n-2)中跳法。
 * 
 * 所以，这是一个斐波那契数列。f(n) = f(n-1)+f(n-2)
 * 
 * @author XIAO
 *
 */
public class JumpFloor {
	public int JumpFloorSolution(int target) {
		if (target == 0) {
			return 0;
		}
		if (target == 1) {
			return 1;
		}
		if (target == 2) {
			return 2;
		}
		int f1 = 1;
		int f2 = 2;
		int cursum = 0;
		for (int i = 3; i <= target; i++) {
			cursum = f1 + f2;
			f1 = f2;
			f2 = cursum;
		}
		return cursum;
	}
}

题目2

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

思路

  1. 假设第一次跳 1 阶。那么还剩 n-1 阶。一共还剩f(n-1)种跳法。
  2. 假设第一次跳 2 阶。那么还剩 n-2 阶。一共还剩f(n-2)种跳法。 。。。
  3. 假设第一次跳 n-1 阶。那么还剩 1 阶。一共还剩f(1)种跳法。
  4. 假设第一次跳 n 阶。一种跳法。
  5. 所以：f(n) = f(n-1)+f(n-2)+…+1; 而且:f(n-1) = f(n-2) +…+1;
  6. 所以f(n) = 2f(n-1)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * 
 * 思路：同样：假设第一次跳 1 阶。那么还剩 n-1 阶。一共还剩f(n-1)种跳法。
 * 
 * 假设第一次跳 2 阶。那么还剩 n-2 阶。一共还剩f(n-2)种跳法。 。。。
 * 
 * 假设第一次跳 n-1 阶。那么还剩 1 阶。一共还剩f(1)种跳法。
 * 
 * 假设第一次跳 n 阶。一种跳法。
 * 
 * 所以：f(n) = f(n-1)+f(n-2)+...+1; 而且:f(n-1) = f(n-2) +...+1;
 * 
 * 所以f(n) = 2f(n-1)
 * 
 * @author XIAO
 *
 */
public class JumoFloor2 {
	public int JumpFloorSolution(int target) {
		if (target <= 0) {
			return 0;
		}
		if (target == 1) {
			return 1;
		}
		return JumpFloorSolution(target - 1) * 2;
	}
}