0

需要使用两把枪 A 和 B 来杀死一个怪物(有 N 个头)。当使用枪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

You need to structure the program a bit better I think.

Perhaps create a function for A and B that takes the number of heads and returns the number of heads after applying the function (effect of gun + regeneration).

Keep the recursive calls in a separate control function; i.e. don't have A and B call themselves.

Use an enum (or whatever the python equivalent is) rather than strings for the end conditions.

It's not clear to me if the end conditions are handled correctly.

Update - as user695518's answer explains, you need to count the length of each path and return the minimum if you want an optimal solution.

于 2011-09-13T14:59:21.273 回答