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.9k
ハノイの塔問題の解法をできるだけわかりやすく解説
再帰関数を使うプログラミング問題としても有名なハノイの塔をなるべくわかりやすいよう解説
https://twitter.com/nekonenene
ハトネコエ
March 29, 2017
Tweet
Share
More Decks by ハトネコエ
See All by ハトネコエ
プルリクエストレビューを終わらせるためのチーム体制 / The Team for Completing Pull Request Reviews
nekonenene
4
2.7k
今年こそ知るべきセキュリティー入門 / Security Basics 2025
nekonenene
0
44
Godot 4.3 と学ぶインタラクティブミュージック / Interactive Music Basics with Godot 4.3
nekonenene
0
120
Developer Consoleを使い倒そう / Use Web Browser DevTools
nekonenene
0
35
まだまだマイナー?! 未踏事業について教えます / Introduction of Mitou Project
nekonenene
1
130
Docker for Windows/macOS
nekonenene
0
25
技術的負債を防ぐには / What is the Technical Debt
nekonenene
0
320
画像処理の基礎の基礎 / Ultra Basic of Image Processing
nekonenene
0
41
伝わる文章を書こう講座 / Write the Kind Japanese Message
nekonenene
2
150
Other Decks in Technology
See All in Technology
DevOpsDays Taipei 2025 -- Creating Awesome Change in SmartNews!
martin_lover
0
160
KMP導⼊において、マネジャーとして考えた事
sansantech
PRO
1
210
LT:組込み屋さんのオシロが壊れた!
windy_pon
0
460
CSS polyfill とその未来
ken7253
0
140
Bill One 開発エンジニア 紹介資料
sansan33
PRO
4
12k
令和トラベルQAのAI活用
seigaitakahiro
0
520
Cursor Meetup Tokyo
iamshunta
2
660
GitHub Coding Agent 概要
kkamegawa
1
1.7k
Data Hubグループ 紹介資料
sansan33
PRO
0
1.7k
RDRA3.0を知ろう
kanzaki
2
430
All About Sansan – for New Global Engineers
sansan33
PRO
1
1.2k
ソフトウェアテストのAI活用_ver1.10
fumisuke
0
240
Featured
See All Featured
Fireside Chat
paigeccino
37
3.5k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
Site-Speed That Sticks
csswizardry
7
590
Building Adaptive Systems
keathley
41
2.6k
Why Our Code Smells
bkeepers
PRO
336
57k
Mobile First: as difficult as doing things right
swwweet
223
9.6k
Java REST API Framework Comparison - PWX 2021
mraible
31
8.6k
Product Roadmaps are Hard
iamctodd
PRO
53
11k
Building Better People: How to give real-time feedback that sticks.
wjessup
368
19k
Reflections from 52 weeks, 52 projects
jeffersonlam
349
20k
The Art of Programming - Codeland 2020
erikaheidi
54
13k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
160
15k
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 こういう易しいテーマでかまいません、 ぜひ皆様ご登壇ください