台阶问题

发布于 | 分类： . .
字数统计

现在有这样的一个问题：

楼梯有n个台阶，上楼可以一步上1阶，也可以一步上2阶，一共有多少种上楼的方法？

假设一个有11级的台阶，一个人一次可以上一阶也可以上两阶，那这个人有多少种方式走完这11级台阶？

==下面的结果都是排列组合算出来的==

  1. 每次上一台阶，也就是1*11=11，共1中方案。
  2. 只有一次上两个台阶，也就是一共上十次台阶，在这十次中任选一次上两阶，这样做共10中方案。
  3. 有两次上两个台阶，一共上九次台阶，也就是在9次中任选两次上两阶，共36中方案
  4. 有三次上两个台阶，共56种方案。
  5. 有四次上两个台阶，共35种方案。
  6. 有五次上两个台阶，共6种方案。

所以共有144种方案

理论上分析：只有一个台阶的话，只有1种走法，2级台阶的话，可以一步一个台阶走，也可以一步2个台阶走，共有2种走法。

当台阶数大于等于3之后，可以这么分析：如果最后一步走一个台阶，那么就是n-1个台阶的走法的种类，如果最后一步走两个台阶，那么就是n-2个台阶的走法的种类，所以n个台阶的走法种类就是n-1个台阶和n-2个台阶的走法的总和。因此，这是一个递归函数。也是一个裴波那契函数。

C++版本的程序代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int fstep(int n)
{
 if(n==1)return 1;
 if(n==2)return 2;
 if(n>=3)return fstep(n-2)+fstep(n-1);
 return 0;
}
int main()
{
 int n,step;
 cout<<"input the steps of the stair:"<<endl;
 cin>>n;
 step=fstep(n);
 cout<<"The methods to finish the stair are: "<<step<<endl;
 return 0;
}

Python版本的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	def upstep(self, n):
		if n == 1:
			a = 1
		elif n == 2:
			a = 2
		else:
			a = self.upstep(n-1) + self.upstep(n-2)
		print(str(a))
sol = Solution()
sol.upstep(1)
sol.upstep(2)
sol.upstep(3)
sol.upstep(11)

这样写是有报错的，因为

1
2
3
4
5
6
7
8
9
10
11
root@peter-VirtualBox:/home/peter/Documents# python3 upstep.py 
1
2
2
1
Traceback (most recent call last):
  File "upstep.py", line 29, in <module>
    sol.upstep(3)
  File "upstep.py", line 23, in upstep
    a = self.upstep(n-1) + self.upstep(n-2)
TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

在函数体内部两次对自身的调用的结构都是无类型的，不知道该怎么解决

这样写就是可以成功运行的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def allMethods(stairs):
	if isinstance(stairs, int) and stairs > 0:
		basic_num = {1:1, 2:2}
		if stairs in basic_num.keys():
			return basic_num[stairs]
		else:
			return allMethods(stairs-1) + allMethods(stairs-2)
	else:
		print("The num is wrong")
		return False
print(str(allMethods(1)))
print(str(allMethods(2)))
print(str(allMethods(3)))
print(str(allMethods(11)))
print(str(allMethods(20)))

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
>>> def allMethods(n):
...     if isinstance(n,int) and n > 0:
...         basic_num = {1:1,2:2}
...         if n in basic_num.keys():
...             return basic_num[n]
...         else:
...             return allMethods(n-1) + allMethods(n-2)
...     else:
...         return False
... 
>>> allMethods(1)
1
>>> allMethods(2)
2
>>> allMethods(3)
3
>>> type(allMethods(1))
<class 'int'>
>>> type(allMethods(1)+allMethods(2))
<class 'int'>
>>> allMethods(11)
144
>>> allMethods(20)
10946
>>> allMethods(0)
False

但是这样在shell中尝试也是没问题的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
>>> def upstep(n):
...     if n == 1:
...         return 1
...     elif n == 2:
...         return 2
...     else:
...         return upstep(n-1) + upstep(n-2)
... 
>>> upstep(1)
1
>>> upstep(2)
2
>>> upstep(3)
3
>>> upstep(11)
144
>>> type(upstep(n-1))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'n' is not defined
>>> type(upstep(11))
<class 'int'>

下面是更加python风格的解决办法：

1
2
3
4
5
6
7
>>> fib = lambda n: n if n <= 2 else fib(n-1) + fib(n-2)
>>> fib(1)
1
>>> fib(2)
2
>>> fib(11)
144

接下来如果有n级台阶，我们可以一次上n个台阶（n = 1,2,3,4…n），那怎么处理呢？

1
2
3
4
5
6
7
8
9
10
11
>>> fib = lambda n: n if n <= 2 else 2*fib(n-1)
>>> fib(1)
1
>>> fib(2)
2
>>> fib(11)
1024
>>> fib(5)
16
>>> fib(10)
512