蔡寶桂

初級班∣多餘的搬移在哪裡指定位置化繁為簡搬盤子

初級班∣三根柱子四根柱子五根柱子六根柱子七根柱子八根柱子

小朋友,你已經能夠順利地將整個柱子上的盤子移位了嗎?是否希望能夠挑戰最低搬移次數了?讓我們一起來研究看看!

 

初級班

當你根據規則不斷的移動著盤子後,無論你將盤子放到哪個位置?或者發現整疊的盤子移錯柱子後,又得全部搬到另一枝柱子之時,你是否感覺到達成最低搬運次數的口訣了?『指定位置、雙異單同、毫無虛步!』,就讓我們來看看這兩個口訣!

1.     多餘的搬移在哪裡?

我們先從簡單的三個柱子開始看這個問題。如果有三根柱子,我們將這三根柱子編號,依序為一、二、三號柱子;那麼有兩個盤子放在一號的柱子上,你要怎麼搬才可以將盤子移到二號柱子?

如果你將第一個小盤子移到二號柱子上,你將發現大盤子會壓住小盤子而犯規,因此只得將大盤子放在三號柱子上,然後將小盤子移回一號柱子上,然後在將大盤子移到二號柱子上,小盤子再放回大盤子上﹝如圖一﹞,這麼一來一往的步驟中將比直接將小盤子放到三號柱子、大盤子放在二號柱子,然後將一號柱子放回的步驟﹝如圖二﹞,多了兩個步驟,甚至中間會產生更多的迂迴、更多不必要的搬移。

 


此外,如果現在是搬三個盤子的遊戲,相信你們一定可以在簡單的步驟中扳開兩個盤子到另一根柱子上﹝如圖三﹞,那麼接下來的大盤子移動到空柱子後,如何在迅速、最少的步數下,將另一根柱子上的兩個盤子直接搬到大盤子上?


現在你是否體會到了指定位置的重要了?當我們可以清楚的了解盤子將落在幾號柱子的上面,並且清楚知道搬運的步數,那麼就可以達成最低次數了!

top

2.      指定位置

現在大家來研究看看,如果固定三根柱子,一個柱子是起點,那麼搬運不同盤子數時的第一個盤子究竟要擺到指定的位置上?或者另一個非指定位置呢?

當搬運兩個盤子的時候﹝如圖二﹞,第一個盤子必須搬到非指定位置,才能夠在最少步數下,順利的將盤子搬到指定位置;當三個盤子的時候,我們可以將問題簡化為兩個盤子,而暫時忽略最下層的大盤子,待兩個盤子移到另一個柱子後,再將大盤子移到空出的另一個柱子上,再如法將兩個小盤子移回,如此將發現第一個盤子必須移到指定位置上,才可能將三個盤子移到指定位置。

依此類推,我們可以發現下表的規律:

1:三個柱子下的指定位置規律性

盤子數

兩個盤子

三個盤子

四個盤子

五個盤子

……

2N個盤子

2N+1個盤子

第一個盤子

的搬運策略

非指定位置

指定位置

非指定位置

指定位置

…..

非指定位置

指定位置

top

3.      化繁為簡搬盤子

根據以上之指定搬運策略,不但可以成功的搬出兩個盤子、三個盤子的最少次數,也可以搬出更多的盤子,只要將盤子的數量化繁為簡!

如果,搬運的是三個盤子,你可以將它視為搬兩個盤子,最後加一步移到第三個盤子的步數後,再將兩個盤子移回;如果搬的是四個盤子,你可以將它視為搬三個盤子的方法,然後加一步移到第四個盤子的步數後,再將三個盤子移回,依此類推,不斷簡化盤子數,並隨時判斷基、偶盤子數的搬運策略之第一個盤子的指定位置,如此就可以搬出最低的次數。


例如,五個盤子,搬移前兩個盤子後,將第三個盤子移到空出的柱子上後,依判斷兩個盤子為偶數,第一個盤子必須在非指定位置﹝指不是擺放第三個盤子的柱子上﹞,那麼就可以在最少的步數下,將兩個小盤子移到第三個盤子的上面;接著將第四個盤子移到空出的柱子上後,再判斷三盤子為基數之盤子數,所以要將此三個盤子移到第四個盤子上,第一個盤子必須擺在和第四個盤子相同的柱子,之後再依序重複前面兩個盤子、三個盤子的搬移步驟;當完成了四個盤子在同一柱子上後,再將第五個盤子移到空出的柱子後,判斷四個盤子為偶數盤,則應該將第一個盤子搬到不是第五個盤子的另一個柱子上,如此接連完成和前二、三、四個盤子相同的步驟,即可以在最少的次數下搬移成功﹝如圖四﹞。

