Go-求解汉诺塔游戏【递归函数&栈】两种方式

烟汐忆梦

先去看递回函数的方法：

1. /*
2. *                    .::::.
3. *                  .::::::::.
4. *                 :::::::::::
5. *             ..:::::::::::'
6. *           '::::::::::::'
7. *             .::::::::::
8. *        '::::::::::::::..
9. *             ..::::::::::::.                Utils:递回函数供解汉诺塔游戏
10. *           ``::::::::::::::::                Author:崔金朋
11. *            ::::``:::::::::'        .:::.
12. *           ::::'   ':::::'       .::::::::.
13. *         .::::'      ::::     .:::::::'::::.
14. *        .:::'       :::::  .:::::::::' ':::::.
15. *       .::'        :::::.:::::::::'      ':::::.
16. *      .::'         ::::::::::::::'         ``::::.
17. *  ...:::           ::::::::::::'              ``::.
18. * ```` ':.          ':::::::::'                  ::::..
19. *                             '.:::::'                                  ':'````..
20. */
22. package main
24. import (
25.         "fmt"
26.         "strconv"
27. )
29. func Hannoi(num int, left, middle, right, from, to string) int {
30.         if num < 1 {
31.                 return 0
32.         }
34.         return Process(num, left, middle, right, from, to)
35. }
37. func Process(num int, left, middle, right, from, to string) int {
38.         if num == 1 {
39.                 if from == middle || to == middle {
40.                         step := "Move 1 from " + from + " to " + to
41.                         fmt.Println(step)
42.                         return 1
43.                 } else {
44.                         step1 := "Move 1 from " + from + " to " + middle
45.                         step2 := "Move 1 from " + middle + " to " + to
46.                         fmt.Println(step1)
47.                         fmt.Println(step2)
48.                         return 2
49.                 }
50.         }
52.         if from == middle || to == middle {
53.                 var another string
54.                 if from == left || to == left {
55.                         another = left
56.                 } else {
57.                         another = right
58.                 }
60.                 part1 := Process(num-1, left, middle, right, from, another)
61.                 part2 := 1
62.                 step := "Move " + strconv.Itoa(num) + " from " + from + " to " + to
63.                 fmt.Println(step)
64.                 part3 := Process(num-1, left, middle, right, another, to)
65.                 return part1 + part2 + part3
66.         }
68.         part1 := Process(num-1, left, middle, right, from, to)
69.         part2 := 1
70.         step1 := "Move " + strconv.Itoa(num) + " from " + from + " to " + middle
71.         fmt.Println(step1)
72.         part3 := Process(num-1, left, middle, right, to, from)
73.         part4 := 1
74.         step2 := "Move " + strconv.Itoa(num) + " from " + middle + " to " + to
75.         fmt.Println(step2)
76.         part5 := Process(num-1, left, middle, right, from, to)
77.         return part1 + part2 + part3 + part4 + part5
78. }

复造代码

接下去是栈的方法：

1. /*
2. *                    .::::.
3. *                  .::::::::.
4. *                 :::::::::::
5. *             ..:::::::::::&#39;
6. *           &#39;::::::::::::&#39;
7. *             .::::::::::
8. *        &#39;::::::::::::::..
9. *             ..::::::::::::.                Utils:栈供解汉诺塔游戏
10. *           ``::::::::::::::::                Author:崔金朋
11. *            ::::``:::::::::&#39;        .:::.
12. *           ::::&#39;   &#39;:::::&#39;       .::::::::.
13. *         .::::&#39;      ::::     .:::::::&#39;::::.
14. *        .:::&#39;       :::::  .:::::::::&#39; &#39;:::::.
15. *       .::&#39;        :::::.:::::::::&#39;      &#39;:::::.
16. *      .::&#39;         ::::::::::::::&#39;         ``::::.
17. *  ...:::           ::::::::::::&#39;              ``::.
18. * ```` &#39;:.          &#39;:::::::::&#39;                  ::::..
19. *                             &#39;.:::::&#39;                                  &#39;:&#39;````..
20. */
22. package main
24. import (
25.         "fmt"
26.         "strconv"
27. )
29. const (
30.         Number = iota
31.         LeftToMiddle
32.         MiddleToLeft
33.         RightToMiddle
34.         MiddleToRight
35. )
37. type HannoiStack struct {
38.         LeftStack   CommonStack
39.         MiddleStack CommonStack
40.         RightStack  CommonStack
41. }
43. func (h *HannoiStack) HannoiGame(num int, left, middle, right string) interface{} {
44.         h.LeftStack.CommonPush(32164)
45.         h.MiddleStack.CommonPush(32164)
46.         h.RightStack.CommonPush(32164)
47.         for i := num; i > 0; i-- {
48.                 h.LeftStack.CommonPush(i)
49.         }
51.         retcord := []int{Number}
52.         step := 0
53.         for h.RightStack.CommonLen() != num+1 {
54.                 step += h.ToStack(retcord, MiddleToLeft, LeftToMiddle, left, middle, right, left, middle)
55.                 step += h.ToStack(retcord, LeftToMiddle, MiddleToLeft, left, middle, right, middle, left)
56.                 step += h.ToStack(retcord, RightToMiddle, MiddleToRight, left, middle, right, middle, right)
57.                 step += h.ToStack(retcord, MiddleToRight, RightToMiddle, left, middle, right, right, middle)
58.         }
60.         return step
61. }
63. func (h *HannoiStack) ToStack(retcord []int, pre, now int, left, middle, right, from, to string) int {
64.         fromNum := h.HannoiPeek(from, left, middle, right)
65.         toNum := h.HannoiPeek(to, left, middle, right)
66.         if retcord[0] != pre && fromNum < toNum {
67.                 fromElement := h.HannoiPop(from, left, middle, right)
68.                 h.HannoiPush(to, left, middle, right, fromElement)
69.                 toEle := h.HannoiPeek(to, left, middle, right)
70.                 fmt.Println("Move " + strconv.Itoa(toEle) + " from " + from + " to " + to)
71.                 retcord[0] = now
72.                 return 1
73.         }
75.         return 0
76. }
78. func (h *HannoiStack) HannoiPeek(item, left, middle, right string) int {
79.         if item == left {
80.                 element, _ := h.LeftStack.CommonPeek()
81.                 return element.(int)
82.         }
84.         if item == middle {
85.                 element, _ := h.MiddleStack.CommonPeek()
86.                 return element.(int)
87.         }
89.         if item == right {
90.                 element, _ := h.RightStack.CommonPeek()
91.                 return element.(int)
92.         }
94.         return 0
95. }
97. func (h *HannoiStack) HannoiPop(item, left, middle, right string) int {
98.         if item == left {
99.                 element, _ := h.LeftStack.CommonPop()
100.                 return element.(int)
101.         }
103.         if item == middle {
104.                 element, _ := h.MiddleStack.CommonPop()
105.                 return element.(int)
106.         }
108.         if item == right {
109.                 element, _ := h.RightStack.CommonPop()
110.                 return element.(int)
111.         }
113.         return 0
114. }
116. func (h *HannoiStack) HannoiPush(item, left, middle, right string, pushItem int) bool {
117.         if item == left {
118.                 h.LeftStack.CommonPush(pushItem)
119.                 return true
120.         }
122.         if item == middle {
123.                 h.MiddleStack.CommonPush(pushItem)
124.                 return true
125.         }
127.         if item == right {
128.                 h.RightStack.CommonPush(pushItem)
129.                 return true
130.         }
132.         return false
133. }

复造代码

免责声明：假如进犯了您的权益，请联络站少，我们会实时删除侵权内乱容，感谢协作！