算法问题

风行者 · 发表于 2010-8-7 16:49:34

有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法？

pusofalse · 发表于 2010-8-7 17:00:15

把10分解成1、2，总共有多少种解？

1+1+1+1+1+1+1+1+1+1
2+2+2+2+2
1+2+1+1+1+1+1+1+1
是这个意思吗？另外1+2+2+2+2+1不同于2+2+2+2+1+1？

hzxymkb · 发表于 2010-8-7 17:02:11

看来P版已经是想好了！期待P版的代码！

水木子 · 发表于 2010-8-7 17:04:06

1111111111
111111112
11111122
1111222
……

是这样吗？

pusofalse · 发表于 2010-8-7 17:05:46

回复 3# hzxymkb

没想好，只是在理解题意呢。对于这样的算法题目，我是最头疼的，初步设想要用递归。

风行者 · 发表于 2010-8-7 17:22:21

就是P版理解的题意,期待答案

水木子 · 发表于 2010-8-7 17:47:48

本帖最后由水木子于 2010-8-8 09:04 编辑

还好楼主说只有10级台阶，要说100级 …… 那还得了啊！

tryhi · 发表于 2010-8-7 18:25:18

本帖最后由 tryhi 于 2010-8-7 23:53 编辑

我不懂，但提供一下思路.
这是关于排列问题.
0个2时有1种
1个2时有9种
2个2时有28种
3个2时有35种
4个2时有15种
5个2时有1种
共89种

3mile · 发表于 2010-8-7 19:25:48

1、登上第1级台阶只有1种登法。
2、登上第2级台阶可由第1级台阶上去，或者从平地跨2级上去，故有2种登法。
3、登上第3级台阶可从第1级台阶跨2级上去，或者从第2级台阶上去，所以登上第3级台阶的方法数是登上第1级台阶的方法数与登上第2级台阶的方法数之和，共有1+2＝3（种）
以此类推，可得如下方法：

Local $n=1,$y=2,$j
For $i=3 To 10
        $j=$n+$y
        $n=$y
        $y=$j
Next
MsgBox(0,0,"有"&$j&"种方法")

pusofalse · 发表于 2010-8-7 19:53:52

只是问有多少种方法吗？不输出具体的走法方案？

风行者 · 发表于 2010-8-7 20:24:14

能够输出具体走法最好

pusofalse · 发表于 2010-8-7 21:05:35

本帖最后由 pusofalse 于 2010-8-8 00:34 编辑

费了不少脑细胞啊。测试10阶用时5ms左右，递归的效率永远是个大问题~

Local $iMaxLevels = 10, $iNumSeqs = 1, $sInitSeq, $iTimer = TimerInit()

For $i = 1 To $iMaxLevels
        $sInitSeq &= 1
Next
$sResult = $sInitSeq & @CRLF

_StepsRecur($sInitSeq, $iMaxLevels, $sResult)
$sResult &= @CRLF & $iNumSeqs & " method(s). Time delay: " & TimerDiff($iTimer)

FileDelete("Steps.x")
FileWrite("Steps.x", $sResult)
ShellExecute("Steps.x")

Func _StepsRecur($sSeq, $i, ByRef $sResult)
        If ($i < 2) Then Return

        $iNumSeqs += 1
        _StepsRecur($sSeq, $i - 1, $sResult)

        $sSeq = StringLeft($sSeq, $i - 2) & 2 & StringTrimLeft($sSeq, $i)
        $sResult &= $sSeq & @CRLF

        _StepsRecur($sSeq, $i - 2, $sResult)
EndFunc        ;==>_StepsRecur

C.L · 发表于 2010-8-7 23:24:31

这道题是比较麻烦，有空再研究下，先看看P版的递归法

大绯狼 · 发表于 2010-8-7 23:37:40

我是来学习的。。。。

		自动登录	找回密码
密码			加入

[效率算法] 算法问题

相关帖子

评分

评分