Programming Practice

使用堆疊 (stack) 運算寫一個河內塔 (tower of Hanoi) 的專案程式。河內塔的問題描述如課程教材所示。

在本程式中,你需宣告為三個堆疊來代表三根柱子。主程式步驟及重點:

  1. 先讀入一個在 1 12 之間的正整數 n 並設定第一根柱子之堆疊的起始狀態,即 push n 個數字 ( n 遞減至 1) 到堆疊,底部元素為 n,頭部元素為 1。 每一個數字代表一個盤子的半徑。 輸出三根柱子的起始狀態。

  2. 執行河內塔的運算,在每一移動步驟後輸出三根柱子的即時狀態。每根柱子的狀態輸出為自下而上的盤子順序。

  3. 你可寫一個函式來輸出三根柱子的狀態,這個函式的介面為 void printPegs(stack *ppeg1, stack *ppeg2, stack *ppeg3)

  4. 河內塔的副程式為 void hanoi(int n, stack *sour, stack *aux, stack *dest, stack *ppeg1, stack *ppeg2, stack *ppeg3),盤子的移動需使用堆疊運算執行 。

堆疊運算可使用 hanoi_stack_array.h hanoi_stack_array.c 中的函式。以下為河內塔的執行範例:

Please enter the number of disks: 4

Initial pegs:

Peg A: 4 3 2 1
Peg B:
Peg C:

**********************************************
>>>> Step 1: Move disk 1 from Peg A to Peg B

Peg A: 4 3 2
Peg B: 1
Peg C:

**********************************************
>>>> Step 2: Move disk 2 from Peg A to Peg C

Peg A: 4 3
Peg B: 1
Peg C: 2

**********************************************
>>>> Step 3: Move disk 1 from Peg B to Peg C

Peg A: 4 3
Peg B:
Peg C: 2 1

**********************************************
>>>> Step 4: Move disk 3 from Peg A to Peg B

Peg A: 4
Peg B: 3
Peg C: 2 1

**********************************************
>>>> Step 5: Move disk 1 from Peg C to Peg A

Peg A: 4 1
Peg B: 3
Peg C: 2

**********************************************
>>>> Step 6: Move disk 2 from Peg C to Peg B

Peg A: 4 1
Peg B: 3 2
Peg C:

**********************************************
>>>> Step 7: Move disk 1 from Peg A to Peg B

Peg A: 4
Peg B: 3 2 1
Peg C:

**********************************************
>>>> Step 8: Move disk 4 from Peg A to Peg C

Peg A:
Peg B: 3 2 1
Peg C: 4

**********************************************
>>>> Step 9: Move disk 1 from Peg B to Peg C

Peg A:
Peg B: 3 2
Peg C: 4 1

**********************************************
>>>> Step 10: Move disk 2 from Peg B to Peg A

Peg A: 2
Peg B: 3
Peg C: 4 1

**********************************************
>>>> Step 11: Move disk 1 from Peg C to Peg A

Peg A: 2 1
Peg B: 3
Peg C: 4

**********************************************
>>>> Step 12: Move disk 3 from Peg B to Peg C

Peg A: 2 1
Peg B:
Peg C: 4 3

**********************************************
>>>> Step 13: Move disk 1 from Peg A to Peg B

Peg A: 2
Peg B: 1
Peg C: 4 3

**********************************************
>>>> Step 14: Move disk 2 from Peg A to Peg C

Peg A:
Peg B: 1
Peg C: 4 3 2

**********************************************
>>>> Step 15: Move disk 1 from Peg B to Peg C

Peg A:
Peg B:
Peg C: 4 3 2 1

Finish!!!