n步能到达顶端。每次可以爬一步或两步，有多少方法？

PGC123

2018-10-23 阅读量: 960

python编程你正在爬楼梯的情况。需要n个步骤才能到达顶端。每次你可以爬上1或2步。有多少种不同的方法可以爬到顶端？完全没思路，这个要怎么做？

首先可以假设有y种爬到顶端的方法，则 y与n之间存在一种函数映射 y = f(n)

已知

当 n = 1 则 y = 1

当 n = 2 则 y = 2

当 n>2时第一步骤可以是走一步或者两步。

当第一步骤走一步时有f(n-1)中方法

当第一步骤走两步时有f(n-2)中方法

则f(n)应当是f(n-1) 与 f(n-2)的和

既

当 n >2 则 y = f(n-1) + f(n-2)

这个题目考察的是对递归函数的熟悉程度，递归函数的优点是逻辑复杂的问题简单化，代码简练。实现代码如下

def y(n):
  if n == 1:
      return 1
  elif n == 2:
      return 2
  else:
    return y(n-1)+y(n-2)

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数，递归还要有停止条件是要收敛的。递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

0.0000

关注作者

发表评论

暂无数据

CDA考试动态

CDA报考指南

推荐帖子