파이썬에서의 재귀

Question

문제는 트윈 팬 균형에서 주어진 가중치 세트로 원하는 값을 측정 할 수 있는지 여부를 결정하는 "def EhMensuravel (target, weight)" 재귀 함수를 작성하는 데 있습니다. 사용 가능한 가중치는 "가중치"목록에 저장됩니다. 목표 무게의 동일한 플레이트에서 무게가 반대되는 플레이트에 무게를 놓을 수 있다는 것을 기억하십시오.

내가 만든 코드는 그 것이지만 뭔가 잘못되었습니다.

weights = [1, 2, 3] 
matrix = [] 

def createaMatrix(): 
    for i in range(len(weights)): 
     matrix.append([]) 
    for j in range(3): 
     for i in range(len(weights)): 
      if j==0: 
       matrix[j].append(weights[i]) 
      if j==1: 
       matrix[j].append(-weights[i]) 
      if j==2: 
       matrix[j].append(0) 

createMatrix() 


def EhMensuravel(entry, weights, final_weight=0): 
    if final_weight == entry: 
     return True 
    for j in range(3): 
     for i in range(len(weight)): 
      final_weight += matrix[i][j] 
      return EhMensuravel(entry, weight[1:], final_weight) 

편집 : 나는 print EhMensuravel(4, weights) 할 때 예를 들어, 출력은 다음과 같습니다

>>> 
1 
2 
3 
None 
>>> 

Answer 1

당신은 심지어이

weights = [1, 2, 3] 

def EhMensuravel(entry, weights, weight_idx = 0): 
    if entry == 0: 
     return True 

    if weight_idx == len(weights): 
     return False 

    if EhMensuravel(entry + weights[weight_idx], weights, weight_idx+1): 
     return True 

    if EhMensuravel(entry - weights[weight_idx], weights, weight_idx+1): 
     return True 

    if EhMensuravel(entry, weights, weight_idx+1): 
     return True 

    return False 

print EhMensuravel(4, weights) 

등 글로벌 매트릭스없이 재귀가 매우 간단하게 할 수 있습니다 첫 번째 if 문은 0이 측정 가능하다고 말합니다. 두 번째는 여전히 가중치가 있음을 보장하는 경우입니다. 다음 3 회의 재귀 호출은 현재 가중치를 더하거나 빼거나 무시하여 현재 가중치를 업데이트하고 다음 가중치에서 검색을 다시 시작합니다. 솔루션을 찾지 못하면 False가 반환됩니다.