0

モンスター（N頭）を倒すには、2丁の銃AとBを使用する必要があります。銃Aを使用すると、6つの頭をカットしますが、モンスターが死なない場合（頭の数が0より大きい場合）、3つの頭が成長します。銃Bを使用すると、4つの頭がカットされますが、モンスターが死なない場合は2つの頭が成長します。N <（ガンが切断できるヘッドの数）の場合、ガンは使用できません。そして、N = -1の場合、モンスターとハンターの両方が死にます。

問題によって、モンスターを殺すことが可能かどうか、ハンターがモンスターを殺そうとして死ぬかどうか、最短経路を見つける必要があります。

上記の問題を解決するために、次のPythonプログラムを作成しました。

def A(heads, path):
    if heads < -1:
        path = []
        return "Impossible to kill"    
    heads -= 6
    path.append("A")
    if heads == 0:
        print path
        path = []
        return "Monster dies"
    if heads == -1:
        return "Both monster and human die"
    heads += 3
    if A(heads, path)=="Monster dies" or B(heads, path) == "Monster dies":
        return "Monster dies"
def B(heads, path):
    if heads < -1:
        path = []
        return "Impossible to kill"
    #print "B", path, heads
    heads -= 4
    path.append("B")
    if heads == 0:
        print path
        path =[]
        return "Monster dies"
    if heads == -1:
        return "Both monster and human die"
    heads += 2
    if A(heads, path)=="Monster dies" or B(heads, path) == "Monster dies":
        return "Monster dies"

print A(10, [])

サンプルデータ（質問で提供）：N = 10の場合、最短経路はAABです。

プログラムのどこで間違ったのですか？この問題を解決するためのより良い方法は何ですか？

4

2 に答える 2

1

最小ではないパスを探しています。次のようにパスの長さを保存して確認する必要があります。

def A(heads, path, path_len):
    if heads < -1:
        path = []
        return float('inf') #Impossible to kill
    heads -= 6
    if heads < 0:
        return float('inf')
    path_len = path_len + 1
    path.append("A")
    if heads == 0:
        print path
        return path_len
    heads += 3
    return min(A(heads, path, path_len), B(heads, path, path_len))

def B(heads, path, path_len):
    if heads < -1:
        path = []
        return float('inf') #Impossible to kill
    heads -= 4
    if heads < 0:
        return float('inf')
    path_len = path_len + 1
    path.append("B")
    if heads == 0:
        print path
        return path_len
    heads += 2
    return min(A(heads, path, path_len), B(heads, path, path_len))

A(10, [], 0)

これは正しい答えを与えます。パスを単純に印刷する代わりに、グローバル変数を使用してパスを格納できます。

于 2011-09-13T15:15:34.970 に答える
0

プログラムをもう少しうまく構成する必要があると思います。

おそらく、AとBの関数を作成して、ヘッドの数を取得し、関数を適用した後にヘッドの数を返します（銃の効果+再生）。

再帰呼び出しを別の制御関数に保持します。つまり、AとBが自分自身を呼び出す必要はありません。

終了条件には、文字列ではなく列挙型（またはPythonに相当するもの）を使用します。

終了条件が正しく処理されているかどうかはわかりません。

更新-user695518の回答で説明されているように、最適なソリューションが必要な場合は、各パスの長さをカウントし、最小値を返す必要があります。

于 2011-09-13T14:59:21.273 に答える