汉诺塔来源及应用

相传在古印度圣庙中，有一种被称为汉诺塔(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>