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
4k
ハノイの塔問題の解法をできるだけわかりやすく解説
再帰関数を使うプログラミング問題としても有名なハノイの塔をなるべくわかりやすいよう解説
https://twitter.com/nekonenene
ハトネコエ
March 29, 2017
Tweet
Share
More Decks by ハトネコエ
See All by ハトネコエ
日経が読める?! 株式市場の基礎 / Stock Market Basics
nekonenene
0
25
プルリクエストレビューを終わらせるためのチーム体制 / The Team for Completing Pull Request Reviews
nekonenene
4
2.8k
今年こそ知るべきセキュリティー入門 / Security Basics 2025
nekonenene
0
55
Godot 4.3 と学ぶインタラクティブミュージック / Interactive Music Basics with Godot 4.3
nekonenene
0
150
Developer Consoleを使い倒そう / Use Web Browser DevTools
nekonenene
0
44
まだまだマイナー?! 未踏事業について教えます / Introduction of Mitou Project
nekonenene
1
140
Docker for Windows/macOS
nekonenene
0
34
技術的負債を防ぐには / What is the Technical Debt
nekonenene
0
340
画像処理の基礎の基礎 / Ultra Basic of Image Processing
nekonenene
0
53
Other Decks in Technology
See All in Technology
我々は雰囲気で仕事をしている / How can we do vibe coding as well
naospon
2
220
人を動かすことについて考える
ichimichi
2
320
TypeScript入門
recruitengineers
PRO
8
1.5k
Goss: Faiss向けの新しい本番環境対応 Goバインディング #coefl_go_jp
bengo4com
0
1.4k
攻撃と防御で実践するプロダクトセキュリティ演習~導入パート~
recruitengineers
PRO
1
140
Amazon Bedrock AgentCore でプロモーション用動画生成エージェントを開発する
nasuvitz
6
420
Goでマークダウンの独自記法を実装する
lag129
0
210
mruby(PicoRuby)で ファミコン音楽を奏でる
kishima
1
220
サービスロボット最前線:ugoが挑むPhysical AI活用
kmatsuiugo
0
190
KiroでGameDay開催してみよう(準備編)
yuuuuuuu168
1
130
Gaze-LLE: Gaze Target Estimation via Large-Scale Learned Encoders
kzykmyzw
0
310
Browser
recruitengineers
PRO
3
260
Featured
See All Featured
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
30
9.6k
KATA
mclloyd
32
14k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
4k
A Tale of Four Properties
chriscoyier
160
23k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
139
34k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
229
22k
Docker and Python
trallard
45
3.5k
Designing Experiences People Love
moore
142
24k
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.6k
How STYLIGHT went responsive
nonsquared
100
5.7k
VelocityConf: Rendering Performance Case Studies
addyosmani
332
24k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
9
780
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 こういう易しいテーマでかまいません、 ぜひ皆様ご登壇ください