首页 > Python基础教程 >
-
递归和循环:跳台阶和变态跳台阶和矩形覆盖
题目描述
跳台阶:一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
变态跳台阶:一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
矩形覆盖:我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解题思路
看到这样的题，基本上都是一脸蒙蔽，但是其实这样的题，一般都是有规律的，没有规律，那还怎么计算，这个时候学的数学就有用了，找规律。
跳台阶：
1级台阶：1，共1种，
2级台阶：2,11 共2种
3级台阶：12,21,111 共3种
4级台阶：22,211,121,112,1111 共5种
5级台阶：221,212,122,2111,1211,1121,1112,11111共8种
.....看出来规律了fn=f(n-1)+f(n-2)
变态跳台阶：
1级台阶：1，共1种，
2级台阶：2,11 共2种
3级台阶：3,21,12,1111 共4种
4级台阶：4,31,13,22,211,121,112,1111 共8种
5级台阶：5,41,14,32,23,311,131,113,221,212,122,2111,1211,1121,1112,11111共16种
.....看出来规律了fn=2f(n-1)
矩形覆盖：
1的矩阵：1，共1种
2的矩阵4平：2*2,1111，共2种
3的矩阵9平：2*2 + 2*2 + 1, 2*2 + 1*5, 1*9共3种
4的矩阵16平：2*2*4, 2*2*3+1*2, 2*2*1+1*4(2种，2挨着和不挨着), 1*16共5种
.......规律了fn=f(n-1)+f(n-2),可以看出和跳台阶一样
代码实现
/// <summary>
/// 循环跳台阶
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static int Jump(int n) {
if (n <= 2) {
return n;
}
int first = 1;
int second = 2;
int result = 0;
for (int i = 3; i <= n; i++) {
result = first + second;
first = second;
second = result;
}
return result;
}
/// <summary>
/// 变态跳台阶
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static int Jump(int n) {
if (n <= 1) {
return n;
}
int first = 1;
int result = 0;
for (int i = 2; i <= n; i++) {
result = 2 * first;
first = result;
}
return result;
}
想入非非：扩展思维，发挥想象
1. 数学不要忘，学会找规律
2. 不要动不动就用递归
