皆さん,こんばんは(^-^)
先日、"ハノイの塔に再帰で挑む"記事で再帰の勉強をしました。
https://qiita.com/AKpirion/items/c0f7905c6227e086644e
※ハイパーリンクって出来ないんですかね！？
そこで @shiracamus さんに教えて頂いた以下の記述を早速パクリ、
スタックを追加して実現できないか考察します。
def move(n, a, b, c):
"""n枚の円盤をaからbを一時退避所にしてcに移動する"""
if n > 1:
move(n - 1, a, c, b) # aの1番下以外を、cを一時退避所にしてbに退避する
print(f" {n}番の円盤を {a} から {c} へ移動") # 1番下をaからcに移動
if n > 1:
move(n - 1, b, a, c) # bに退避した1番下以外を、aを一時退避所にしてcに移動する
def hanoi(n):
print(f"{n}枚の円盤を A から C へ移動する手順")
move(n, 'A', 'B', 'C')
if __name__ == '__main__':
hanoi(2)
hanoi(3)
今回は、前回の記事にあるように 2 つの円盤を動かしていきます。
再帰の記述では、必ず print(f" {n}番の円盤を {a} から {c} へ移動") に戻ってきます。
だとすると、{a},{c} のそれぞれの値について if 文で場合分けを行い、
push , pop を混ぜ込めば、スタックでハノイの塔を実現できるのではと思いました。
まずは位置 A , B , C に専用スタックをそれぞれ用意してみました。
class top:
def __init__(self,capacity:int = 2):
self.Astr = [2,1]
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
特に補足は不要だと思います。
次に push ですが、基本的に full になることは無いので、
記述はシンプルにできます。
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
pop も Empty の心配が無いので、
記述はシンプルです。
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
問題ないですよね？
あとは move です。
def move(self,n,a,b,c):
if n>1:
top.move(self,n-1,a,c,b)
print(f"{n}を{a}から{c}へ")
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if n>1:
top.move(self,n-1,b,a,c)
冒頭にも書きましたが、必ず print(f" {n}番の円盤を {a} から {c} へ移動") に
降りてくるので、この後に if を使って条件分けをしています。
3 枚の円盤だと、もっと場合分け増えそうですね(笑)
なんか良いやり方ないかな～。。（ ´Д｀）ｙ━─┛~~
if 文の中をもう少し補足すると、
push/pop はポインタptr の動作を管理しているだけなので、
必ず、None でA/B/C スタック本体の値を上書きしないと上手くいきません。
なので、None を push するんですが、
ptr が 1 増えちゃうので、そのあとに pop を使って元に戻します。
class top:
def __init__(self,capacity:int = 2):
self.Astr = [2,1]
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
def view(self):
print(f"A = {self.Astr}")
print(f"B = {self.Bstr}")
print(f"C = {self.Cstr}")
def move(self,n,a,b,c):
if n>1:
top.move(self,n-1,a,c,b)
print(f"{n}を{a}から{c}へ")
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if n>1:
top.move(self,n-1,b,a,c)
test = top()
if __name__ =="__main__":
print("default setting")
print("A = [2,1]")
print("B = [None,None]")
print("C = [None,None]")
test.move(2,"A","B","C")
実行結果はこちらです。
default setting
A = [2,1]
B = [None,None]
C = [None,None]
1をAからBへ
A = [2, None]
B = [1, None]
C = [None, None]
2をAからCへ
A = [None, None]
B = [1, None]
C = [2, None]
1をBからCへ
A = [None, None]
B = [None, None]
C = [2, 1]
N = 2 固定ではなくて、自由に変動させても追従できるような構成は、
改めて検討しようと思います。
多分、枚数が増えても移動の場所が増えるわけではないので、
何とかなる気がしています。やろう、いつの日か。。(￣з￣)
--10/03 18:53
子供の運動会も無事終わって、早めに寝てくれたので
時間が出来ました。チョット更新しようと思います。
更新内容は円盤数を N に変換しても大丈夫な構成を検討することです。
前回サラっと触れましたが、円盤の枚数が増えても移動箇所が増えるわけではありません。
なので、移動パターンを全て if 文で列挙すれば OK です。
A => B
A => C
B => C
B => A
C => A
C => B
と場合分けできれば、スマートじゃないですが
問題はクリアに出来ます。
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if a == "B" and c == "A":
top.Apush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if a == "C" and c == "B":
top.Bpush(self,top.Cpop(self))
top.Cpush(self,None)
top.Cpop(self)
top.view(self)
if a == "C" and c == "A":
top.Apush(self,top.Cpop(self))
top.Cpush(self,None)
top.Cpop(self)
top.view(self)
OK です。
次に用意する円盤数を N , 可変式にします。
class top:
def __init__(self,capacity):
self.Astr = [] * capacity #None も一応データなので、ここは空にしておく
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
for i in range(capacity): #4 を入れたら、0 => 1 => 2 => 3 と変化
self.Astr.append(capacity-i) #円盤枚数 capacity - i とすれば 4 => 3 => 2 => 1 を Astr に代入出来る
top.view(self)
if __name__ =="__main__":
num = int(input("enter: ")) # 何枚の円盤を用いるか定義します
test = top(num) # def__init__ の初期値、capacity を num に代入
test.move(num,"A","B","C") # num は実質、スタックの深さともイコールになる
そもそも None 無くても良くない？！(笑)
試しに 5 枚でやってみました。
enter: 5
A = [5, 4, 3, 2, 1]
B = [None, None, None, None, None]
C = [None, None, None, None, None]
1をAからCへ
A = [5, 4, 3, 2, None]
B = [None, None, None, None, None]
C = [1, None, None, None, None]
2をAからBへ
A = [5, 4, 3, None, None]
B = [2, None, None, None, None]
C = [1, None, None, None, None]
1をCからBへ
A = [5, 4, 3, None, None]
B = [2, 1, None, None, None]
C = [None, None, None, None, None]
3をAからCへ
A = [5, 4, None, None, None]
B = [2, 1, None, None, None]
C = [3, None, None, None, None]
1をBからAへ
A = [5, 4, 1, None, None]
B = [2, None, None, None, None]
C = [3, None, None, None, None]
2をBからCへ
A = [5, 4, 1, None, None]
B = [None, None, None, None, None]
C = [3, 2, None, None, None]
1をAからCへ
A = [5, 4, None, None, None]
B = [None, None, None, None, None]
C = [3, 2, 1, None, None]
4をAからBへ
A = [5, None, None, None, None]
B = [4, None, None, None, None]
C = [3, 2, 1, None, None]
1をCからBへ
A = [5, None, None, None, None]
B = [4, 1, None, None, None]
C = [3, 2, None, None, None]
2をCからAへ
A = [5, 2, None, None, None]
B = [4, 1, None, None, None]
C = [3, None, None, None, None]
1をBからAへ
A = [5, 2, 1, None, None]
B = [4, None, None, None, None]
C = [3, None, None, None, None]
3をCからBへ
A = [5, 2, 1, None, None]
B = [4, 3, None, None, None]
C = [None, None, None, None, None]
1をAからCへ
A = [5, 2, None, None, None]
B = [4, 3, None, None, None]
C = [1, None, None, None, None]
2をAからBへ
A = [5, None, None, None, None]
B = [4, 3, 2, None, None]
C = [1, None, None, None, None]
1をCからBへ
A = [5, None, None, None, None]
B = [4, 3, 2, 1, None]
C = [None, None, None, None, None]
5をAからCへ
A = [None, None, None, None, None]
B = [4, 3, 2, 1, None]
C = [5, None, None, None, None]
1をBからAへ
A = [1, None, None, None, None]
B = [4, 3, 2, None, None]
C = [5, None, None, None, None]
2をBからCへ
A = [1, None, None, None, None]
B = [4, 3, None, None, None]
C = [5, 2, None, None, None]
1をAからCへ
A = [None, None, None, None, None]
B = [4, 3, None, None, None]
C = [5, 2, 1, None, None]
3をBからAへ
A = [3, None, None, None, None]
B = [4, None, None, None, None]
C = [5, 2, 1, None, None]
1をCからBへ
A = [3, None, None, None, None]
B = [4, 1, None, None, None]
C = [5, 2, None, None, None]
2をCからAへ
A = [3, 2, None, None, None]
B = [4, 1, None, None, None]
C = [5, None, None, None, None]
1をBからAへ
A = [3, 2, 1, None, None]
B = [4, None, None, None, None]
C = [5, None, None, None, None]
4をBからCへ
A = [3, 2, 1, None, None]
B = [None, None, None, None, None]
C = [5, 4, None, None, None]
1をAからCへ
A = [3, 2, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 1, None, None]
2をAからBへ
A = [3, None, None, None, None]
B = [2, None, None, None, None]
C = [5, 4, 1, None, None]
1をCからBへ
A = [3, None, None, None, None]
B = [2, 1, None, None, None]
C = [5, 4, None, None, None]
3をAからCへ
A = [None, None, None, None, None]
B = [2, 1, None, None, None]
C = [5, 4, 3, None, None]
1をBからAへ
A = [1, None, None, None, None]
B = [2, None, None, None, None]
C = [5, 4, 3, None, None]
2をBからCへ
A = [1, None, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 3, 2, None]
1をAからCへ
A = [None, None, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 3, 2, 1]
誰か問題無いか確認してください(笑)
さて、次は @shiracamus さんがくれたヒントを
元に簡略化できる pyhton らしい記述にチャレンジしようと思います。
@shiracamus さんのコードを読みましたが、
読み終わったあと、笑ってしまいました。
Pyhton って、そんなこと出来るんですね(笑)。
あ ~ 恥かしい(*ﾉωﾉ)
勉強のために記事を書いているので、
この際、気にしません(笑)
取りあえず、まずこれを走らせてみました。
tower = {"A": [*range(3, 0, -1)], "B": [], "C": []}
print(tower)
{'A': [3, 2, 1], 'B': [], 'C': []}
なにこれ?! 魔法??
因みに range の前にある * を消すと。。
{'A': [range(3, 0, -1)], 'B': [], 'C': []}
っとなりました。
なるほど、おまじない" * "を付けると、
配列に化けるんですね( ..)φメモメモ
前述でも触れましたが、None もデータの一種なので、
None を使わずに空で行きます、同じことですよね。
次に、append() と pop() の導入です。
append() は、push と同じ動きをします。
更に pop は pop の考えそのままです。
しかも、便利なのは pop に関しては、データを取り出したらちゃんと
データを消してくれるところです。
。。。ちょっと待ってください。
ってことはポインタで管理していた制御は不要になるのでは?!
早速、最適化してみましょう、def __ init __ の記述を。
def __init__(self,capacity):
###############################
self.Astr = [] * capacity #=> tower = {"A": [*range(n, 0, -1)], "B": [], "C": []} へ置き換え
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
###############################
self.Aptr = 0 #=> append,pop でスタック動作を実現するのでポインタ管理用の変数は不要
self.Bptr = 0
self.Cptr = 0
##############################
for i in range(capacity): #=> "A": [*range(n, 0, -1)], に置き換えられるので不要
self.Astr.append(capacity-i)
top.view(self)
##############################
# || #
# \/ #
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
笑ってしまいましたw。
次に append, pop がスタックの動きになるのであれば、
push,pop 時のポインタ動作を管理した以下の記述も不要になるのではないでしょうか？
#全て不要!!!!#####################
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
################################
初期値として定義した tower ですが、
早速、append , pop を使って動かしてみましょう。
結論から言うと、こうなりました。
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}を{a}から{c}へ")
self.tower[c].append(self.tower[a].pop())
if n>1:
hanoi.move(self,n-1,b,a,c)
私の理解では class 内の def 間へ変数を渡す場合は self を用いるイメージです。
なので、self.tower と宣言しておけば、def move(self, ) とself を打ち込むことで
self.tower を def move 内に持ち込める理解です。
hanoi.move に関しては class hanoi の中にある def move を呼び出すイメージなので
hanoi.move( ) っとしました。
もうちょっと self の勉強が必要かもしれません。
次に行きます。
箱がそれぞれ、どのような状態かを表すために定義した以下の関数です。
def view(self):
print(f"A = {self.Astr}")
print(f"B = {self.Bstr}")
print(f"C = {self.Cstr}")
今となっては Astr/Bstr/Cstr は不要になったので、
別の方法で表す必要があります。
頂いたコードだけで理解できるほど天才ではないので、
調べました。以下に分かりやすい説明がありました。
これによると、箱の名称、箱の中身 で for 文を回して表現できるよ。っとの事でした。
def view(self):
for name,value in self.tower.items()
print(f"{name} = {value}")
なるほど。
早速、組み込んでみましょう。
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def view(self):
for name,value in self.tower.items():
print(f"{name} = {value}")
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}を{a}から{c}へ")
self.tower[c].append(self.tower[a].pop())
hanoi.view(self)
if n>1:
hanoi.move(self,n-1,b,a,c)
死ぬほどシンプルになりました。
全体像としては、こんなかんじです。
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def view(self):
for name,value in self.tower.items():
print(f"{name} = {value}")
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}を{a}から{c}へ")
self.tower[c].append(self.tower[a].pop())
hanoi.view(self)
if n>1:
hanoi.move(self,n-1,b,a,c)
if __name__ =="__main__":
num = int(input("enter: "))
test = hanoi(num)
test.move(num,"A","B","C")
勉強の機会をくれた @shiracamus さんに感謝です m(_ _)m