回答編集履歴
4
画像を追加
test
CHANGED
|
@@ -230,4 +230,8 @@
|
|
|
230
230
|
|
|
231
231
|
|
|
232
232
|
|
|
233
|
-
再帰呼出はループではありませんが、再帰呼出することはループの繰り返しと同じことをし
|
|
233
|
+
再帰呼出はループではありませんが、再帰呼出することはループの繰り返しと同じことをします。再帰呼出ししなければループ終了と同じ。hanoi()では n=1 の時再帰しません。
|
|
234
|
+
|
|
235
|
+
|
|
236
|
+
|
|
237
|
+
|
3
再帰呼出の解説
test
CHANGED
|
@@ -199,3 +199,35 @@
|
|
|
199
199
|
=> nil
|
|
200
200
|
|
|
201
201
|
```
|
|
202
|
+
|
|
203
|
+
|
|
204
|
+
|
|
205
|
+
### 追記（再帰呼出の解説）
|
|
206
|
+
|
|
207
|
+
|
|
208
|
+
|
|
209
|
+
** 再帰呼出の動作**
|
|
210
|
+
|
|
211
|
+
|
|
212
|
+
|
|
213
|
+
再帰呼出しとはメソッド(hanoi)の中から自分自身(hanoi)を呼ぶことです。これは、自分自身を呼ぶことを除けば、普通のメソッド呼出しと同じです。メソッド呼出しの動作は以下のとおり。
|
|
214
|
+
|
|
215
|
+
- def hanoiの(…)の括弧の中に記述されているのが引数です。n, from, to, viaです。
|
|
216
|
+
|
|
217
|
+
- 引数に値を設定（代入）してメソッドに渡すと引数のコピーが作られます。
|
|
218
|
+
|
|
219
|
+
呼ばれたメソッドはコピーの値しか見えません。
|
|
220
|
+
|
|
221
|
+
- 呼ばれたメソッドは引数の値を使って処理を実行します。
|
|
222
|
+
|
|
223
|
+
hanoi()では原則に従い n=1 かそれ以外 (n≠1) かで処理が異なります。
|
|
224
|
+
|
|
225
|
+
- 処理が終わってメソッドからリターンする時に引数のコピーは消滅します。
|
|
226
|
+
|
|
227
|
+
|
|
228
|
+
|
|
229
|
+
メソッド呼び出しの都度、異なる引数の値がコピーされるため異なる動作ができるのです。
|
|
230
|
+
|
|
231
|
+
|
|
232
|
+
|
|
233
|
+
再帰呼出はループではありませんが、再帰呼出することはループの繰り返しと同じことをしています。再帰呼出ししなければループを終了させることになります。hanoi()では n=1 の時再帰しません。
|
2
再帰呼出の理解
test
CHANGED
|
@@ -95,3 +95,107 @@
|
|
|
95
95
|
**再帰の意味**
|
|
96
96
|
|
|
97
97
|
再帰するのは、問題を小さな部分問題に分割して解くためです。再帰する都度、n, n-1, n-2, ... , 1 と問題が小さくなり、1 のとき再帰せずリターンします。ネストした再帰がすべてリターンすると、部分問題がすべて解かれ、問題全体が解かれたことになります。再帰の動作がわかりづらければシーケンス図を書きましょう。表でもよい。縦に処理の流れ、横に再帰のネストごとの処理を畫いてください。
|
|
98
|
+
|
|
99
|
+
|
|
100
|
+
|
|
101
|
+
### 追記（再帰呼出のトレース）
|
|
102
|
+
|
|
103
|
+
> hanoi(n - 1, C, B, A)でいいと思うのですがこのメソッドの処理過程が真下に書いてないので混乱してます
|
|
104
|
+
|
|
105
|
+
|
|
106
|
+
|
|
107
|
+
コメントの内容から「ハノイの塔」の問題ではなく、それ以前の「再帰呼出し」が理解できていないと判断しました。トレースコードを示します。再帰を勉強してください。
|
|
108
|
+
|
|
109
|
+
|
|
110
|
+
|
|
111
|
+
**再帰呼出トレース用コード**
|
|
112
|
+
|
|
113
|
+
hanoi() の呼出/リターンを表示するための行を追加。
|
|
114
|
+
|
|
115
|
+
|
|
116
|
+
|
|
117
|
+
```ruby
|
|
118
|
+
|
|
119
|
+
def hanoi(n, from, to, via)
|
|
120
|
+
|
|
121
|
+
puts "hanoi(#{n}, #{from}, #{to}, #{via}) : enter"
|
|
122
|
+
|
|
123
|
+
if n == 1
|
|
124
|
+
|
|
125
|
+
puts "#{from} から #{to} へ移す"
|
|
126
|
+
|
|
127
|
+
else
|
|
128
|
+
|
|
129
|
+
hanoi(n - 1, from, via, to)
|
|
130
|
+
|
|
131
|
+
puts "#{from} から #{to} へ移す"
|
|
132
|
+
|
|
133
|
+
hanoi(n - 1, via, to, from)
|
|
134
|
+
|
|
135
|
+
end
|
|
136
|
+
|
|
137
|
+
puts "hanoi(#{n}, #{from}, #{to}, #{via}) : return"
|
|
138
|
+
|
|
139
|
+
end
|
|
140
|
+
|
|
141
|
+
|
|
142
|
+
|
|
143
|
+
hanoi(3, :A, :B, :C)
|
|
144
|
+
|
|
145
|
+
```
|
|
146
|
+
|
|
147
|
+
|
|
148
|
+
|
|
149
|
+
**再帰呼出トレース**
|
|
150
|
+
|
|
151
|
+
irbで実行した結果を編集しました。
|
|
152
|
+
|
|
153
|
+
|
|
154
|
+
|
|
155
|
+
```irb
|
|
156
|
+
|
|
157
|
+
hanoi(3, A, B, C) : enter
|
|
158
|
+
|
|
159
|
+
hanoi(2, A, C, B) : enter <-- 前半の移動 (A->C)
|
|
160
|
+
|
|
161
|
+
hanoi(1, A, B, C) : enter
|
|
162
|
+
|
|
163
|
+
A から B へ移す <-- この円盤は、この下で B->C に移動する
|
|
164
|
+
|
|
165
|
+
hanoi(1, A, B, C) : return
|
|
166
|
+
|
|
167
|
+
A から C へ移す <-- 2) ２枚目（前半(n-1)最後の円盤）の移動
|
|
168
|
+
|
|
169
|
+
hanoi(1, B, C, A) : enter
|
|
170
|
+
|
|
171
|
+
B から C へ移す
|
|
172
|
+
|
|
173
|
+
hanoi(1, B, C, A) : return
|
|
174
|
+
|
|
175
|
+
hanoi(2, A, C, B) : return
|
|
176
|
+
|
|
177
|
+
A から B へ移す <-- 1) ３枚目（全体(n)最後の円盤）の移動
|
|
178
|
+
|
|
179
|
+
hanoi(2, C, B, A) : enter <-- 後半の移動 (C->B)
|
|
180
|
+
|
|
181
|
+
hanoi(1, C, A, B) : enter
|
|
182
|
+
|
|
183
|
+
C から A へ移す <-- この円盤は、この下で A->B に移動する
|
|
184
|
+
|
|
185
|
+
hanoi(1, C, A, B) : return
|
|
186
|
+
|
|
187
|
+
C から B へ移す <-- 3) ２枚目（後半(n-1)最後の円盤）の移動
|
|
188
|
+
|
|
189
|
+
hanoi(1, A, B, C) : enter
|
|
190
|
+
|
|
191
|
+
A から B へ移す
|
|
192
|
+
|
|
193
|
+
hanoi(1, A, B, C) : return
|
|
194
|
+
|
|
195
|
+
hanoi(2, C, B, A) : return
|
|
196
|
+
|
|
197
|
+
hanoi(3, A, B, C) : return
|
|
198
|
+
|
|
199
|
+
=> nil
|
|
200
|
+
|
|
201
|
+
```
|
1
追記。
test
CHANGED
|
@@ -73,3 +73,25 @@
|
|
|
73
73
|
『コンピュータの数学』 ロナルド・L. グレアム、オーレン パタシュニク、ドナルド・E. クヌース 1993 共立出版
|
|
74
74
|
|
|
75
75
|
第1ページにハノイの塔の計算量の漸化式の解説があります。
|
|
76
|
+
|
|
77
|
+
|
|
78
|
+
|
|
79
|
+
### 追記
|
|
80
|
+
|
|
81
|
+
|
|
82
|
+
|
|
83
|
+
**表示からわかること**
|
|
84
|
+
|
|
85
|
+
中点にあたる移送を見れば、ピラミッドがどこに移動するのかが、わかります。
|
|
86
|
+
|
|
87
|
+
- 1) n ピラミッドは、A->B へ移動
|
|
88
|
+
|
|
89
|
+
- 2) n-1 ピラミッドは、A->C へ移動
|
|
90
|
+
|
|
91
|
+
- 3) n-1 ピラミッドは、C->B へ移動
|
|
92
|
+
|
|
93
|
+
|
|
94
|
+
|
|
95
|
+
**再帰の意味**
|
|
96
|
+
|
|
97
|
+
再帰するのは、問題を小さな部分問題に分割して解くためです。再帰する都度、n, n-1, n-2, ... , 1 と問題が小さくなり、1 のとき再帰せずリターンします。ネストした再帰がすべてリターンすると、部分問題がすべて解かれ、問題全体が解かれたことになります。再帰の動作がわかりづらければシーケンス図を書きましょう。表でもよい。縦に処理の流れ、横に再帰のネストごとの処理を畫いてください。
|