top

進階班:最少的次數是多少?

v     三根柱子

根據之前的搬運說明中,不難發現,搬兩個盤子的最少步數是三步﹝移開兩個盤子兩步、小盤子搬回大盤子上一步﹞,而搬三個盤子又可以將它分成搬兩次兩個盤子,加上一步移到最底下的盤子,所以搬移最少步數是3乘以2再加17步。依此類推,我們可以發現以下的規律性:

2:三個柱子下,不同盤子數的最少搬運次數

盤子數

2

3

4

5

6

7

….

n

最少次數

計算

1*2+1

3*2+1

7*2+1

15*2+1

31+2+1

63*2+1

….

?

結果

3

7

15

31

63

127

….

?

發現

22-1

23-1

24-1

25-1

26-1

27-1

….

2n-1

p.s.22,稱之為『22次方』,意思就是2乘以2次,也就是2*2;同理,
23
,稱之為『23次方』,意思就是2乘以3次,也就是2*2*2
24
,稱之為『24次方』,意思就是2乘以4次,也就是2*2*2*2

 

所以,從上面的資料整理中,我們可以發現,如果用n代表盤子的數量,an代表在n個盤子下的移動次數。當n=1的時候就是移動1步,超過1以上可以得到下面的規律性﹝公式﹞:

文字方塊: an=	 
	或
an=	2n-1

 


盤子數少於柱子數時

在柱子數是三的情況下,搬運一個盤子只需要1步,搬運兩個盤子需要2步,且都足以利用空出的兩的柱子直接搬移,而無須重疊等待搬移。同樣的當柱子數是四枝時,盤子數在2個以下的情形和柱子三枝的情形一樣,但是3個盤子的只要搬出3次、疊回2次,只要5次即可,比三根柱子少搬了2次。依此類推,可以得到下表:

3:盤子數少於柱子數時的搬運次數

盤子數

1

2

3

4

5

…..

n

搬運次數

計算

1

2+(2-1)

3+(3-1)

4+(4-1)

5+(5-1)

 

n+(n-1)

結果

1

3

5

7

9

…..

?

發現

1

2*2-1

3*2-1

4*2-1

5*2-1

 

2 n-1

由上可以發現,當柱子數多於盤子數時,搬運的次數為將盤子全部移到各個柱子上,移到和盤子數量相同的次數,接著固定最大的盤子不移到,再將其他的盤子照大小順序移回最大盤子的固定柱子上,移動次數為比全部的盤子數少一次的移動次數。所以會得到以下的規律性﹝公式﹞

top
文字方塊: an=	n+(n-1)  或2 n-1
	
n代表盤子數,an代表移動次數

v    四根柱子

探討各種盤子數少於柱子數的通則之後,則可以進一步討論四根柱子,且盤子數多於、等於柱子數的各種情形。以四個盤子而言,空餘的柱子只有三根,並且加上遊戲規則規定大盤子不得壓小盤子,所以先移到上面兩個盤子到同一根柱子上﹝兩個盤子、四根柱子﹞,因此只剩下三個柱子、兩個盤子的問題,再將第一次移開的兩個盤子移回﹝兩個盤子、四根柱子﹞,因此切分成此三種的移動方式,都是在盤子數量小於柱子數量,移動兩個盤子的情形,對照表3,皆需移動3步共3次,所以總共要9步。

當五個盤子時,也依上面的方法,將盤子切分為盤子數少於柱子數的移動。如,在四根柱子的情形下,移走三個盤子,再剩下的三個柱子下,移走兩個盤子,再將三個盤子移回,對照表3,移動次數為5+3+5=13;六個盤子時,在四個柱子的情形下移動3個盤子,在剩下的3個柱子下移動3個盤子,因此,情形分為盤子數量少於柱子數的﹝對照表3﹞,和盤子數量等於或多於柱子數的﹝對照表2﹞,因此移動次數為5+7+5=17

