文档章节

坏台阶问题

o
 osc_n6euf5h6
发布于 2019/03/20 01:19
字数 671
阅读 8
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

题:

一个人走了很多年,发现自己走到一个很长的,年久失修的楼梯面前。年久失修的意思就是,有k个台阶坏了,没法走。楼梯一共有n层,你一次能上一阶、两阶或三阶台阶,请问,你从楼梯底部(0开始)走到楼梯顶部,共有多少种走法。

输入格式

输入数据共两行,第一行包含两个自然数n(1 ≤ n ≤ 100)和 k (0 ≤ k < n),第二行包含k个自然数Xi (1 ≤ Xi  ≤ n),数字之间用一个空格隔开,表示损坏的台阶的序号(从楼梯底部到楼梯顶部,台阶序号依次为1到n)

输出格式

输出数据仅包含一个整数,表示所有可行走法的总数

样例

input
------------------------------------------
5 2
2 4
------------------------------------------
output
------------------------------------------
2

分析

题目解读很重要,简要说就是有一个楼梯有n个台阶,其中坏了k个台阶不能落脚走,楼梯底部平台编号为0,依次往上自增编号1,2,3......n,n为楼梯顶部的平台。一个人从楼梯底部要走到楼梯顶部去,他一步只能走1个或者2个或者3个台阶,问他有几种方法恰巧能够走到楼梯顶部,不限制步数。

把台阶抽象成数组a,a[0]即为楼梯底部的平台处,a[n] 即为所要到达的楼梯顶部。

万物皆可遍历!遍历就要进行比对判断,所要初始化完表示台阶的a数组之后就需要把a数组中的坏的台阶编号对应的数值修改为特定值,可定为-1。

就像求一个集合有多少子集一样的思路去进行判断,判断当这个人站在某个台阶上的时候往后走1步/2步/3步之后再继续1步/2步/3步的情况。

又可以抽象成一颗树,从根节点往下衍生出孩子节点,一直衍生到叶子节点刚好到顶部台阶(满足)或者超过顶部台阶(不满足)。

直接上代码,代码也加上了一些注释,顺着思路应该就能够清晰了。

题目限制输入输出的格式,但我还是加了点提示按舒服点儿的方式去输入,当然你要去修改成题目要求格式也是可以,但是这不是重点,重点还是在解题上,格式规范舒服就好。

如果真的是平台解题那肯定是需要按输入输出格式来的。

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【OSChina Android客户端设计】界面原型代码问题

看到大家说希望能把代码分享出来,实在令我不安。因为这些代码根本就是非常粗糙的原始设计,但既然有这个要求,那么就考虑吧。 目前,客户端设计还仅仅处在界面原型的设计和讨论定位的阶段,...

BarryWey
2011/05/10
441
3
想看看大家是怎么实现百鸡百钱问题的

RT,如果大家有兴趣,可以用任何语言把百鸡百钱的问题实现下。

只会百度的程序员
2013/04/15
858
8
[用事实说明两个凡是]一个由mysql事务隔离级别造成的问题分析

背景 最近要做一个批跑服务, 基本逻辑就是定时扫描数据库的记录, 有满足条件的就进行处理(一条记录代表一个任务,以下任务与记录含义相同). 要求支持多机部署批跑服务. 批跑支持多机部署实现方...

周翼翼
2015/11/24
3.8K
44
tomcat memecached session 共享同步问题的解决

web项目windows系统下实现session的共享 第一个步: 在俩个tomcat的context.xml这个文件中配置如下代码: <Manager className="de.javakaffee.web.msm.MemcachedBackupSessionManager" memca......

海空天阔007
2015/10/12
759
4
nginx过滤url实现前台js的配置问题

基于摘要里的,在Java后台实现很方便,只需要读取properties配置文件即可 但是在前台js,js是在浏览器里执行的,无法读取服务器上的配置,除非请求后台,但是每次的开销也是挺大的,所以这个想法被p...

Crazy_Coder
2015/09/24
433
1

没有更多内容

加载失败,请刷新页面

加载更多

我在广州面试的那些事

背景   这次的疫情让原本看似有序的但是浮躁的社会彻底打乱了,不少劳动者在多年稳定的节奏也随之而变,而我在于其中放慢了步调,从5月份放弃了一份工作同时拒绝了两份offer后回家休息加造...

osc_d8t0zzig
11分钟前
0
0
快速读入、输出,及其他模板

头 如果你在我博客里,读到某个代码没有头。请把这段复制到代码前面: //problem:#include <bits/stdc++.h>using namespace std;#define pb push_back#define mk make_pair#define lo...

osc_k12h8kbw
12分钟前
0
0
彻底解决unable to find valid certification path to requested target

安装证书。 下载证书 第一步是要下载证书 去你程序要访问的网站,点击那个锁按钮,并点击查看详情(chrome浏览器) 点击View certificate 点击详细信息 复制到文件 下一步 选择格式 生成的名...

osc_r9yyhhqz
13分钟前
10
0
reg007最新邀请码!!!

需要的小伙伴留邮箱我邀请你们。

osc_50znnx42
15分钟前
9
0
Python正课目录

本文内容皆为作者原创,如需转载,请注明出处:https://www.cnblogs.com/xuexianqi/p/12515420.html My: 我的整理 我的字典 luffy上线 First:安装教程 PyCharm2020.1破解教程 Python安装1...

osc_wxsc35it
17分钟前
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部