5

私は Python がまったく初めてで、現在、ハノイの塔と再帰に関するチュートリアルを進めています。彼らがこの例を与えるまで、私は再帰を理解していると思っていました:

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)


moveTower(3,"A","B","C")

これは、3 つのディスクを使用してハノイの塔問題を解くための正しい動きを出力します。 ディスクを A から B に移動 ディスクを A から C に移動 ディスクを B から C に移動 ディスクを A から B に移動 ディスクを C から A に移動AからBにディスクを移動する

私の質問は、どうやってそうするのですか?! 誰かがコード行を調べて、正しい動きをどのように出力するかを理解できますか? 私は主に、 と の値が から にどのように変化するかについて混乱fpしてtpいます。これが少し広い質問である場合は申し訳ありません！どんな助けでも大歓迎です！ABC

4

5 に答える 5

3

printこの単純なケースでは、次のように適切な を使用して何が起こるかを視覚化できます。

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        print( "    "*(3-height), "moveTower:", height, fromPole, toPole )
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole,height)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp,height):
    print("    "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp)


moveTower(3,"A","B","C")

出力は次のとおりです。

moveTower: 3 A B
     moveTower: 2 A C
         moveTower: 1 A B
             moving disk ~ from A to B
         moving disk ~~ from A to C
         moveTower: 1 B C
             moving disk ~ from B to C
     moving disk ~~~ from A to B
     moveTower: 2 C B
         moveTower: 1 C A
             moving disk ~ from C to A
         moving disk ~~ from C to B
         moveTower: 1 A B
             moving disk ~ from A to B
于 2014-04-16T11:22:34.523 に答える
2

これが何をするかです。開始位置は次のとおりです。

A|321
B|
C|

moveTower(2,fromA,toC, withB)結果は次のとおりです。

A|3
B| 
C|21

その後moveDisk(fromA, toB)、

A|
B|3
C|21

そして最後moveTower(2,fromC, toB)にゲームを終了します

A|
B|
C|321

これがハノイの通常の解決策です。高さの塔をh-1にwithPole移動し、最大の円盤を に移動し、endPole高さの塔を に移動h-1しendPoleます。

h-1これは、最大の円盤で高さの塔の各円盤を移動できるため機能します。

moveTower(height-1,w,x)残りのディスクを 3 つのタワーすべてに配置することができます。

次にmoveTower(height-2,y,z)、2 番目に大きいディスクを目的地に移動し、タワーの高さ 2 を再び移動します。

編集：このリンクの図は、私が言おうとしていることを最もよく説明しています（「絵は千の言葉に値する」）。

タワーを移動することがわかっている場合はheight-1、アルゴリズムで説明されている 3 つの手順を実行してください。moveDiscは「基本ケース」 (最初のステップを登る) であり、moveTower は再帰 (ステップnからに移動する方法n+1) です。

于 2014-04-16T11:20:39.180 に答える
0

引数の変更を確認するには、各 moveTower の呼び出しを出力する必要があります。再帰は通常、引数を介して変更を伝達します。シーケンス番号は順序を示すのに役立ちます (もちろん、コンソールへの出力も順序付けされています)。

def seq_nummer():
    num = 0
    while True:
        num += 1
        yield num

seq_num = seq_nummer()

def moveTower(height, fromPole, toPole, withPole):
    print("seq: %d" % seq_num.next())
    print("height: %d, fromPole: %s, toPole: %s, withPole: %s" % (height, fromPole, toPole, withPole))
    if height >= 1:
        moveTower(height-1, fromPole, withPole, toPole)
        moveDisk(fromPole, toPole)
        moveTower(height-1, withPole, toPole, fromPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)

moveTower(3,"A","B","C")
于 2014-04-16T11:26:03.277 に答える
0 
moveTower(height-1,fromPole,withPole,toPole)

3 番目の極を使用して、1 つを除くすべてのディスクを最初の極から中間の極に移動します。

moveDisk(fromPole,toPole)

最後の円盤を最初の極から最後の極に移動します。最後のディスクは正しい位置にあり、移動する必要はありません。

moveTower(height-1,withPole,toPole,fromPole)

必要に応じて最初の極を使用して、中間の極から最後の極まですべてのディスクを移動します。

于 2014-04-16T11:27:12.640 に答える