難解Pythonのハノイ塔の再帰的実装の理解

Question

ハノイ塔問題のPythonコードonlineが見つかりました。コードは機能しますが、わかりにくいです。ここでは、次のとおりです。

def hanoi(n, source, helper, target): 
    if n > 0: 
     # move tower of size n - 1 to helper: 
     hanoi(n - 1, source, target, helper) 
     # move disk from source peg to target peg 
     if source: 
      target.append(source.pop()) 
     # move tower of size n-1 from helper to target 
     hanoi(n - 1, helper, source, target) 


source = [2, 1] 
target = [] 
helper = [] 
hanoi(len(source), source, helper, target) 

print (source, helper, target) 

私は最後の部分で問題を抱えている：

hanoi(n - 1, helper, source, target) 

は、私の知る限り理解できるよう、起こるだけ移動はtarget.append経由で（source.pop （））行。私たちが[2,1]の単純なリストでそれをするとき、1を目標リストに移動した後、何とか1をヘルパーリストに移動させますが、どうやって???

私はそれを参照してください方法は、ここで実行をプログラムする方法は次のとおりです。それは、ターゲットに1を移動させ、それが私の難しい点に達する、nを返す= 1、n = 0のは、何もしません達し、

hanoi(n - 1, helper, source, target) 

を実行します

ですが、n-1 = 0なので、何もしないので、 source = [2]、helper = []、target = [1]でn = 2に移動する必要があります。しかし、私がプログラムでプリントを使用すると、難しさの後、n = 2の前に、何らかの形でヘルパーに1が移動し、状況がsource = [2]、helper = [1]、target = []

n = 0でもどうしますか？ n> 0の場合にのみ実行されるという条件がありますか？その瞬間に何が起こっているのかを知るためにプリントを使用するにはどうすればいいですか？

Answer 1

標準的なトレース印刷ステートメントを挿入しました。私たちは、ルーチンを入力したり終了したりするたびに重要な処理ジャンクションに挿入しました。私はまた、コールレベルを表示するためにインデントを投げた。

問題を説明するうえで、各スタックに文字ラベルを追加した後、nを1つ減らして、それらのラベルを移動しないようにしました。これにより、すべてのコールでどのロールが各ロールにあるかを正確に確認することができます。

出力には、各呼び出しで何が移動するのか、すべてのディスクシャッフルで再帰が行われる場所が表示されます。 2つのディスクのアイデアが得られたら、3で試してみてください。理解し始めたら、それを4に伸ばして、トレースステートメントの1つまたは2つをコメントアウトしてください。

indent = "" 

def hanoi(n, source, helper, target): 
    global indent 
    indent += " " 
    print (indent, "ENTER", n, source, helper, target) 
    if n > 0: 
     # move tower of size n - 1 to helper: 
     hanoi(n - 1, source, target, helper) 
     # move disk from source peg to target peg 
     if source: 
      print (indent, "MOVE disk", source[-1], "from", source[0], "to", target[0]) 
      target.append(source.pop()) 
     # move tower of size n-1 from helper to target 
     hanoi(n - 1, helper, source, target) 

    print (indent, "LEAVE", n, source, helper, target) 
    indent = indent[:-2] 


source = ['A', 2, 1] 
helper = ['B', ] 
target = ['C', ] 

print (source, helper, target) 
hanoi(len(source)-1, source, helper, target) 
print (source, helper, target) 

出力：

['A', 2, 1] ['B'] ['C'] 
    ENTER 2 ['A', 2, 1] ['B'] ['C'] 
    ENTER 1 ['A', 2, 1] ['C'] ['B'] 
     ENTER 0 ['A', 2, 1] ['B'] ['C'] 
     LEAVE 0 ['A', 2, 1] ['B'] ['C'] 
    MOVE disk 1 from A to B 
     ENTER 0 ['C'] ['A', 2] ['B', 1] 
     LEAVE 0 ['C'] ['A', 2] ['B', 1] 
    LEAVE 1 ['A', 2] ['C'] ['B', 1] 
    MOVE disk 2 from A to C 
    ENTER 1 ['B', 1] ['A'] ['C', 2] 
     ENTER 0 ['B', 1] ['C', 2] ['A'] 
     LEAVE 0 ['B', 1] ['C', 2] ['A'] 
    MOVE disk 1 from B to C 
     ENTER 0 ['A'] ['B'] ['C', 2, 1] 
     LEAVE 0 ['A'] ['B'] ['C', 2, 1] 
    LEAVE 1 ['B'] ['A'] ['C', 2, 1] 
    LEAVE 2 ['A'] ['B'] ['C', 2, 1] 
['A'] ['B'] ['C', 2, 1]