爬楼梯问题
2018-06-05 19:19:44 小德 算法 访问次数 517

题目:

     有个人想上一个50层的台阶,但他一次只能迈一层或两层台阶,问:这个人有多少种方法可以把台阶走完?

     分析:先列举几个实例:1代表迈一层,2代表迈2

一层:1

二层:11  2

三层:111 12 21

四层:1111 121 211 112 22

五层:11111 2111 1211 1121 1112 221 212 122 

我们可以看到从第三层开始的走法等于上两层的走法之和,这个符合斐波纳契数列(斐波纳契数列指数列的第一项和第二项已知,那么后面的项等于前面两项的和,比如,第四

=第三项+第二项)。我们可以这样理解,当我们走到50层的时候,最后他有两种到达50层的途径:

1. 从49层走一层,

2. 从48层走两层,

那么,到达50层所有的走法就等于到达49层的走法+到达48层的走法,依次类推,可以得到总的走法符合斐波纳契数列,知道了这,我们的代码也就好写了。

代码实现:

斐波拉契数列非递归实现:

<?php
 function f($n)
 {
    $a1 = 1;
    $a2 = 2;
    if($n == 1) {
        return $a1;
    }elseif ($n == 2) {
        return $a2;
    }else {
        for($i=3;$i<=n;$i++) {
        $count = $a1 + $a2;
        $a1 = $a2;
        $a2 = $count;
        }
        return $count;
    }
    
 }
 echo f(50);