파이썬의 몬스터 헤드 문제

몬스터를 죽이기 위해 두 개의 건 A와 B를 사용해야합니다 (N 개의 머리 포함). 총 A를 사용하면 6 개의 머리를 자르지 만 몬스터가 죽지 않으면 (머리가 0이 아닌) 머리가 3 개 커집니다. 총 B를 사용하면 4 개의 머리를 자르지 만 몬스터가 죽지 않으면 머리가 두 개 커집니다. N < (총을 절단 할 수있는 헤드 수)이 아닌 경우 총을 사용할 수 없습니다. 그리고 N = -1이면 괴물과 사냥꾼이 모두 죽습니다.파이썬의 몬스터 헤드 문제

몬스터를 죽일 수 있는지, 사냥꾼이 몬스터와 최단 경로를 죽이려 고 죽을 지 여부를 알아내는 것이 문제로 요구됩니다.

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, [])

샘플 데이터 (질문에 의해 제공) :

I은 상기 과제를 해결하기 위해 다음 파이썬 프로그램을 작성한 N = 10, 최단 경로 AAB이다.

프로그램에서 내가 잘못 가고이 문제를 해결하는 데 더 좋은 방법은 무엇입니까?

출처

2011-09-13 Anonymous

숙제? 면접 질문? 개발 한 솔루션에 어떤 문제점이 있습니까? –

숙제 또는 면접 질문 :) 그냥 내 호기심을 사로 잡았 어! 내가 겪고있는 문제에 관해서는, 표시된 경로가 정확하지 않다는 것입니다. –

잘못된 결과가 무엇인지 보여주는 것이 좋습니다. 사람들이 직접 프로그램을 실행하지 않아도 문제를 해결할 수 있습니다. –

가장 작지 않은 경로를 검색하고 있습니다. 다음과 같이 경로의 길이를 저장하고 검사해야합니다.

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-13 15:15:34 pomel

원래 코드가 실제로 작동한다는 것을 알지 못했습니다! 이것은 더 나은 대답입니다 (비록 내가 다르게 구조를 짓 겠지만). –

프로그램을 좀 더 구조화해야한다고 생각합니다.

아마도 건수를 사용하고 함수를 적용한 후 (건 + 재생의 효과) 머리 수를 반환하는 A 및 B 함수를 만듭니다.

재귀 호출은 별도의 제어 함수로 유지하십시오. 즉 A와 B는 스스로를 호출하지 않습니다.

끝 조건에 대한 문자열이 아닌 enum (또는 파이썬과 동등한 것)을 사용하십시오.

최종 조건이 올바르게 처리되는지는 확실하지 않습니다.

업데이트 - user695518의 답변에 따르면 최적 경로가 필요한 경우 각 경로의 길이를 계산하고 최소값을 반환해야합니다.

출처

2011-09-13 14:59:21

파이썬의 몬스터 헤드 문제

답변

관련 문제