2 
def printMove(source, destination): 
    print('move From ' + str(source) + ' to destination ' + str(destination))
    count +=1
    print count

def Towers(n, source, destination, spare):
    if not count in  locals():
        count = 0
    if n == 1:
        printMove(source, destination)
        count +=1   
    else:
        Towers(n-1, source, spare, destination)
        Towers(1, source, destination, spare)
        Towers(n-1, spare, destination, source)

このスクリプトは、「ハノイの塔」を解決するために作成しました。スクリプトはうまく機能しますが、問題を解決するために必要な移動回数も印刷したいと思います。私は、カウントされるカウンターのようなものをどのように置くことができるかを理解することができません：

  1. 解決するのにかかる動きの数。
  2. 「タワー」機能が実行された回数。

このif not count in locals():状態は、解決に必要な移動数のカウントに失敗した試みの1つです。とにかく私は正しい方向に進んでいますか？

また、このアルゴリズムは効率的ですか？それとも、これを解決するためのより良い方法はありますか？

さらに、誰かがハノイの塔のいくつかの有用なアプリケーションと再帰の利点を教えてもらえますか？私が理解できたのはその単純さだけでした。

4

6 に答える 6

3

1 つの方法は、次のようにすべての呼び出しでカウンターを実行することです。

def towers(n, source, destination, spare, count=0):
    if n == 1:
        count += 1
        print('move From', source, ' to destination ', destination, count)
    else:
        count = towers(n-1, source, spare, destination, count)
        count = towers(1, source, destination, spare, count)
        count = towers(n-1, spare, destination, source, count)
    return count

towers(3, 1, 2, 3)

収量

move From 1  to destination  2 1
move From 1  to destination  3 2
move From 2  to destination  3 3
move From 1  to destination  2 4
move From 3  to destination  1 5
move From 3  to destination  2 6
move From 1  to destination  2 7

効率に関して、 http: //en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solutionは次のように述べています。この最小限の移動回数を持つ 1 つだけです。".

再帰の主な利点は、これらのソリューションが洗練されている傾向があることです。ある種の問題では、反復解法は再帰的解法よりも表現がはるかに複雑です。

于 2013-02-24T14:45:54.017 に答える
1

追加のパラメーター「count」がなければ、このバージョンがさらに気に入っています。

def towers(n, source, destination, spare):
    count = 0
    if n == 1:
        print('move From', source, ' to destination ', destination)
        return 1
    else:
        count += towers(n-1, source, spare, destination)
        count += towers(1, source, destination, spare)
        count += towers(n-1, spare, destination, source)
        return count

print(towers(3, 1, 2, 3))

収量

move From 1  to destination  2
move From 1  to destination  3
move From 2  to destination  3
move From 1  to destination  2
move From 3  to destination  1
move From 3  to destination  2
move From 1  to destination  2
7
于 2013-02-24T17:10:18.040 に答える
1

最も簡単な方法は、グローバル var を使用することです。

count = 0

def runTowers(...):
    global count
    count = 0
    Towers(...)

def Towers(...):
    global count
    count += 1
    ...
于 2013-02-24T14:37:57.370 に答える
1

関数の代わりに関数オブジェクトを作成できます。

class Towers:

    def __init__(self):
        self.count = 0

    def __call__(self, n, source, destination, spare):
        if n == 1:
            self.printMove(source, destination)
            self.count +=1   
        else:
            self(n-1, source, spare, destination)
            self(1, source, destination, spare)
            self(n-1, spare, destination, source)

    def printMove(self, source, destination):
        print('move From ' + str(source) + ' to destination ' 
              + str(destination))
        print(self.count)

towers = Towers()
towers(3, 1, 2, 2)
于 2013-02-24T14:49:00.980 に答える
0

上記の答えはあなたの答えを与えるはずです:)

効率の点では、ソリューションは n タワーで機能するようです。古典的な問題をより効率的に解決したい場合は、次のリンクを参照してください。

http://www.vogella.com/articles/JavaAlgorithmsTowersOfHanoi/article.html

最後に、再帰は、基本的なコードで複雑な計算を実行できる非常に単純なアルゴリズムを作成するように設計されています。欠点は、メモリを集中的に使用することです (各呼び出しは、最後の呼び出しのスタックに新しいメモリ アドレスを配置します)。

于 2013-02-24T14:39:40.947 に答える