因照上面之方式,將盤子數量進行分割,並從各種分割情形中找到數量最少的移動次數,得到下表:

4:四個柱子下,不同盤子數的移動次數初探﹝盤子數等於或多於柱子數﹞

盤子總數

4

5

6

7

盤數少於柱數下的移動探討

移動盤數

2

2

2

3

3

移動次數a

3

3

3

5

5

盤數等於或多於柱數下的探討

移動盤數

 

 

3

3

4

移動次數b

 

 

7

7

15

計算移動次數

移動次數a +移動次數b +移動次數a

移動總次數

9

13

17

25

因此,根據表2、表3、表4之資料,超過8個盤子以上之最低次數搬移,則考量如何對8個盤子進行分解,以搬出最小值。例如,8個盤子可以分成四柱5盤和三柱3盤﹝13+7+13=33﹞、四柱3盤和三柱5盤﹝5+31+5=41﹞,或者是四柱4盤和三柱4盤﹝9+15+9=33等,然後取出移動次數最少的盤數組合情形,即可求得每次搬運的最低次數。

5:四個柱子下,不同盤子數的最低移動次數總表

盤子數

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18*

19

20

四柱

第一次

盤數

0

1

2

3

2

3

3

3

5

5

6

7

7

8

9

10

11

12

12

13

14

次數

0

1

3

5

3

5

5

5

13

13

17

25

25

33

41

49

65

81

81

97

113

三柱

第二次

盤數

0

0

0

0

2

2

3

4

3

4

4

4

5

5

5

5

5

5

6

6

6

次數

0

0

0

0

3

3

7

15

7

15

15

15

31

31

31

31

31

31

63

63

63

最低次數

0

1

3

5

9

13

17

25

33

41

49

65

81

97

113

129

161

193

225

257

289

增加次數

0

1

2

3

4

4

4

8

8

8

8

16

16

16

16

16

32

32

32

32

32

*18也可以是13597+31+97=225

*本程式之設計僅到20個盤子,超過20以上也可以依此類推

依此類推,我們將盤子數量分解為二,再從各種不同的分解情形中,選擇移動次數最低的組合。也就是說,當盤子又增加一個時,判斷柱數相同或柱數少一所移動的次數,並且在第一次的移動,因為移開後還得移回第二次移動之上面,所以移動次數為兩倍,根據上面兩項因素的判斷,就能夠很快的掌握最低次數的移動方式。

top

v    五根柱子

盤子數

0

1

2

3

4

5

6*

7*

8

9

10

11

12

13

14

15

16

17

18

19

20

五柱
第一次

盤數

0

1

2

3

4

2

2

2

2

3

4

4

4

4

4

5

6

7

8

9

10

次數

0

1

3

5

7

3

3

3

3

5

7

7

7

7

7

11

15

19

23

27

31

四柱

第二次

盤數

0

0

0

0

0

3

4

5

6

6

6

7

8

9

10

10

10

10

10

10

10

次數

0

0

0

0

0

5

9

13

17

17

17

25

33

41

49

49

49

49

49

49

49

最低次數

0

1

3

5

7

11

15

19

23

27

31

39

47

55

63

71

79

87

95

103

111

增加次數

0

1

2

2

2

4

4

4

4

4

4

8

8

8

8

8

8

8

8

8

8

*6也可以是335+5+5=15﹞;7也可以是437+5+7=19

top

v    六根柱子

盤子數

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

六柱

第一次

盤數

0

1

2

3

4

5

2

3

4

5

5

5

5

5

5

5

5

5

5

5

5

次數

0

1

3

5

7

9

3

5

7

9

9

9

9

9

9

9

9

9

9

9

9

五柱

第二次

盤數

0

1

0

0

0

0

4

4

4

4

5

6

7

8

9

10

11

12

13

14

15

次數

0

1

0

0

0

0

7

7

7

7

11

15

19

23

27

31

39

47

55

63

71

最低次數

0

1

3

5

7

9

13

17

21

25

29

33

37

41

45

49

57

65

73

81

89

增加次數

0

1

2

2

2

2

4

4

4

4

4

4

4

4

4

4

8

8

8

8

8

top

v    七根柱子

盤子數

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

七柱

第一次

盤數

0

1

2

3

4

5

6

2

2

2

2

2

2

2

2

2

2

2

3

4

