问题
刚才在首页看到一篇博客,说的是腾讯的一道面试题:一个楼梯有50个台阶,每一步可以走一个台阶,也可以走两个台阶,请问走完这个楼梯共有多少种方法?博主把这题分析的很麻烦。引来很多人围观。我以前也碰到过这个问题。写出来和大家分享一下。
举个例子,假设有3个台阶,则有三种走法:分别是,1-1-1, 1-2, 2-1。
分析
很简单的一道题,学过组合数学的人很快就能想到,这是一个递推关系。假设走完k个台阶有f(k)种走法。
- k = 1时,f(k) = 1
- k = 2时,f(k) = 2
- k = n时,第一步走一个台阶,剩n-1个台阶,有f(n - 1)种走法。第一步走两个台阶,剩n-2个台阶,有f(n - 2)种走法。所以共有f(n - 1) + f(n - 2)种走法。
于是有如下公式
代码
int count(unsigned int n)
{
if(n == 1)
return 1 ;
if(n == 2)
return 2 ;
else
return count(n - 1) + count(n - 2) ;
}
具体是怎么走的呢?
上面只给出了有多少种走法,那么具体每一种走法是怎么走的呢?比如n=4时,五种走法分别如下:
1,1,1,1
1,1,2
1,2,1
2,1,1
2,2
我们用一个整型数组来存放每一步的内容,1表示这步走了一个台阶,2表示这步走了两个台阶。回溯法搞定。代码如下。
void count(int n, int t)
{
if(n < 0)
return ;
if (n == 0)
Output(step, t) ;
else
{
for (int i = 1; i <= 2; ++i)
{
step[t] = i ;
count(n - i, t + 1) ;
}
}
}
类似的问题
与此题类似的问题有很多,比如铺地砖问题,自然数拆分等。
铺地砖问题
有一个长度为n,宽度为2的地面,有若干块长为2,宽为1的地砖,请问用此地砖铺完这个地面共有多少种方法?
分析一下,假设铺完长度为n的地面有f(n)种方法,如果第一块地砖竖起来铺,还剩下长度为n-1的地面,有f(n-1)种方法。如下图。
如果第一块地转横着铺,那么还剩下长度为n-2的地面,有f(n-2)种铺法。如下图。
所以这道题与上面的题解法完全一样。不同的题目,相同的模型而已。
自然数拆分
给定一个自然数n,将其拆分为若干个自然数字之和,请问有多少种方法?举个例子,n=4时,可以拆分为1-1-1-1,1-1-2,1-3,2-2。
这题和上面的题很像,不过上面的问题是排列问题,而这题是组合问题,比如n=4时,1-1-2,1-2-1,2-1-1这三种只能算一个拆分。在上面的基础上,去掉重复的组合即可。
分享到:
相关推荐
针对特殊爆破工程(如构筑海堤工程)中对石料规格要求很高,采取一系列的分析实验研究爆破参数数据,找出台阶爆破控制粉矿率的措施。
筑好计算机专业的第一级台阶——谈计算机导论课程教学.pdf
甘肃金昌金川集团股份有限公司西二采区破碎硐室、提升机硐室,在破碎围岩条件下采用上中心导硐法结合正台阶法施工大断面硐室方法,通过合理优化支护参数,提高了施工人员在强支护区域内施工作业的安全性,而且施工速度快...
介绍了技术改进的主要形式和内容,并通过对黑岱沟露天煤矿开采工艺、高台阶抛掷爆的应用和爆破参数的优化等技术改进实例的详细论述,说明其在成本控制中所起到的作用和效果,表明技术改进对于降低露天煤矿生产成本的...
一、增强管理意识——班级更上一个台阶。 1、完善班干部队伍。开学初,创建了更加完善的班级管理体制,加入了新鲜血液,让更多学生得到锻炼的机会。明确了班级努力和前进的方向。 2、定期召开班干部会,总结工作...
车载移动多媒体系统是指嵌入安装在汽车移动环境使用的多媒体系统。主要包括车载导航系统、行车记录仪、车载移动通讯...与此同时国家交通运输部新规适时出台,也将促进国内车载移动多媒体系统发展迈上一个新的台阶。
车载移动多媒体系统是指嵌入安装在汽车移动环境使用的多媒体系统。主要包括车载导航系统、行车记录仪、车载移动通讯系统...与此同时国家交通运输部新规适时出台,也将促进国内车载移动多媒体系统发展迈上一个新的台阶。
九十年代以后,由于人工智能、机械电子和计算机技术以及传感器技术的迅猛发展,使得机器人技术更上一个新的台阶,所以说机器人技术将沿着智能化、复杂化的趋势发展下去。 简单的说机器人就
近年来,随着我国自动化技术的提高,工厂自动化也上了一个新台阶。PLC作为一个新兴的工业控制器,以其体积小,功能齐全,价格低廉,可靠性高等方面具有独特的优点,在各个领域获得了广泛应用。 作为国内最大的...
随着科学技术日新月异的... 九十年代以后,由于人工智能、机械电子和计算机技术以及传感器技术的迅猛发展,使得机器人技术更上一个新的台阶,所以说机器人技术将沿着智能化、复杂化的趋势发展下去。 简单的说机器
也有台阶式,踏步板装在履带上连续运行,俗称自动电梯. 服务于规定楼层的固定式升降设备.它具有一个轿厢,运行在至少两列垂直的或倾斜角小于15°的刚性导轨之间.轿厢尺寸与结构形式便于乘客出入或装卸货物. 1 工程...
数字城市数字城市是从工业化时代向信息化时代转换的基本标志之一。它一般指在城市"自然、社会、经济"系统的范畴中,能够有效...因此,无论从科学的定义上,还是从管理的定义上,数字城市均可视作是人类发展的台阶式进
此文就北京绿化建设有关当前的形势、上新台阶的目标及相应的对策,提出了一些看法.
通过深入调查研究,我们发现这并不是因为同学们学习能力不够,也不是高中教学出现了问题,而是由于初中课改教材与高中教材之间不能很好地衔接。 初中新课程教材删除了繁、难、偏、旧的知识,体现了“浅、少、易”的...
解决问题的方法和思维方式,也与初中有着较大的差异。近78%的学生无法很快适应高中化学的学习,近70%的学生认为高一教学课堂容量大,内容难度大,找不到重点。 一、学生学习困难的原因: 刚入高中不适应主要有四...
通过理论联系实际,巩固所学的知识,提高处理实际问题的能力,为顺利毕业进行做好充分的准备,并为自己能顺利与社会环境接轨做准备。 见习期间我能快速的适应公司的环境,融入企业的团体,用心跟同事沟通,更好的...
这里我进行了20w次连续操作(10w读,10w写),不用pipeline耗时:187242ms,用pipeline耗时:1188ms,可见使用管道后的性能上了一个台阶。看了代码了解到,管道通过一次性写入请求,然后一次性读取响应。也就是说...
在这个系列中一共包含6个案例,从简单到复杂,也是对问题分解、思考和解决的一个过程,它们分别是: (1)类之间的依赖; 降低 (2)接口依赖; (3)基 于配置文件和Reflection的工厂模式; (4)使用Spring.net...