Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
ハノイの塔問題の解法をできるだけわかりやすく解説
Search
ハトネコエ
March 29, 2017
Technology
0
3.5k
ハノイの塔問題の解法をできるだけわかりやすく解説
再帰関数を使うプログラミング問題としても有名なハノイの塔をなるべくわかりやすいよう解説
https://twitter.com/nekonenene
ハトネコエ
March 29, 2017
Tweet
Share
More Decks by ハトネコエ
See All by ハトネコエ
Godot 4.3 と学ぶインタラクティブミュージック / Interactive Music Basics with Godot 4.3
nekonenene
0
33
Developer Consoleを使い倒そう / Use Web Browser DevTools
nekonenene
0
4
まだまだマイナー?! 未踏事業について教えます / Introduction of Mitou Project
nekonenene
1
89
Docker for Windows/macOS
nekonenene
0
5
技術的負債を防ぐには / What is the Technical Debt
nekonenene
0
290
画像処理の基礎の基礎 / Ultra Basic of Image Processing
nekonenene
0
21
伝わる文章を書こう講座 / Write the Kind Japanese Message
nekonenene
2
140
Unity で Android 自動ビルドしたかった話 / I tried Android build of Unity using Docker, but...
nekonenene
0
2.1k
これでわかるB-treeアルゴリズム / B-tree algorithm
nekonenene
12
9.7k
Other Decks in Technology
See All in Technology
20241120_JAWS_東京_ランチタイムLT#17_AWS認定全冠の先へ
tsumita
2
300
CysharpのOSS群から見るModern C#の現在地
neuecc
2
3.5k
リンクアンドモチベーション ソフトウェアエンジニア向け紹介資料 / Introduction to Link and Motivation for Software Engineers
lmi
4
300k
Lambdaと地方とコミュニティ
miu_crescent
2
370
適材適所の技術選定 〜GraphQL・REST API・tRPC〜 / Optimal Technology Selection
kakehashi
1
690
OCI Security サービス 概要
oracle4engineer
PRO
0
6.5k
AWS Media Services 最新サービスアップデート 2024
eijikominami
0
200
Amazon CloudWatch Network Monitor のススメ
yuki_ink
1
210
AGIについてChatGPTに聞いてみた
blueb
0
130
The Role of Developer Relations in AI Product Success.
giftojabu1
0
130
ExaDB-D dbaascli で出来ること
oracle4engineer
PRO
0
3.9k
Application Development WG Intro at AppDeveloperCon
salaboy
0
190
Featured
See All Featured
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
280
13k
Designing for humans not robots
tammielis
250
25k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
329
21k
Being A Developer After 40
akosma
87
590k
Building an army of robots
kneath
302
43k
How GitHub (no longer) Works
holman
310
140k
Making Projects Easy
brettharned
115
5.9k
What's in a price? How to price your products and services
michaelherold
243
12k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
169
50k
Imperfection Machines: The Place of Print at Facebook
scottboms
265
13k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
246
1.3M
Raft: Consensus for Rubyists
vanstee
136
6.6k
Transcript
ϋτωίΤ ハノイの塔の解き方を 解説してみる @nekonenene
ࣗݾհ ハトネコエ • Twitter : @nekonenene https://twitter.com/nekonenene • Github :
nekonenene • ミクさんかわいい!!!!!!
લஔ͖ ハノイの塔とは?
ϋϊΠͷౝ フランスの数学者 エドゥアール・リュカが 考案したパズル。 より大きい円盤は上に置けない というルールを守りつつ、 1枚ずつ円盤を動かし、 すべての円盤を異なる柱へ移動
ϋϊΠͷౝ プログラミングの世界では、 X枚からなるハノイの塔を解く 最短手数Yを求めるプログラムが、 「再帰関数」を使う プログラミング問題の定番として あったりする。
けっこうむずかしい。 解答読んでもわからなかった ͚ͩͲ
出力→ ↑コード(Kotlin)
↑今回はそれを解説 なんで解けるの?!
小さい問題を手動で解き 法則をつかみます ·ͣखಈ
̍ຕ൛ なお、左端の柱から右端の柱へ運ぶものとします Q
̍ຕ൛ なお、左端の柱から右端の柱へ運ぶものとします A 簡単ですが、実は意外と大事です
ϙΠϯτ ̍ ハノイの塔1枚版は ゴールへ移動させるだけ
̎ຕ൛ 真ん中の柱が役立ちます Q
̎ຕ൛ A1 真ん中の柱が役立ちます
̎ຕ൛ A2 真ん中の柱が役立ちます
̎ຕ൛ A3 真ん中の柱が役立ちます
̎ຕ൛ɿࣦഊ 先に右端に運んだ場合 Q
̎ຕ൛ɿࣦഊ 先に右端に運んだ場合 A1 一番下の円盤を真ん中にしか運べなくなる
ϙΠϯτ ̎ 円盤を動かしたあと その下にいた円盤の移動先は1通りだけ
̏ຕ൛ɿࣦഊ 成功した2枚版同様、最初に真ん中に運んでみよう Q
̏ຕ൛ɿࣦഊ 成功した2枚版同様、最初に真ん中に運んでみよう A1
̏ຕ൛ɿࣦഊ 成功した2枚版同様、最初に真ん中に運んでみよう A2
̏ຕ൛ɿࣦഊ 成功した2枚版同様、最初に真ん中に運んでみよう A3 一番下の円盤を真ん中にしか運べなくなる
Ͳ͏͔͔ͨͬͨ͠ʁ より大きな円盤は上に置けないから、 一番大きな円盤から先に目的地に運びたかった
͜ͷܗ࣮ 出発地点が変わったハノイの塔2枚版 出発地 ゴール
ϙΠϯτ ̏ ハノイの塔3枚版を解く過程で ハノイの塔2枚版を解く
̐ຕ൛ಉ༷ 「どんな形にしたいか」で考えてみる Q 出発地 ゴール
̐ຕ൛ಉ༷ 「どんな形にしたいか」で考えてみる A1 出発地 ゴール
̐ຕ൛ಉ༷ 「どんな形にしたいか」で考えてみる A2 出発地 ゴール 3枚版の形に
̐ຕ൛ಉ༷ 「どんな形にしたいか」で考えてみる A3 出発地 ゴール
̐ຕ൛ಉ༷ 「どんな形にしたいか」で考えてみる A4 出発地 ゴール 2枚版の形に
̐ຕ൛ಉ༷ 「どんな形にしたいか」で考えてみる A5 出発地 ゴール
̐ຕ൛ಉ༷ 「どんな形にしたいか」で考えてみる A6 出発地 ゴール 1枚版の形に
̐ຕ൛ಉ༷ 「どんな形にしたいか」で考えてみる A7 出発地 ゴール 1枚版は ゴールに 円盤を 動かすだけ
ϙΠϯτ ̐ 出発地点を変えつつ 1枚少ない版のハノイの塔を解く イメージ
ϙΠϯτ·ͱΊ • X枚版のハノイの塔は、 出発地点の異なるX-1枚版のハノイの塔を 解決することで攻略できる • ハノイの塔1枚版は ゴールへ移動させるだけ • 最短手数を求めるとき、
より大きな円盤の移動手段が限定されること、 X-1枚版のハノイの塔を攻略することから 1通りの動かし方しかないとわかる
これらを踏まえて コードを改めて読んでみよう ίʔυಡΈ
େ·͔ͳྲྀΕ 出発地 ゴール ハノイの塔4枚版で見る 大まかな流れ
େ·͔ͳྲྀΕ 出発地 ゴール 出発地 ゴール 上3枚を移動させ 最下段の1枚を 移動する旨プリント
େ·͔ͳྲྀΕ 出発地 ゴール 出発地を変え ハノイの塔3枚版を 解き始める
出発地 ゴール ̎ຕ൛ͰͷྲྀΕ(1) ハノイの塔2枚版で 実際の流れを 追ってみよう!
̎ຕ൛ͰͷྲྀΕ(2) 関数呼び出しで、 左図のハノイの塔を 解くように指示 出発地 ゴール
̎ຕ൛ͰͷྲྀΕ(3) 呼び出された側は discNumber = 1 だから、 println の行だけ実行 「1をAからBへ」 と出力
出発地 ゴール
出発地 ゴール ̎ຕ൛ͰͷྲྀΕ(4) 関数呼び出しが終わり、 呼び出し元も println 行の処理 「2をAからCへ」 と出力
̎ຕ൛ͰͷྲྀΕ(5) 関数呼び出しで、 左図のハノイの塔を 解くように指示 出発地 ゴール
̎ຕ൛ͰͷྲྀΕ(6) 呼び出された側は discNumber = 1 だから、 println の行だけ実行 「1をBからCへ」 と出力
出発地 ゴール
出発地 ゴール ̎ຕ൛ͰͷྲྀΕ(7) 関数呼び出しが終わり、 処理終了。 3枚版, 4枚版も、 規模は大きいが根本的には同様
·ͱΊ どうして解けるか わかったけど難しい!!
Thanks 解答コードの参考 • ハノイの塔を攻略せよ!【Windowsプログラミング研究 所】 http://www13.plala.or.jp/kymats/study/C++/Hanoi/ Hanoi.html こういう易しいテーマでかまいません、 ぜひ皆様ご登壇ください