22
回答
腾讯面试题:50个阶梯,走上去,共有多少种走法
终于搞明白,存储TCO原来是这样算的>>>   
转自: http://club.it.sohu.com/r-it-1922843-0-0-900.html

有个同学去了腾讯,他说面试时有这么一道思维题:50个阶梯,你一次可以上一阶或两阶,走上去,共有多少种走法?

我的思路: 

我的思维比较直线简单:

1,求出走上次可能有的方式,这里的方式是指:共走多少个1步,多少个2步。比如说,你走了2个1步,其余走2步,要走24个2步,用对象存起来就是:{one:2,two:24}

2,每个方式的走法是可以通过排列组合公式算出来的。如下是排列组合公式:


 3,用到的公式是c(n,r)=n!/r!(n-r)!;这个比较好实现,无非就是阶乘除阶乘。

代码如下:

        (function() {
            var waysArr = []; //上台阶方式的,每一种方式为一个对象字面量,如[{one:2,two:24},{one:4,two:23}]
            var counts = []; //存每种方式排列组合数
            //生成waysArr
            for (var i = 25; i >= 0; i--) {
                var x = 50 - 2 * i;
                waysArr.push({ one: x, two: i });
            }
            //阶乘
            function factorial(num) {
                if (num <= 1) {
                    return 1;
                }
                else {
                    return num * arguments.callee(num - 1);
                }
            }

            //每种方式的排列数
            //参数是走1步的次数,走2步的次数
            function thisWayTimes(one, two) {
                //排列组合公式: n!/r!(n-r)!
                //穷举--求得被除数
                var ExhaustiveTimes = factorial(one + two);
                //重复的次数---求得除数
                var repeatedTimes = factorial(one) * factorial(two);
                //算出次数---相除
                var thisWayTime = ExhaustiveTimes / repeatedTimes;
                //存进数组
                counts.push(thisWayTime);
            }

            //计算每种方式的,除去全1全2,存入数组
            for (var j = 0, waysLen = waysArr.length; j < waysLen; j++) {
                if (waysArr[j].one != 0 && waysArr[j].one != 50) {
                    thisWayTimes(waysArr[j].one, waysArr[j].two);
                }
            }

            //求和函数
            function arrayNumSum(len) {
                if (len <= 0) {
                    return 0;
                } else {
                    return counts[len] + arguments.callee(len - 1);
                }
            }

            //求和,包括全1全2
            countsSum = arrayNumSum(counts.length - 1) + 2; //计算出来共是20,365,010,749次
            alert(countsSum);
        })();
 后来正解出来,我的答案是不对,又不全错,因为排列组合公式做了除法运算,js算出来的结果不精确。

(这就是没有找到真正数学规律的方案,费力不讨好)

 

 peter.liu的思路:

 以一个台阶为迈步的单位, 每次迈步都只有三种可能: 
1.一次走完了一个台阶, 这种情况用 ‘O’表示.  (One的首字母)
2.一次走两个台阶, 但是只走到前一半, 脚还在空中悬着, 没放下. 这种情况用’T1’表示. (Two的首字母)
3.一次走两个台阶, 这次走的是后一半, 也就是脚从空中放下的过程. 这种情况用’T2’表示.
假设这个人开始走
1.走第一个台阶他有两个选择: ‘O’, 和 ‘T1’
2.走第二个台阶他的选择取决于第一个台阶怎么走的:
   a.前一个台阶如果是’O’和’T2’, 这个台阶就有两个选择: ’O’和’T1’
   b.前一个台阶如果是’T1’, 那么这个台阶就只能是’T2’.  (悬着的脚总要放下来才行啊)
3.走第三个台阶的方式, 取决于第二个台阶是怎么走的
4.走第n个台阶的方式, 取决于第n-1个台阶只怎么走的.
可以把他的每一步想象成一棵多叉树的节点, 下一步有多种走法, 那么节点就分叉. 这棵树一直到50层, 第50层有多少个叶节点, 就一共有多少种走法. 每一种走法, 都代表了从根节点到某一叶节点的那条路径.
当然, 有一个问题, 最后一层的节点类型是不能为’T1’的, 否则悬着的脚就放不下来了.
代码如下: 

(function(){

function steps(n){
    if (n === 1)
        return ['O', 'T1']; //第一步两种可能
    lastSteps = steps(n-1);
    var currentSteps = [];
    for(var i = 0; i< lastSteps.length; i++){
        var lastStep = lastSteps ;
        if(lastStep === 'O' || lastStep === 'T2')
            currentSteps.push('O', 'T1');
        else if(lastStep === 'T1')                                              
            currentSteps.push('T2');        
    }
    return currentSteps;
}

var result = steps(20);
result = result.filter(function(item, index){return item !== 'T1'}); //最后一步不能是'T1', 过滤掉
console.log(result.length);

})();
 

