也来说说电影《少年班》中周知庸问王大法的问题

原创
2016/06/08 17:44
阅读数 3.7W

在电影《少年班》中周知庸老师刚遇到王大法的时候,周问了王这么一个问题:

设一共有20级楼梯,每次能下1级或2级,问共有多少种下法?

王大法很快算出了有10946种。

其实这个数字也不难得出,设下n级楼梯时有F(n)种下法,那么n=1时有1种下法,n=2时有2种下法(连下两个一级或直接下两级),n>=3时有F(n-1)+F(n-2)种下法。所以F(1)=1,F(2)=2,F(3)=F(2)+F(1),F(4)=F(3)+F(2),F(5)=F(4)+F(3),…… 最后F(20)=F(19)+F(18)

这个递归形式的计算方法和斐波那契数列(OEIS:A000045)是一样的,只不过初始值不一样。

斐波那契数列的递归规律:

(图1)

这是我们要计算内容的递归规律:

(图2)

用代码实现这个递归也很方便,如下面的VB.net函数:

Public Function Func(x As Integer) As Integer
    If x < 0 Then
        Return 0
    ElseIf x = 1 Then
        Return 1
    ElseIf x = 2 Then
        Return 2
    Else
        Return Func(x - 1) + Func(x - 2)
    End If
End Function

使用此函数对前20级楼梯的计算结果为:

F(20)=10946,电影中王大法给出的结果与之一致。

下面我们更深入地研究一下这个问题:找出这个数列的通项公式。 Richard A. Brualdi 所著的《组合数学》第5版(冯速等译)一书第7章《递推关系和生成函数》给出了寻找斐波那契数列生成函数的方法,我们完全可以照猫画虎,写出本题中数列的通项公式,计算步骤如下:

∵n>=3时,有 F(n)=F(n-1)-F(n-2)

∴n>=3时,F(n)-F(n-1)-F(n-2)=0

令F(n)=q^n,则有

(图3)

(图4)

因为q不为0,所以只需要解出方程q^2-q-1=0即可:

(图5)

q1和q2都是我们所求数列的解,我们所求数列的通项公式可以写成下面的形式:

(图6)

当n=1和n=2时,我们可以联立两个二元一次方程:

(图7)

(图8)

将c1和c2带入到F(n)中

(图9)

因此可得出通项公式为:

(图10)

为验证此方法的正确性,我写了一段代码进行验证:

Public Function Func2(x As Integer) As Decimal
    If x < 0 Then
        Return 0
    ElseIf x = 1 Then
        Return 1
    ElseIf x = 2 Then
        Return 2
    Else
        Dim result As Decimal = 0
        Dim sqrt5 As Decimal = Math.Sqrt(5)
        result = ((5 + sqrt5) / 10) * ((1 + sqrt5) / 2) ^ x + _
            ((5 - sqrt5) / 10) * ((1 - sqrt5) / 2) ^ x
        Return Math.Round(result)
    End If
End Function

运行结果如下,计算得出的结果与上一种递归解法是一样的。

附:本文中所有的数学公式,都是在Wikipedia的编辑器上写的,该编辑器使用TeX语法编辑数学公式,代码如下:

图1: <math>F(n)=\begin{cases}1,n=0\\1,n=1\\F(n-1)+F(n-2),n\ge2\end{cases}</math>

图2: <math>F(n)=\begin{cases}0,n=0\\1,n=1\\2,n=2\\F(n-1)+F(n-2),n\ge3\end{cases}</math>

图3: <math>q^{n}-q^{n-1}-q^{n-2}=0</math>

图4: <math>q^{n-2}\left(q^2-q-1\right)=0</math>

图5: <math>q_1=\frac{1+\sqrt{5}}{2},q_2=\frac{1-\sqrt{5}}{2}</math>

图6: <math>F(n)=c_1\left(\frac{1+\sqrt{5}}{2}\right)^n+c_2\left(\frac{1-\sqrt{5}}{2}\right)^n</math>

图7: <math>\begin{cases}F(1)=\frac{1+\sqrt{5}}{2}c_1+\frac{1-\sqrt{5}}{2}c_2=1\\F(2)=\left(\frac{1+\sqrt{5}}{2}\right)^2c_1+\left(\frac{1-\sqrt{5}}{2}\right)^2c_2=2\end{cases}</math>

图8: <math>c_1=\frac{5+\sqrt{5}}{10},c_2=\frac{5-\sqrt{5}}{10}</math>

图9: <math>F(n)=\frac{5+\sqrt{5}}{10}\left(\frac{1+\sqrt{5}}{2}\right)^n+\frac{5-\sqrt{5}}{10}\left(\frac{1-\sqrt{5}}{2}\right)^n</math>

图10: <math>F(n)=\begin{cases}0,n=0\\1,n=1\\2,n=2\\\frac{5+\sqrt{5}}{10}\left(\frac{1+\sqrt{5}}{2}\right)^n+\frac{5-\sqrt{5}}{10}\left(\frac{1-\sqrt{5}}{2}\right)^n,n\ge3\end{cases}</math>

END

展开阅读全文
打赏
2
7 收藏
分享
加载中
也是闲的不要不要的 高中知识温习啊
2016/06/13 11:24
回复
举报
更多评论
打赏
1 评论
7 收藏
2
分享
返回顶部
顶部