[高级难度真题] 村庄走法

小学教育网

设从A1按箭头方向走到An+1的走法数为an，n=1，2，…，9.则a9即为所求（因为从A10回到A1只有一种方式）.可见，a1=1，a2=2，ak＋1=ak＋ak-1为递推公式。
        ∴an（n＝1，2，…，9）依次为1，2，3，5，8，13，21，34，55.即共55种不同的走法。也可以用图来表示解答过程.
       

100403_4c5779131992351.jpg

        每一个村（点）旁边的数字就是到这村的不同走法个数.正好符合斐波那契数列的特点。
        从A1出发走到A2点只有一种方式，A2点标有数目1.从A1到A3，一种直接沿圆弧走，另一种途经A2走，所以共有1＋1＝2种方式，从A1到A4，有两种方式，一种途经A2再沿从A2到A4的直线走，另一种途经A3到A4.所以总方式数目等于A1到A2的方式数加A1到A3的方式数。
        也即（A1→→A4）方式数
        =（A1→→A2）方式数+（A1→→A3）方式数
        =1＋2
        ＝3
        其余类推.