最近、気温の差が大きく、着る服に悩んでいますTOSHです...
今回は、Swiftでハノイの塔のプログラムを描いてみようと思い、書いてみることにしました！
ハノイの塔のプログラムは、再帰の考えを用いたとてもシンプルなものなのですが、再帰を使っているぶん、コードを読んで、何が起こっているのかを理解するのは、意外と難しいです!!!
ハノイの塔とは
・三本の杭と、任意の枚数の円盤位よって構成される。
・はじめ、円盤は、全て、左端に下から大きい順に並べられてある
・一回に一枚動かすことができ、左端から、別の食いへと動かすことができれば成功
・ただし、小さい円盤の上に、大きな円盤を置くことはできない
・2^n - 1の手順で動かすことができる
ハノイの塔のプログラム
ViewController.swift
class ViewController: UIViewController {
var number: Int = 3
var total: Int = 0
override func viewDidLoad() {
super.viewDidLoad()
hanoi(num: number, from: "Left", dst: "Center", work: "Right")
print("Total is \(total)!")
}
func hanoi(num:Int, from: String, dst: String, work: String){
if num > 0{
// この文を①とする
hanoi(num: num - 1, from: from, dst: work, work: dst)
printer(b: from, c: dst)
// この文を②とする
hanoi(num: num - 1, from: work, dst: dst, work: from)
}
}
func printer(b: String, c: String){
total = total + 1
print("\(total): 棒", b, "から棒", c,"へ移動")
}
}
実行結果
解説
一言で言えば、再帰を使っているのは明白なのですが再帰を使うとなぜプログラムができるのかというのを苦労するのにとても苦労しました。
理解する上で、参考にしたサイトをここに載せておきます。 here!
円盤が三本の時について考えてみましょう。
まず、最初のこの状態から
この状態へ変化させるためには、
必ずこの状態を経由しなければなりません。
そして、今Aにある一番大きな円盤がCに移動した時、一番大きな円盤を無視でき、残るはn-1枚(この場合は2枚)の円盤を一番大きな円盤が刺さっている（つまりC）へ動かせばいいと考えることができる。つまりこの時n枚の円盤の移動問題はn-1枚に変わったと考えることができる。これを繰り返していくことで、ハノイの塔は解くことができる。
うーん、ややこしい笑
うまく書けていない気がするので、もっと理解が深まったら随時更新していく予定です...