求一递归算法

八云紫

题目是这样的：

    有一个 N 层台阶， 可以一次上一层台阶， 也可以一次上三成台阶，问有多少种走法？

要求1： 用递归；

要求2： 给个思路就可以啦。

谢谢大家{/hx}。

hitlerson

Fibonacci数列

八云紫

以下引用hitlerson于2008-9-10 12:37:42的发言：

Fibonacci数列

为什么会是 Fibonacci？？

hitlerson

1  1
2  11
3  111 3

第N步是前一步前加1和前三步前加3

如 4 是 3前加1和1前加3

hitlerson

Dim i As Long
If stairnum = 1 Then
methodn = 1
ReDim steps(1 To methodn)
steps(1) = 1
End If
If stairnum = 2 Then
methodn = 1
ReDim steps(1 To methodn)
steps(1) = 11
End If
If stairnum = 3 Then
methodn = 2
ReDim steps(1 To methodn)
steps(1) = 111
steps(2) = 3
End If
If stairnum > 3 Then
Dim a() As String, b() As String, methoda As Long, methodb As Long
upstairs stairnum - 1, a, methoda ’递归调用

upstairs stairnum - 3, b, methodb  '递归调用
ReDim steps(methoda + methodb)
For i = 1 To methoda
steps(i) = 1 & a(i)
Next
For i = 1 To methodb
steps(i + methoda) = 3 & b(i)
Next
methodn = methoda + methodb
End If

End Sub

---

系统信息：本贴获得楼主认可，66RPG感谢您的热情解答～

yangff

Ruby
msxjie = 5
no = 0
sub upsta(n)
  if (n =msxjie) then
    no += 1
  end
  upsta(n+1)
{  upsta(n+2)}
  upsta(n+3)
end
Pascal:
var msxjie:integer;
var no:integer;
msxjie := 5;
no := 0;
procedure upsta(n:integer);
begin
  if (n =msxjie) then begin
    no += 1;
exit;
end;
  upsta(n+1);
  upsta(n+2);
  upsta(n+3);
end;
begin
upsta(0) {0还是1记不得鸟}
no就是答案
end.
不知什么原因,其实就是菲波纳妾数列

---

系统信息：本贴获得楼主认可，66RPG感谢您的热情解答～

yangff

vb(最简单的,速度最快的,不会栈溢出的)：
n = Inputbox("台阶数")

结果=(1/sqrt(5))*(((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)

yangff

可以一次上一层台阶， 也可以一次上三成台阶
记忆里是
可以一次上一层台阶， 也可以一次上两成台阶

原理的话：
转载：
首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。

现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。

我们把上面的分析用一个公式总结如下：

        /  1                          n=1
f(n)=      2                          n=2
        \  f(n-1)+(f-2)               n>2

分析到这里，相信很多人都能看出这就是我们熟悉的Fibonacci序列。

做游戏的新手

连3贴注意

yangff

以下引用做游戏的新手于2008-9-10 14:26:24的发言：

连3贴注意

抱歉我太激动了，这个问题我们曾经讨论过了3个小时