『入門 データ構造とアルゴリズム』[1] の 2 章「再帰と後戻り」の課題を Python で書いてみました.ハノイの塔が例として出てくるのですが,私にはそれが初見だと難しかったので残します.
再帰の問題
問題 2-1 ハノイの塔を論ぜよ
Python でハノイの塔の最小移動回数の手順を求めるプログラムを書いてみます.コード自体は短いですが,理解するのが難しかったので順を追って説明します.
この記事では本に従って以下のように用語を使います.
「Source にある円盤を Destination に移動させよ.その際に Auxiliary を用いてよい.」という感じです.
最小移動回数を求める
ハノイの塔の解説を読むと,「
最初に,漸化式を使って最小移動回数を求めます.
まず,円盤の枚数が
以下の図のように
まず,円盤が 1 枚のときは最小移動回数は
次に
段の円盤を Auxiliary に移動する.n 枚目 ( Source にある一番下の段 ) を Destination に移動する.n + 1 - Auxiliary に移動した n 段の円盤を
の上に載せるように Destination に移動する.n + 1 の山が完成する.n + 1
つまり,
まず,
次に,
最後に,
これが
ここで,
よって数列
したがって
というわけで円盤 n 枚のときのハノイの塔の最小移動回数は
その過程で
なぜ再帰関数か
なぜ再帰関数で求められるのかを考えます.再帰であるということは,繰り返されている処理と入れ子になっている処理があるはずなので,それを見つけます.
繰り返されている部分
私は以下の図のイメージで繰り返されている部分に気づきました.再帰に気づくヒントになると思います.この図では
繰り返されているのは以下の処理です.
段を真ん中に作る.n - 1 段を Auxiliary に移動する.n - 1 段目を Destination に移動する.n 段を Auxiliary から Destination に移動する.n - 1
これは何段であっても同じです.
次に上の図では省略されている
例えば,
では,そもそも
手順を求める
それでは,どのような手順で円盤を操作すれば最小移動回数でハノイの塔の目標を達成できるか,再帰関数を使ってコードを書いていきます.
まず,
def towers_of_Hanoi(n, frompeg, topeg, auxpeg):
# First, move disk 1.
if n == 1:
print("Move disk 1 from peg", frompeg, "to peg", topeg)
return
# move n - 1 pegs from source to auxiliary.
towers_of_Hanoi(n - 1, frompeg, auxpeg, topeg)
print("Move disk", n, "from peg", frompeg, "to peg", topeg)
# move n - 1 pegs from auxiliary to destination
towers_of_Hanoi(n - 1, auxpeg, topeg, frompeg)
towers_of_Hanoi(3, "A", "B", "C")
後戻りの問題
問題 2-2 n ビットのすべての列を生成せよ.A[0..n-1]をサイズが n の配列と仮定せよ.
例えば,
コードを追うと 0 と 1 で分岐する図が想像できると思います.
bit: int = int(input())
A = [0] * bit
def binary(n):
if n < 1:
print(A)
else:
A[n - 1] = 0
binary(n - 1)
A[n - 1] = 1
binary(n - 1)
binary(bit)
問題 2-3 0..k-1 を要素とする長さ n の列をすべて生成せよ.
問題 2-2 では 2 進数の場合を考えましたが,今度は
digit, nary = map(int, input().split())
A = [0] * digit
def k_string(n, k):
if n < 1:
print(A)
else:
for i in range(k):
A[n - 1] = i
k_string(n - 1, k)
k_string(digit, nary)
例えば,3 桁の
おわりに
ハノイの塔が難しかったです.階乗を再帰で計算するのとはやっていることが全然違うものに思えて理解するのに時間がかかりました.再帰は遅くて実際のコード中ではほとんど使われない(大抵が反復を使う)イメージがあるので,解きながら問題の難易度と実用性が見合わないのではないかと感じていました.本によると再帰の問題が後のページで出てくるようなので,今回の勉強が役に立つといいです.
『入門データ構造とアルゴリズム』 ( Narasimha Karumanchi 著 黒川 利明・木下 哲也 訳 ) オライリージャパン ↩︎