题目
有个人想上一个50级的台阶,每次只能迈1级或者迈2级台阶,问:这个人有多少种方法可以把台阶走完?例如:总共3级台阶,可以先迈1级再迈2级,或者先迈2级再迈1级,或者迈3次1级总共3中方式。
心路历程
这个题目我刚看到的时候觉得很有意思,值得思考一下,也和同学讨论过思路,并没有直接去网上找答案,觉得那样的话就浪费了,所以自己先尝试着解了。
说这么多是希望大家也不要直接去看解答,因为看完之后一个星期也就忘了。可以先收藏一手,自己去试试然后再回来看,我会把我自己解的思路和正解都放在这篇文章里。
思路step1:
从初中生的思路来看,第一个能想到的方法肯定是一个二元方程,也就是x+2y=50,其中x代表迈1步,y代表迈2步,无论怎么迈总共50级台阶。
接下来的问题就是求这个方程解的数量(不是某一个解),x+2y-50=0这个方程的所有解应该是一条直线,所以我很单纯的去把图给画了,就像下面这个样子:
再考虑x和y都必须是整数才能符合题意,y取值在025之间,可以看出只要y是整数解那么x一定为整数解,0也可以作为一种特殊情况,综上y可能的取值是:025共26个。那么相对应的x取值也就可以算出来了。
这里还有一种情况,如果总台阶数不是50,那么y的取值范围有可能是0~24.5,那么我认为y只能取值到24,也就是向下取整。
思路step2:
如果仅从数量上来看,xy总共有26种组合的方式,但这肯定不是最后答案,例如,迈2次1步再迈24次2步和先迈24次2步再迈2次1步是两种不同的方式,那么接下来就是排列组合的问题。
所以,我们要求的是所有xy同为整数的解的排列之和,是不是感觉有点复杂了,但是没关系,前面说的内容都是用PHP可以实现的,排列组合也是可以用PHP实现的。然后,排列组合算法的第一个问题就是如何实现阶乘?
在PHP中range函数可以建立一个包含指定范围单元的数组,允许传入三个参数起始值、终止值和步长值,例如rang(1,3)会返回包含1、2、3这三个数的一个数组。
另外PHP中的array_product函数可以计算数组中所有值的乘积。
有了这两个函数我们就可以自己写出阶乘的函数了,虽然我不知道效率怎么样,但起码我们不用往递归的方面去想了,另外还需要考虑一下0和1阶乘的情况,就是下面这个样子:
有了阶乘,排列也就有了:
回到问题上来,我们需要用到组合吗?
首先,总数量是确定的x+y,而且第一次迈2步和后面无论第几次迈2步都是相同的,所以这种排列组合其实可以转化为“把鸡蛋放入篮子”的问题——将n个无差别的鸡蛋放入m个篮子中共有几种放法。那么求组合数函数也是需要的:
接下来就是循环每一个可能解,可以总是将x值作为鸡蛋的数量,将xy之和作为篮子的数量,也就是C(x+y,x),举个例子来说就是,总共要迈26次脚,选择其中2次只迈1步,有多少种迈法。
思路step3:
有了前面那么多的思考,我们来写代码:
经过测试,最终50级台阶的走法有20365011074种,二百零三亿六千五百零一万一千零七十四种(醉了)。
那么到这里我就开始去网络上找正确答案了,让我震惊了,发现我的思路果然是初中生的,且是从来不参加任何数学竞赛的那种,下面我分析一下网络上答案的思路。
答tu案cao
网上的解只有一种,那就是把这个问题归结为斐波那契数列的问题,完全看不出来好吗!
答案穷举了总台阶数从1级到5级的情况,得出结论1级共1种走法,2级2种走法,3级3中走法,4级5种走法,5级有八种走法,然后就开始研究斐波那契数列去了!
那你出个题目出个那么悬乎干嘛!直接让我们用PHP写个斐波那契函数不就好了吗!要考察思维能力也得给点提示啊!比如说设置两个问题:第一问,当台阶总数为5时有几种走法?第二问,当台阶总数为n时有几种走法?
总之呢就是在面试的时候,如果你见过这题那么恭喜你,如果没见过那么就可以去下一题了。
当然也有大神给出了比较让人信服的逻辑:
当我们走到第50层的时候,最后有两种选择,从49开始迈1级或者从48开始迈2级。那么到达50层的走法等于到达49层的走法+到达48层的走法,以此类推,可以得到总的走法符合斐波那契数列,我们的代码就好写了。
恩............膜拜奥数大神的思维。
PHP写斐波那契应该是比较简单的问题,那最后让我们用答案中的斐波那契函数来验证一下自己的答案。
可以看到,小编自己的思路和最终答案是相同的,只是过程相对复qing杂xi。
还是不太放心,测试了台阶总数从1~7的所有情况,也都是符合答案的,甚至我没有特殊考虑的只有1~2层的情况也能返回正确的答案。