腾讯面试题：50个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法【原】
- XcessLeo - 博客园-首页原创精华区有个同学去了腾讯，他说面试时有这么一道思维题：50个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法. 1，求出走上次可能有的方式，这里的方式是指：共走多少个1步，多少个2步. 比如说，你走了2个1步，其余走2步，要走24个2步，用对象存起来就是：{one:2,two:24}. 2，每个方式的走法是可以通过排列组合公式算出来的.
腾讯面试题：50个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法【原】
标签：
腾讯
面试
阶梯
| 发表时间：2011-09-14 16:26 | 作者：繁花 XcessLeo
出处：http://www.cnblogs.com/
有个同学去了腾讯，他说面试时有这么一道思维题：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);
})();
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[i];
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);
})();
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[i];
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个阶梯
我想大家会有很多其它解法，欢迎留言讨论。
本文系原创，转载请声明出处（http://www.cnblogs.com/flowerszhong/）
作者: 繁花 发表于 2011-09-14 16:26 原文链接
最新新闻：
· 用笔记本煎蛋，伊莱克斯推出笔记本电磁炉(2011-09-14 21:06)
· 敏捷精益九问(2011-09-14 20:19)
· 乔布斯催生的创业商机(2011-09-14 18:00)
· Augmented Car Finder：用增强现实技术找汽车(2011-09-14 17:55)
· Windows 8你不可不知的4件事情(2011-09-14 17:55)
相关 [腾讯 面试 阶梯] 推荐：
中国将从7月全面试行阶梯电价
- - Solidot国家发展改革委宣布，从7月1日开始在全国全面试行阶梯电价制度. 虽然新的阶梯电价是按照“少用不涨，多用多花”的原则制定，但许多民众担忧，新的规定是变相猛涨电价. 中国电力企业联合会今年3月发布的报告称，中国电价水平偏低，国内电价不应处于人为抑制状态，中国电价应每年提高5%. 这是与西方国家的平均水平价格对比而得出的.
九月腾讯，创新工场，淘宝等公司最新面试十三题
- iDesperadO - 结构之法 算法之道 九月腾讯，创新工场，淘宝等公司最新面试十三题. 曾记否，去年的10月份也同此刻一样，是找工作的高峰期，本博客便是最初由整理微软等公司面试题而发展而来的. 如今，又即将迈入求职高峰期--10月份，而本人也正在找下一份工作中，所以，也不免关注了网上和我个人建的算法群Algorithms1-10群（第1-9群已满，Algorithms_10群，149200941）内朋友发布和讨论的最新面试题.
春招两次腾讯面试都挂二面，分享下我失败+傻傻的面试经历 - 帅地 - 博客园
- -这个春招估计也要介绍了吧，自己投的公司也不多吧，投简历的时候，如果你提前批和正常网申都投的话，可能会获得两次笔试/面试的机会，我投了两次腾讯，不过，两次都在二面挂了，特别是第二次二面，我真的决定自己太他妈傻了. 作为一个新人，谈谈我面试过程中犯过的一些错吧，或许对你也有点收获. 腾讯提前批的面试应该是一个月前就开始的，我第一个投的公司就是腾讯了，人生的第一次笔试和面试也献给了腾讯.
[原]九月百度人搜，阿里巴巴，腾讯华为小米搜狗笔/面试三十题(更新至09.25)
- - 结构之法 算法之道 最新九月百度人搜，阿里巴巴，腾讯华为小米搜狗笔试面试三十题. 自发表上一篇文章至今（事实上，上篇文章更新了近3个月之久），blog已经停了3个多月，而在那之前，自开博以来的21个月每月都不曾断过. 正如上一篇文章 支持向量机通俗导论（理解 SVM的三层境界）末尾所述：”额，blog许久未有更新了，因为最近实在忙，无暇顾及blog.
【8090在职场】阿里、腾讯、百度产品经理40+道面试题记录：我是怎样同时拿到BAT Offer的？
- - SocialBeta华中科技大学新闻学院大四应届生. 2015年已经来到石榴如火的5月，没错，小半年就快过去了. 很多同学正在毕业找工作，也有些同学在准备着2015的暑期实习. 而进入4A、BAT、500强是很大部分营销和传媒人的选择. 在求职或求实习的过程中，你一定希望看到前辈们的实际求职经历或者经验心得分享吧. 不管是企业的招聘流程、求职环节设置、面试题、学长学姐的真人故事，都能让你更胸有成竹和收到鼓舞.
最早实施阶梯电价的是哪国？
- - 百度知道_精彩推荐悬赏分：0 - 解决时间 2012-7-1 22:46. 实施阶梯式电价的做法，在国际上早有先例. 上个世纪70年代石油危机以后，日本、韩国及美国的部分地区对居民用电采取了阶梯式电价的做法，将居民用电实行分档定价，用电越少价格越低，用电越多价格越高. 这样，既能合理反映供电成本，又能兼顾不同收入水平居民的承受能力.
阶梯电价都是怎么算电费的？
- - 百度知道_精彩推荐悬赏分：0 - 解决时间 2012-7-1 22:37. 发改委明确表示居民电价严重偏低，但不准备采取“一刀切”提价，而是推行相对公平的居民生活用电阶梯式递增电价. 这不能不触及老百姓的敏感神经，对普通群众而言，电费是否要多掏腰包，关键取决于“第一阶梯”电量基数，据国家发改委价格司司长曹长庆披露，阶梯式电价拟将居民用电分为保证基本生活需求用电、正常家庭生活用电和奢侈型用电三档.
腾讯的内涵图
- keeno - 阿禅日记2011年5月31日10:33，腾讯QQ 浏览器首页的截图如下：. 内涵关键词：释放、aiww、64. 1小时后，腾讯将图片替换掉了. 对这位如此有内涵的经理或编辑或设计师致敬. © Jason Ng for 阿禅日记, |. 不要用中国手机号来找回Gmail密码.