汉诺塔来源及应用
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
图1：汉诺塔问题图示
分析：对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，但我们可以利用下面的方法来解决。设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：
(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；
(2)将A杆中剩下的第n号盘移至C杆；
(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。
以上摘抄自百度百科汉诺塔问题
Swift实现汉诺塔问题移动过程
直接上代码以及备注，我是在Playground上直接写的
print("汉诺塔问题，需要3个可移动盘子的柱子，那么初始需要定义3个可变数组A，B，C")
print("汉诺塔问题中盘子从小到大依次在A柱子上，那么对应数组中前元素比后元素大")
var A = [5,4,3,2,1]//举例A柱子上有5个盘子
var B : Array<Int> = []
var C : Array<Int> = []
enum Tower:String{
case A = "A"
case B = "B"
case C = "C"
}
func hanoiMove(_ x : Tower,_ z : Tower){
var xValue : Int? = nil
switch x {
case .A:
• xValue = A.last;
• A.removeLast()
• break
case .B:
• xValue = B.last;
• B.removeLast()
• break
case .C:
• xValue = C.last
• C.removeLast()
• break
}
if let value = xValue {
• switch z {
• case .A:
• A.append(value)
• break
• case .B:
• B.append(value)
• break
• case .C:
• C.append(value)
• break
• }
•
}
print("编号\(xValue ?? 0)的盘子从\(x.rawValue)移动到\(z.rawValue)\nA:\(A)\nB:\(B)\nC:\(C)")
}
func hanoi(_ n:Int,_ x:Tower,_ y:Tower,_ z:Tower){
if n == 1 {
• //当n==1的时候，说明x柱子上只有1个盘子，那么直接从x柱子移动到z柱子上
• hanoiMove(x, z)
}else{
• //将n-1个盘子从x柱子借助z柱子移动到y柱子上：此时x柱子还有最后一个盘子(编号为n的盘子)，y柱子有n-1个盘子，z柱子上是空柱子
• hanoi(n-1, x, z, y)
• //此时可以直接将x柱子上最后1个盘子直接移动到z柱子上
• hanoiMove(x, z)
• //将y柱子上的n-1个盘子，再借助此时的空柱子x，移动到z柱子上
• hanoi(n-1, y, x, z)
}
}
print("汉诺塔初始状态\nA:\(A)\nB:\(B)\nC:\(C)")
print("把A柱子上的盘子经由B柱子全部移动到C柱子上移动汉诺塔过程如下")
hanoi(A.count, .A, .B, .C)//A.count A柱子上的所有盘子经由B柱子移动到C柱子上
print("至此汉诺塔移动完成\nA:\(A)\nB:\(B)\nC:\(C)")</pre>
网友评论