文档章节

记一道面试题

纳兰清风
 纳兰清风
发布于 2015/10/03 15:43
字数 242
阅读 198
收藏 5

题目:有n个台阶,每次可以走的步数任意,问有多少种走法?

面试时由于太紧张没答上,回来后仔细想了想,顺便记一下。

我的思路是n个台阶,相当于是有n个小球依次排开,有n-1个木棍,将0~n-1个木棍放到这些小球的间隔中,将这n个小球分成若干份,问有多少种分法的问题。这是一个组合数学问题,稍微分析一下就知道可以用如下算法:

1.设木棍个数k ∈ [0,n-1], k∈Z

2.计算k个木棍插在n-1个缝隙中有多少种插法: C(n-1,k)

3.求和:∑ C(n-1,k) (k ∈ [0,n-1], k∈Z)

=C(n-1,0) + C(n-1,1) + C(n-1,2) + ... + C(n-1,n-1)

等于杨辉三角第n行求和,其生成函数为(1+x) ^ (n-1) 取x=1,即最后结果=2^(n-1)。

© 著作权归作者所有

纳兰清风

纳兰清风

粉丝 33
博文 36
码字总数 37100
作品 0
朝阳
程序员
私信 提问
2018 前端面试准备

前端面试常见问题按知识点分类整理 前端面试常考问题整理,按模块知识点分类,持续完善中... Front-end-Developer-Questions by Modules and knowledge 前端面试经典问题:CSS 中居中的几种方...

掘金官方
2017/12/14
0
0
30行代码实现一个带并发数限制的fetch请求函数

早上吃早餐边逛掘金的时候看到一个面试题,看下面的各位大佬各显神通,我也手痒,拿起我的机械键盘一顿乱敲,发现只需要30行代码就可以实现,似不似很腻害👻👻,快来跟我往下翻😛 原题...

zenghongtu
03/14
0
0
前端相关整理

整理一下最近在网上收集的前端面试相关资料,包括预备知识、书籍、面试考点、面经等。前端方面资料其实太多太多,就光从知乎、前端乱炖、w3cplus 等网站就能找到很多,所以针对细节不发散,仅...

Seas0n_
2016/03/01
335
0
18届清华硕士狂拿18家互联网公司offer

2018校招总结(外企,国内大公司,国内创业公司) 本篇是我参加2018春招实习和秋招的求职经历,除了笔试面试中遇到的一些问题,更多的是一些个人想法。 春招和秋招面了不少公司,实习offer有...

野梦M
2017/12/18
0
1
远程面试的问题

因为地点不同,所以面试先安排远程面试,就是他们出题,自己这边做,写好程序后截图给他看源码。 HR发了3道面试题,都是算法面试题。一道一道发的,算法面试题网上都有答案。 但是都没有拿网...

盲人摸象
2015/02/09
3.2K
21

没有更多内容

加载失败,请刷新页面

加载更多

[转] Java 无界阻塞队列 DelayQueue 入门实战

原文出处:http://cmsblogs.com/ 『chenssy』 DelayQueue是一个支持延时获取元素的无界阻塞队列。里面的元素全部都是“可延期”的元素,列头的元素是最先“到期”的元素,如果队列里面没有元...

泥瓦匠BYSocket
6分钟前
1
0
zk中集群版中角色和消息类型

服务器角色 LEADER LEARNER FOLLOWING OBSERVER 消息类型 数据同步 服务器初始化 请求处理型 会话管理型 LEADER 集群工作核心,作用有: 1事务请求唯一调度和处理者,保证事务处理顺序性 2集...

writeademo
8分钟前
2
0
阿里云推送的基本使用-Swift;iOS10+

func initCloudPush(){ CloudPushSDK.asyncInit("*****", appSecret: "*******") { (result) in if result!.success{ print("deviceId===......

west_zll
19分钟前
2
0
分布式及高可用元数据采集原理

转载本文需注明出处:微信公众号EAWorld,违者必究。 引言: 元数据采集是元数据产品的核心部分,如何提升采集效率是需要仔细斟酌的事情,既要保持稳定性也要保持跟上主流技术的发展趋势。元...

EAWorld
35分钟前
2
0
为构建社交关系链手淘都做了啥?

作者|王卫(泓冰) 出品|阿里巴巴新零售淘系技术部 01、淘宝社交关系推荐的背景 1、互联网下半场到来:互联网的下半场,人口红利消失,各大平台需要对用户做精细化运营,用户的增长和留存是每一...

阿里云官方博客
36分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部