5

次數

0

1

3

5

7

9

11

3

3

3

3

3

3

3

3

3

3

3

5

7

9

六柱

第二次

盤數

0

0

0

0

0

0

0

5

6

7

8

9

10

11

12

13

14

15

15

15

15

次數

0

0

0

0

0

0

0

9

13

17

21

25

29

33

37

41

45

49

49

49

49

最低次數

0

1

3

5

7

9

11

15

19

23

27

31

35

39

43

47

51

55

59

63

67

增加次數

0

1

2

2

2

2

2

4

4

4

4

4

4

4

4

4

4

4

4

4

4

top

v    八根柱子(*)

盤子數

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

八柱

第一次

盤數

0

1

2

3

4

5

6

7

2

3

4

5

6

7

7

7

7

7

7

7

7

次數

0

1

3

5

7

9

11

13

3

5

7

9

11

13

13

13

13

13

13

13

13

七柱

第二次

盤數

0

0

0

0

0

0

0

0

6

6

6

6

6

6

7

8

9

10

11

12

13

次數

0

0

0

0

0

0

0

0

11

11

11

11

11

11

15

19

23

27

31

35

39

最低次數

0

1

3

5

7

9

11

13

17

21

25

29

33

37

41

45

49

53

57

61

65

增加次數

0

1

2

3

2

2

2

2

4

4

4

4

4

4

4

4

4

4

4

4

4

*本程式最高到八根柱子。

top

v    不同柱子數之盤數的最低移動次數總表

盤子數

柱子數

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

3

0

1

3

7

15

31

63

127

255

511

1023

2045

4091

8183

2n-1

4

0

1

3

5

9

13

17

25

33

41

49

65

81

97

113

129

161

193

225

257

289

5

0

1

3

5

7

11

15

19

23

27

31

39

47

55

63

71

79

87

95

103

111

6

0

1

3

5

7

9

13

17

21

25

29

33

37

41

45

49

57

65

73

81

89

7

0

1

3

5

7

9

11

15

19

23

27

31

35

39

43

47

51

55

59

63

67

8

0

1

3

5

7

9

11

13

17

21

25

29

33

37

41

45

49

53

57

61

65

top

v    不同柱子數之隨盤子數量增加而增加的移動次數總表

盤子數

柱子數

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

3

0

1

2

4

8

16

32

64

128

256

512

1024

2048

4096

2n-1

4

0

1

2

3

4

4

4

8

8

8

8

16

16

16

16

16

32

32

32

32

32

5

0

1

2

2

2

4

4

4

4

4

4

8

8

8

8

8

8

8

8

8

8

6

0

1

2

2

2

2

4

4

4

4

4

4

4

4

4

4

8

8

8

8

8

7

0

1

2

2

2

2

2

4

4

4

4

4

4

4

4

4

4

4

4

4

4

8

0

1

2

3

2

2

2

2

4

4

4

4

4

4

4

4

4

4

4

4

4

top

v     不同柱數之盤數分解對照表

盤子數

柱子數

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

3

0

0

1

0

2

0

2

1

3

1

4

1

5

1

6

1

7

1

8

1

9

1

10

1

11

1

12

1

13

1

14

1

15

1

16

1

17

1

18

1

19

1

4

0

0

1

0

2

0

3

0

2

2

3

2

3

3

3

4

5

3

5

4

6

4

7

4

7

5

8

5

9

5

10

5

11

5

12

5

12

6

13

6

14

6

5

0

0

1

0

2

0

3

0

4

0

2

3

2

4

2

5

2

6

3

6

4

6

4

7

4

8

4

9

4

10

5

10

6

10

7

10

8

10

9

10

10

10

6

0

0

1

0

2

0

3

0

4

0

5

0

2

4

3

4

4

4

5

4

5

5

5

6

5

7

5

8

5

9

5

10

5

11

5

12

5

13

5

14

5

15

7

0

0

1

0

2

0

3

0

4

0

5

0

6

0

2

5

2

6

2

7

2

8

2

9

2

10

2

11

2

12

2

13

2

14

2

15

3

15

4

15

5

15

8

0

0

1

0

2

0

3

0

4

0

5

0

6

0

7

0

2

6

3

6

4

6

5

6

6

6

7

6

7

7

7

8

7

9

7

10

7

11

7

12

7

13

top