前の関連記事：Python(16)ハノイの塔の再帰を除去する
再帰関数を再帰を使わずwhile文で書く方法は習得できました。1回の再帰で使用する変数をすべて同じスタックに入れてしまえばよいようです。いままでやった例をすべてこの方法で再帰を除去します。
ユークリッドの互除法
Python(9)再帰のお勉強:ユークリッドの互除法でやったものです。
漸化式
$${\rm gcd}(x, y) = \begin{cases} x & (y = 0)\\{\rm gcd}(y, x \bmod y) & (y > 0) \end{cases} $$ 再帰関数
def gcd(x, y):
if y == 0:
return x
else:
return gcd(y, x % y)
print(gcd(24, 9))
while文
def gcd(x, y):
stack = [x, y]
while stack[-1] > 0:
x, y = stack[-2:]
del stack[-2:]
stack.extend([y, x % y])
return stack[-2]
print(gcd(24, 9))
ループの次に行く間にスタックから2個取り出して2個追加しているのでスタックに貯めておくものはなく、スタックは除去できます。def gcd(x, y):
while y > 0:
x, y = y, x % y
return x
print(gcd(24, 9))
自然数の階乗
Python(10)再帰のお勉強:自然数の階乗でやったものです。
漸化式 $${\rm factorial}(n) = \begin{cases}
1& (n=1) \\
n\times{\rm factorial}(n-1)& (n>1)
\end{cases}$$ 再帰関数
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(4))
while文
def factorial(n):
stack = [n, n]
while stack[-2] > 1:
n, r = stack[-2:]
del stack[-2:]
stack.extend([n - 1, r * (n - 1)])
return stack[-1]
print(factorial(4))
これもループの次に行く間に2個追加して2個削除しているのでスタックを除去できます。
def factorial(n):
r = n
while n > 1:
n, r = n - 1, r * (n - 1)
return r
print(factorial(4))
フィボナッチの数列
Python(11)再帰のお勉強:フィボナッチの数列でやったものです。
漸化式 $$ {F}_{n}=\begin{cases} 1 &(n = 0 \text{ or } n = 1) \\ {F}_{n-1}+{F}_{n-2}&(n > 1) \end{cases}$$ 再帰関数
def fib(n):
if n > 1:
return fib(n-1) + fib(n-2)
else:
return 1
print(fib(4))
while文
def fib(n):
stack = [n, 1, 1]
while stack[-3] > 1:
n, x, y = stack[-3:]
del stack[-3:]
stack.extend([n - 1, y, x + y])
return stack[-1]
print(fib(4))
これもいままでと同じく次のループに持ち越すスタックの内容がないのでスタックが除去できます。4行目のスタックから取り出したものと6行目のスタックに入れるものを=でつなげばいいだけですね。
def fib(n):
x, y = 1, 1
while n > 1:
n, x, y = n - 1, y, x + y
return y
print(fib(4))
複数同時の代入 (multiple assignment)(3.2. プログラミングへの第一歩)の作り方がよくわからなかったのですが、このやり方だと機械的に代入式が作れますね。ハノイの塔
Python(16)ハノイの塔の再帰を除去するでやったものです。
漸化式 $$ {\rm hanoi}(n, x, y, z)=\begin{cases}
x\rightarrow z&(n = 1) \\
\begin{pmatrix} {\rm hanoi}(n-1, x, z, y)\\
{\rm hanoi}(1, x, y, z)\quad\quad\\
{\rm hanoi}(n-1, y, x, z)\end{pmatrix}&(n > 1)
\end{cases}$$ 再帰関数
# -*- coding: utf-8 -*-
def hanoi(n, x, y, z):
if n == 1:
print("{}→{}".format(x, z))
else:
hanoi(n-1, x, z, y)
hanoi(1, x, y, z)
hanoi(n-1, y, x, z)
hanoi(3, "A", "B", "C")
4行目の"→"でUTF-8の文字列を使っているので1行目のエンコードの指定をしています。このエンコードの指定は実行には必要ありませんが、これがないとPyCharm3.4でブレークポイントを設定してデバッグするときにエラーになります。
while文
# -*- coding: utf-8 -*-
def hanoi(n, x, y, z):
stack = [n, x, y, z]
while stack:
n, x, y, z = stack[-4:]
if n > 2:
stack.extend([n-1, x, z, y])
elif n == 2:
print("{}→{}".format(x, y))
print("{}→{}".format(x, z))
print("{}→{}".format(y, z))
del stack[-4:]
if stack:
x, y, z = stack[-3:]
stack.extend([1, x, y, z ])
elif n == 1:
print("{}→{}".format(x, z))
if len(stack) > 4:
n = stack[-8]
del stack[-8:]
stack.extend([n-1, y, x, z])
else:
del stack[-4:]
hanoi(4, "A", "B", "C")
これのスタックは除去できません。アッカーマン関数
Python(15)アッカーマン関数の再帰を除去するでやったものです。
漸化式 $$ack(x, y)=\begin{cases} y+1& (x=0) \\ ack(x-1, 1)& (x>0かつy=0) \\ ack(x-1, ack(x, y-1))&(x>0かつy>0) \end{cases}$$ 再帰関数
def ack(x, y):
if x == 0:
return y + 1
elif y == 0:
return ack(x-1, 1)
else:
return ack(x-1, ack(x, y-1))
print(ack(3,6))
while文def ack(x, y):
stack = [x, y]
while len(stack) > 1:
# print(stack)
x, y = stack[-2:]
del stack[-2:]
if x == 0:
stack.append(y+1)
elif y == 0:
stack.extend([x-1, 1])
else:
stack.extend([x-1, x, y-1])
return stack[0]
print(ack(3, 6))
4行目のコメントアウトをはずすとstackの変化がみれますが、ack(2, 2)ぐらいにとどめておかないと結果があふれて表示されません。参考にしたサイト
3.2. プログラミングへの第一歩
Pythonの複数同時の代入 (multiple assignment)の解説があります。
0 件のコメント:
コメントを投稿