爬楼梯问题

c/c++

浏览数:533

2019-11-2

AD:资源代下载服务

       最近看到很有意思的一道题目,问的是☞有一座高度10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。例如,每次走1级台阶,一共走10步,这是其中一种走法;或者每次垮两级台阶,一共走5步;and so on.问一共有多少种走法。

      当楼梯级数很小时,凭借我们大脑弱小的计算能力,可以很快的得出答案。例如台阶数为1时,当然只有一种方法;台阶数为二时,有两种方法(11或2);台阶数为三时,有三种方法(111,12,21)。再随着台阶数的增长,我们会惊奇的发现☞天呐!我的脑子越来越不够用了?!

       这时就需要我们借助人类的好朋友好伙伴~~>计算机,帮我们解答。但问题来了,我们该怎么告诉它我们的需求呢?相信很多小伙伴一定想说,”反正电脑算的快,我们利用排列组合的思想,告诉它用多层嵌套循环遍历出所有可能!”Bingo,这样是可行的!!!但是请不要虐待电脑,因为它们是我们的好朋友好伙伴!!

        今天小编就要和大家balabala怎么样利用函数重入(递归)来化腐朽为神奇!

       小编有一个习惯,就是看一本书的时候如果发现从前往后不爽的时候,会换个姿势从后往前!这样换个姿势再来一遍,会发现不一样的风景!!!就拿这个问题来说,如果台阶有20级,如果从前往后干,你慢慢从垮一级或两级,再垮一级或两级直至跨到20级,相信你可怜的脑子是算不过来的。但假如我们设想现在到了最后一步(到了第18级台阶,再跨2级到就到第20级台阶了;或到了19级再跨1级到20级),那么,到达20级台阶的方法数Mehod(20)是不是就等于Method(19)+Method(18)?好,如果答案是肯定的,那么我们可不可以归纳出Method(N)=Method(N-1)+Method(N-2)这就是我们得出的状态转移关系!

        如果要想这个递归结束,我们还需要一个状态结束条件(边界条件)。这个简单☞Method(1)=1;Method(2)=2

    万事具备,只欠东风!东风就是用编程语言告诉计算机,它该怎么做。请看小编用C语言怎么和它说的

codes of steps

注:更多有趣问题,请关注leon_Geo
more funning questions,please locate “leon_Geo”

作者:Leon_Geo