Python Recursion Puzzle : 맥도날드에서 n McNuggets 구입 (6, 9 및 20 팩 사용)

Question

이 문제에 대한 몇 가지 관련 질문을 발견했습니다. (웹에서도이 문제에 대해 조금 연구했습니다.) 그러나 이들 모두는 반복적입니다. 나는이 문제가 재귀를 사용하여 해결할 수있는 방법에 조금 당황입니다 : 당신이 눈치

def is_buyable(n): 
''' return whether amount n McNuggets is buyable at McDonalds (using 6, 9 and 20 packs) ''' 
    if n == 0: 
     return True 

    #... 
    #insert some code or if statement, with call on is_buyable(n) 

    else: 
     return False 

는,이 방법은 부울을 반환합니다. 어떤 도움을 주시면 감사하겠습니다!

Answer 1

재귀는 각 문제를 동일한 문제의 "더 작은"버전으로 분해하여 작동합니다. 이 경우에, 당신은이 코드를 삽입 할 수 있습니다

elif n < 0: 
    return False 

elif is_buyable(n - 20) or is_buyable(n - 9) or is_buyable(n - 6): 
    return True 

Answer 2

def is_buyable(n): 
    ''' return whether amount n McNuggets is buyable at McDonalds (using 6, 9 and 20 packs) ''' 
    if n == 0: 
     return True 
    for i in (6, 9, 20): 
     if n >= i and is_buyable(n - i): 
      return True 
    return False 

편집은 : 재귀를 사용하면 함수가 원래의 하위 문제에 자신을 호출해야하는 것을 의미한다. 이 때, (3) 양의 적어도 하나의 기능 검사 인 경우 (구매 가능한) True :

• 초기 량을 뺀 9 (구입 후 (도 6의 팩을 구입 한 후) 초기 량을 뺀 6 9 팩)
• 초기 량 -20 (

) (20)의 패키지를 구매 한 후 그 변성 량 중 적어도 하나는 현재 수량 (n)이 아니라 사볼, 구매 가능한 경우.

이 함수는 또한 처음에 수량 (n)이 수량에서 뺄 팩의 항목 수보다 크거나 같으면 체크합니다 (n >= i 수표).

Answer 3

꽤 맞지 않는 숙제 템플릿을하지만, :

def is_buyable(n): 
    return n==0 or any(n >= i and is_buyable(n - i) for i in (6,9,20))