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
31
Developer Consoleを使い倒そう / Use Web Browser DevTools
nekonenene
0
4
まだまだマイナー?! 未踏事業について教えます / Introduction of Mitou Project
nekonenene
1
86
Docker for Windows/macOS
nekonenene
0
4
技術的負債を防ぐには / What is the Technical Debt
nekonenene
0
290
画像処理の基礎の基礎 / Ultra Basic of Image Processing
nekonenene
0
20
伝わる文章を書こう講座 / Write the Kind Japanese Message
nekonenene
2
130
Unity で Android 自動ビルドしたかった話 / I tried Android build of Unity using Docker, but...
nekonenene
0
2k
これでわかるB-treeアルゴリズム / B-tree algorithm
nekonenene
12
9.7k
Other Decks in Technology
See All in Technology
[JAWS-UG金沢支部×コンテナ支部合同企画]コンテナとは何か
furuton
3
250
ユーザーの購買行動モデリングとその分析 / dsc-purchase-analysis
cyberagentdevelopers
PRO
2
100
2024-10-30-reInventStandby_StudyGroup_Intro
shinichirokawano
1
630
大規模データ基盤チームのオンプレTiDB運用への挑戦 / dpu-tidb
cyberagentdevelopers
PRO
1
110
来年もre:Invent2024 に行きたいあなたへ - “集中”と“つながり”で楽しむ -
ny7760
0
470
急成長中のWINTICKETにおける品質と開発スピードと向き合ったQA戦略と今後の展望 / winticket-autify
cyberagentdevelopers
PRO
1
160
チームを主語にしてみる / Making "Team" the Subject
ar_tama
4
310
生成AIと知識グラフの相互利用に基づく文書解析
koujikozaki
1
140
신뢰할 수 있는 AI 검색 엔진을 만들기 위한 Liner의 여정
huffon
0
340
プロダクトチームへのSystem Risk Records導入・運用事例の紹介/Introduction and Case Studies on Implementing and Operating System Risk Records for Product Teams
taddy_919
1
170
WINTICKETアプリで実現した高可用性と高速リリースを支えるエコシステム / winticket-eco-system
cyberagentdevelopers
PRO
1
190
新卒1年目が向き合う生成AI事業の開発を加速させる技術選定 / ai-web-launcher
cyberagentdevelopers
PRO
7
1.5k
Featured
See All Featured
A designer walks into a library…
pauljervisheath
202
24k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
131
33k
Building a Scalable Design System with Sketch
lauravandoore
459
33k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
228
52k
GraphQLの誤解/rethinking-graphql
sonatard
66
9.9k
How To Stay Up To Date on Web Technology
chriscoyier
788
250k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.2k
Unsuck your backbone
ammeep
668
57k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
14
1.9k
GraphQLとの向き合い方2022年版
quramy
43
13k
The Cost Of JavaScript in 2023
addyosmani
45
6.6k
The Art of Programming - Codeland 2020
erikaheidi
51
13k
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 こういう易しいテーマでかまいません、 ぜひ皆様ご登壇ください