最终发现, 到30层的时候, 结果已经是100多万了, 并且以指数级增长. 运算第50层的时候会卡死, 因为可能性太多运算量太大了. 
(这种思路很好,而且可以求得走上去的路径,可以说既有次数,又有证据,可惜就是运算量太大)

 

 费波拉希数列:

 peter的方法虽然不能求得50层的次数,但是可以求得前30多层。依次如下:

一共1个台阶的话有1种走法.

一共2个台阶的话有2种走法.

一共3个台阶的话有3种走法.

一共4个台阶的话有5种走法.

一共5个台阶的话有8种走法.

一共6个台阶的话有13种走法.

一共7个台阶的话有21种走法.

一共8个台阶的话有34种走法.

一共9个台阶的话有55种走法.

一共10个台阶的话有89种走法.

一共11个台阶的话有144种走法.

一共12个台阶的话有233种走法.

一共13个台阶的话有377种走法.

一共14个台阶的话有610种走法.

一共15个台阶的话有987种走法.

一共16个台阶的话有1597种走法.

一共17个台阶的话有2584种走法.

一共18个台阶的话有4181种走法.

一共19个台阶的话有6765种走法.

一共20个台阶的话有10946种走法.

一共21个台阶的话有17711种走法.

一共22个台阶的话有28657种走法.

一共23个台阶的话有46368种走法.

一共24个台阶的话有75025种走法.

一共25个台阶的话有121393种走法.

一共26个台阶的话有196418种走法.

一共27个台阶的话有317811种走法.

一共28个台阶的话有514229种走法.

一共29个台阶的话有832040种走法.

一共30个台阶的话有1346269种走法.

一共31个台阶的话有2178309种走法.

一共32个台阶的话有3524578种走法.

一共33个台阶的话有5702887种走法.

一共34个台阶的话有9227465种走法.

一共35个台阶的话有14930352种走法.

......
这不正是个费波拉希数列!!!!

 知道这个数学规律就好办了。代码如下:


        function fib(n) {
            return function(n, a, b) {
                return n > 0 ? arguments.callee(n - 1, b, a + b) : a;
            } (n, 0, 1);
        }
        fib(0); //0
        fib(1); //1
        fib(2); //1
        fib(3); //2
        fib(4); //3
        //......
        fib(50); //12586269025
        fib(51); //20365011074,这里是上到第50个阶梯
 

 我想大家会有很多其它解法,欢迎留言讨论。
举报
英姿勃发
发帖于6年前 22回/3K+阅
共有22个评论 最后回答: 3年前
大公司总是搞些这样的题目,招扫地的不知道是不是要问一个一平米的地方有多少清洁方式!!

引用来自“笨蛋EGG”的答案

大公司总是搞些这样的题目,招扫地的不知道是不是要问一个一平米的地方有多少清洁方式!!
某个程度上来说,这和高考出卷人是一个类型。
--- 共有 1 条评论 ---
小小兔中国的教育制度下出来的人,只能是这样了。。。 因为他们就是那样从小到大的考来的 5年前 回复

其实现在在中国很多公司都一样,都不知道自己要什么人。社会环境好,聚的财不知道怎么花了,乱搞呢。

引用来自“奔小康”的答案

其实现在在中国很多公司都一样,都不知道自己要什么人。社会环境好,聚的财不知道怎么花了,乱搞呢。

当他们不知道要什么人的时候,那就看你自己对这份工作的渴望程度了。

有那么复杂么?我想的很简单

可以通过

计算出来就可以了

不知道对不对?(注: C是组合)

--- 共有 6 条评论 ---
J-will看了好长时间,终于看懂了…… 5年前 回复
RainJ@JiangMiao : 组合(C)的下标是底吧?我看楼主贴的公式是这样的啊,当然你写的C(n, r) 也是对的。 6年前 回复
JiangMiao@windrain : 以26为例C(24, 26) = 0,意为24取26 6年前 回复
RainJ@JiangMiao : 我觉得没有反,i表示上完台阶总共需要抬脚的次数,50-i表示所有次数中2步的数量。 最低需要25次2步0次1步最多需要50次1步0次2步。(当然不考虑走到半中间下台阶的情况) 6年前 回复
JiangMiaoC的上下标反了 6年前 回复

啊 ~!!! 疯了!疯了!!  漫天的斐波那契数列 !!!  是不是大家对这个特别有爱啊?? 一周内看到差不多4个类似的问题了!!!!

母猪下崽,兔子下崽,植物生长, 现在又有个爬楼梯!!!!!!   

顶部