PDF《/01 234 234》

! # ! # ! # ! # $ $ $ $%&

'

()* %&

'

()* %&

'

()* %&

'

()* + + + +,-.

,-. ,-. ,-. /01 /01 /01 /01

234 234

234 234

1 棋盘的费伯那契 壹.研究动机 在学校科研营的教材中,有一个题目,其内容相当於: 「在一列格 子中,放入黑棋与白棋.规定白棋不可连续放置,而黑棋不受此限, 请问共有几种可能的排列方式?」此题之答案,基本上就是鼎鼎大名 的费伯那契数列(Fibonacci Sequence),那麽,在此规则下,若将格子推 广为 m 列n行的棋盘,那又如何呢?我们对此好奇不已. 贰.研究目的

(一).定义一: 「相邻」的两格即为有共同的边(不包括共同角)

(二)规定:在长方形棋盘中,每一格皆放入黑棋或白棋,规定白 棋不可和白棋相邻,而黑棋没有限制 例: A:可放入白棋或黑棋 B、C:只可放入黑棋

(三).定义二:我们用 F ( m , n ) 表示在 m 列n行的棋盘,遵照 上述规定放入白棋与黑棋 , 所有可能的排法的总数

(四).我们的目的:探讨 F ( m , n ) 的性质,另外,我们也想探讨 不同形状棋盘的方法数,例如:圆环状棋盘.

2 参.研究设备与器材 纸、笔、计算机、个人电脑 肆.研究方法及过程

(一).F ( m , n )的求法: (甲).实际排列: 定义:顾名思义就是把每一种可能的排列组合一一列 出,再清点所有个数. 优点;

想法简单 缺点;

作业繁杂,当行数及列数增加,则可能排列方法 数 例;

如图一,为一列四行及一列五行所有可能的排列方法 (图一)

3 (乙).导向排列: 定义:见图二为导向法的树状结构图,图为二列

5 行 可能的排列个数 优点:计算速度加快,可处理较大的行列数 缺点:仍需要要大量纸张画图归纳 第一行 第二行 第三行 第四行 第五行

41 17

7 3

1 29

12 5

2 1

29 12

5 2

1 (图二) 图二中,为二列五行方法数的推导.我们先在第五行放入棋子,而 这有 、 、 等三种放法.再由第五行往回推至第四行,第四行 中的 可和第五行中的 、 、 相邻,而第四行中 ,只可与第 五行中的 、 相邻 , 又第四行中的 , 只可与第五行中的 、 相邻,因此,到第四行的总方法数(即为到第三行 的方法数)为3+2+2=7

4 种,依照此原理,即可快速推导至第一行的方法数(第一行方法数总合即 为一列五行的总方法数) , 按照同样的方法 , 一定可以快速求出 F ( m , n ) . (丙).导向排列符号化: 为方便计算,我们将棋盘符号化. 优点:(a)节省纸张上的繁杂图示 (b)标示清楚易懂 首先,我们将已放入黑棋的格子以b表示,而放入白棋的格子以w表示. 例: F( ) = F (

2 ,

3 ) F( ) = F (

4 , b b ) F( )= F (

4 , w b b ) F (

2 ,

3 ) = F ( ) = F( ) + F ( ) + F ( )

5 = F (

3 , b b ) + F (3 , w b ) + F (

3 , b w ) = [ F ( ) + F ( ) + F F ( ) +F ( ) ]+[F ( ) + F ( ) ] = [ F (

2 , b b ) + F ( 2, w b ) + F (

2 , b w ) ] +[ F (

2 , b b ) + F (

2 , b w ) ]+[F (

2 , b b ) + F (

2 , w b ) ] =

3 F ( ) + 2F ( ) + 2F ( ) =

3 F (

2 , b b ) + 2F (2 , w b ) + 2F (

2 , b w ) = 3[F ( ) + F ( ) + F ( )] +2[ F ( )+ F ( ) ] +2 [F ( ) + F ( ) ] = 3[F (

1 , b b ) + F (1 , w b ) + F (

1 , b w )] +2[ F (

1 , b b ) + F (

1 , b w ) ]+2 [F (

1 , b b ) + F (

1 , w b ) ] =

7 F ( ) + 5F ( ) + 5F ( ) =

17 另外,我们定义 F(

1 ,

0 ) = F ( ) =

1 F(

2 ,

0 ) = F ( ) =

1 乃至 F ( m ,

0 ) =