Проблема голов монстров в Python - PullRequest
Новая
       31

Проблема голов монстров в Python

0 голосов
/ 13 сентября 2011

Для убийства монстра нужно использовать две пушки A и B (с N головами). Когда используется пистолет A, он режет 6 голов, но если монстр не умирает (нет голов> 0), он вырастет на 3 головы. Когда используется пистолет B, он режет 4 головы, но если монстр не умирает, он вырастает 2 головы. Если N <(количество головок, которое пистолет может разрезать), в этом случае пистолет не может быть использован. А если N = -1, то и монстр, и охотник умирают. </p>

Задача должна выяснить, возможно ли убить монстра, умирает ли охотник, пытаясь убить монстра, и по кратчайшему пути.

Я написал следующую программу на 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.

Где в программе я ошибся и как лучше решить эту проблему?

Ответы [ 2 ]

1 голос
/ 13 сентября 2011

Вы ищете не самый маленький путь.Вам нужно сохранить и проверить длину пути следующим образом: 

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)

это дает правильный ответ.Вы можете иметь глобальную переменную для хранения пути вместо простой ее печати

0 голосов
/ 13 сентября 2011

Я думаю, вам нужно немного лучше структурировать программу.

Возможно, создайте функцию для A и B, которая будет принимать количество голов и возвращает количество голов после применения функции (эффект gun +регенерация).

Хранить рекурсивные вызовы в отдельной функции управления;то есть не имеют A и B, называют себя.

Используйте перечисление (или любой другой эквивалентный для Python), а не строки для конечных условий.

Мне не ясно, правильно ли обработаны конечные условия.Обновление - как объясняет ответ пользователя 695518, вам нужно посчитать длину каждого пути и вернуть минимум, если вы хотите оптимальное решение.

...