|
# 1. 楼梯有n个台阶，上楼可以一步上1阶，也可以一步上2阶，也可以一步上3阶，一共有多少种上楼的方法？
# 给个分析的例子：
# 有一个6级的台阶，一个人可走一步也可走两步也可走三步，问这个人有多少种方法走完这个台阶？
# 解：
# ①只用一步走：1+1+1+1+1+1=6，共6步，只有1种走法。
# ②用了一次两步走：1+1+1+1+2=6，共5步，有C5,1 =5种走法。
# ③用了两次两步走：1+1+2+2=6，共4步，有C4,2 =6种走法。
# ④用了三次两步走：2+2+2=6，共3步，有1种走法。
# ⑤用了一次三步走：1+1+1+3=11，共4步，有C4,1=4种走法。
# ⑥用了两次三步走：3+3=6，共2步，有1种走法。
# ⑥用了一次两步和一次三步走：有6种走法。
# 总共有1+5+6+1+4+1+6=24种
# 理论上分析：只有一个台阶的话，只有1种走法，
# 2级台阶的话，可以一步一个台阶走，也可以一步2个台阶走，共有2种走法。
# 3级台阶的话，可以一步一个台阶走，也可以一步3个台阶走，共有4种走法。
# 当台阶数大于等于4之后，可以这么分析：如果最后一步走一个台阶，那么就是n-1个台阶的走法的种类，如果最后一步走两个台阶，那么就是n-2个台阶的走法的种类，如果最后一步走三个台阶，那么就是n-3个台阶的走法的种类，所以n个台阶的走法种类就是n-1个台阶和n-2个台阶和n-3个台阶的走法的总和。因此，这是一个递归函数。
def step(n):
if n == 1:
return 1
if n == 2:
return 2
if n == 3:
return 4
else:
return step(n-1)+step(n-2)+step(n-3)
print(step(6))
|