Блог

Мне снова нужна ваша помощь. Я пишу код, который определяет, является ли число полуполноценным числом или нет, возвращая логическое значение. Итак, сначала я подумал, что составлю список факторов числа, исключая само число

 def isSemiPerfect(n):
factor = []
for i in range(n-1, 0, -1):
    if n%i == 0:
        factor.append(i)
  

Если бы я проверил число 12, оно вернулось бы

 factor = [1, 2, 3, 4, 6]
  

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

 True = 6   4   2 or 6   3   2   1
  

Может кто-нибудь сказать мне, как я могу использовать рекурсию для проб и ошибок? Например, я всегда буду начинать с самого большого числа и пробовать путь со следующим по величине числом, пока не попробую все комбинации.

Я знаю, что здесь не так много продолжения, я просто надеюсь, что вы можете рассказать мне, как я могу эффективно использовать рекурсию. Спасибо!

Вы можете думать об этом так.

Вопрос «Может ли [1,2,3,4,6] суммироваться с 12»?

Это то же самое, что «Может ли [2,3,4,6] суммироваться с 11» или «Может ли [2,3,4,6] суммироваться с 12»?

Один использует первый элемент (и имеет меньшую сумму), а другой не использует первый элемент и имеет ту же сумму.

таким образом, функция запуска будет:

 def f(lst,sum_left):
    return f(lst[1:], sum_left-lst[0]) or f(lst[1:],sum_left)
  

Однако эта функция не знает, когда остановиться. Итак, нам нужны некоторые базовые примеры.

Очевидно, что если сумма равна 0, ответ тривиально да:

 if sum_left == 0:
    return true
  

Другой базовый вариант: если сумма < 0, мы взяли слишком большой элемент, и мы никогда не сможем восстановить.

 if sum_left < 0:
    return true
  

Кроме того, мы можем рисковать исчерпанием элементов, например, [1,2] никогда не может суммироваться до 50, поэтому мы добавляем базовый вариант, если в списке нет элементов:

 if not lst:
    return false
  

Собрать все это вместе:

 def f(lst, left):
    if left == 0:
        return True
    if left < 0:
        return False
    if not lst:
        return False
    
    return f(lst[1:],left-lst[0]) or f(lst[1:],left)