查看完整版本: 上楼走台阶的问题

上楼走台阶的问题

一个人上楼,他有两种走法,走一阶或走两阶,问他上10阶楼梯有几种走法?[size=4][/size]

应该还是两种走法，走一阶或走两阶，不知对不对

可以用穷举法来计算

我的木头脑袋只会用穷举法...实在是太多了。
希望有人用简便的方法算出来。我要睡觉啦。

10步走完：
1 1 1 1 1 1 1 1 1 1

9步走完：
1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 2 1 1
1 1 1 1 1 2 1 1 1
1 1 1 1 2 1 1 1 1
1 1 1 2 1 1 1 1 1
1 1 2 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1

8步走完：(开始多了...)
1 1 1 1 1 1 2 2
1 1 1 1 1 2 1 2
1 1 1 1 2 1 1 2
1 1 1 2 1 1 1 2
1 1 2 1 1 1 1 2
1 2 1 1 1 1 1 2
2 1 1 1 1 1 1 2
1 1 1 1 1 2 2 1
1 1 1 1 2 1 2 1
1 1 1 2 1 1 2 1
1 1 2 1 1 1 2 1
1 2 1 1 1 1 2 1
2 1 1 1 1 1 2 1
1 1 1 1 2 2 1 1
1 1 1 2 1 2 1 1
1 1 2 1 1 2 1 1
1 2 1 1 1 2 1 1
2 1 1 1 1 2 1 1
1 1 1 2 2 1 1 1
1 1 2 1 2 1 1 1
1 2 1 1 2 1 1 1
2 1 1 1 2 1 1 1
1 1 2 2 1 1 1 1
1 2 1 2 1 1 1 1
2 1 1 2 1 1 1 1
1 2 2 1 1 1 1 1
2 1 2 1 1 1 1 1
2 2 1 1 1 1 1 1

7步走完：(时间有限，我放弃了...) :s_3:

89种，我用组合的方法计算，
C10 0（10是下标，0是上标，后同）＋C9 1＋C8 2＋C7 3＋C6 4＋C5 5
＝1+9+28+35+15+1
＝89

记得加我分哦，呵呵

我来说我的答案：
一阶台阶，当然（1）一步就跨上去了，有一种走法。

两阶台阶，可以（1 1）一步一步走，也可以（2）两步一次性踏上去，有两种走法。

三阶台阶，可以 1 1 1；1 2；2 1；三种走法。（数字1，2分别表示走的阶数）

四阶台阶，可以 1 1 1 1；1 1 2；1 2 1；2 1 1；2 2；五种走法。

五阶台阶，可以 1 1 1 1 1；1 1 1 2；1 1 2 1；1 2 1 1；1 2 2；2 1 1 1；2 2 1；2 1 2；八种走法。

六阶台阶，可以 1 1 1 1 1 1；1 1 1 1 2；1 1 1 2 1；1 1 2 1 1；1 1 2 2；1 2 1 1 1；1 2 1 2；1 2 2 1；2 1 1 1 1；2 1 1 2；2 1 2 1；2 2 1 1；2 2 2；十三种走法。

七阶台阶，



我们将上面的走法数依次列成一个数列

1         2   3   5   8   13
不难发现一个规律：后面的数等于他前面两个数的和。（3=2+1；5=3+2；8=5+3；13=8+5）

那么：1，2，3，5，8，13，21，34，56，（89）

所以是89

看了4楼的做法
只有一种想法，大刀打不过导弹，还是高科技厉害啊，佩服ING

数学向来是我最怕的科目了。
4楼的解答很科学。
5楼的解答很独特。:loveliness:

恩，89 种！

5 楼是 凑数列然后硬相加的笨办法，4楼就是运用数列的运算法则进行运算了！

其实5L的兄弟再想细一点就很容易了

考虑n>=3的情况,假设f(n)表示走到第n级台阶时候的的算法,那么他就可以从第n-2级走两步到n级,或者从第n-1级走一步到n级
所以,f(n)=f(n-2)+f(n-1)
现在呢,显然有,f(1)=1,f(2)=2
所以
f(3)=f(1)+f(2)=1+2=3
f(4)=f(2)+f(3)=1+2=5
f(5)=f(3)+f(4)=1+2=8
f(6)=f(4)+f(5)=1+2=13
f(7)=f(5)+f(6)=1+2=21
f(8)=f(6)+f(7)=1+2=34
f(9)=f(7)+f(8)=1+2=55
f(10)=f(8)+f(9)=1+2=89

这个数列就是斐波那契数列,类似的就可以一步一步做下去

[[i] 本帖最后由 紫天一色 于 2007-9-24 17:38 编辑 [/i]]

这题我硬排出来的89，太难了，关键是统计起来错综复杂用排列公式容易重复统计，要是把题目再改一下还可以一步走三层那就更复杂了

这个改成1000个台阶只能交给计算机做了:s_6:

这个问题真难啊,上学的时候就最怕这个了:s_6:

不对吧,应该有太多种走法了,不止89啊,那他走2步退1步,走3步退2步........哈哈,开个玩笑啊

[quote]原帖由 [i]吕马全[/i] 于 2007-9-25 15:23 发表 [url=http://www.iyin.net/luntan/redirect.php?goto=findpost&pid=10074185&ptid=623446][img]http://www.iyin.net/luntan/images/common/back.gif[/img][/url]
这题我硬排出来的89，太难了，关键是统计起来错综复杂用排列公式容易重复统计，要是把题目再改一下还可以一步走三层那就更复杂了 [/quote]

可以一步走三层其实是一样的,类似我在9L的解法

考虑n>=4的情况,设f(n)表示走到第n级的走法有多少种,他可以从从f(n-3)一次走3步上来,也可以从f(n-2)一次走两步上来,还可以从f(n-1)一次走一步上来,这样
f(n)=f(n-3)+f(n-2)+f(n-1)
显然有f(1)=1
         f(2)=2
         f(3)=4
接下来就可以求出f(4),再求出f(5),再求出f(6)

……