@Canp

Как найти слагаемые числА, используя только слагаемые из списка?

Есть число 6, как найти его слагаемые, только среди тех значений, которые в списке { 2, 1, 5, 8 } и чтобы количество слагаемых было не больше 2 ?

Данные списка и количества слогаемых примерные.

?

Дополнение к вопросу. Как сделать, чтобы в результате слагаемые не повторялись?
  • Вопрос задан
  • 152 просмотра
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Для двух слагаемых всё элементарно.
Сортируем массив, ставим указатели на первый и последний элементы.
Если сумма элементов равна требуемой, то мы нашли нужную пару.
Если меньше, то сдвигаем левый указатель вправо.
Если больше, то сдвигаем правый указатель влево.
Если указатели сошлись, то подходящей пары нет.
Ответ написан
Комментировать
Vindicar
@Vindicar
RTFM!
Я бы решал задачу рекурсией.
У тебя есть два варианта.
а) Раскладываемое число есть в списке. Тогда это число и будет единственным слагаемым.
б) Раскладываемого числа нет в списке. Тогда последовательно перебирай числа из списка, меньшие раскладываемого числа - возможные слагаемые.

Если нашел такое число, то:
1. Вычитаешь его из раскладываемого числа
2. Убираешь из списка его и все более ранние числа.
3. Пробуешь решить задачу для нового раскладываемого числа и нового списка чисел.
4. Если решение нашлось, возвращаешь результат выше, добавив к нему то возможное слагаемое, которое ты обрабатывал.

Т.е., иными словами, у тебя будет функция вида:
def sum_split(summa: int, candidates: list[int]) -> list[int]:

Если summa присутствует в candidates, то возвращаешь [summa].
Иначе перебираешь список candidates, и для каждого числа candidates[i] делаешь рекурсивный вызов
answer = sum_split(summa - candidates[i], candidates[i+1:])
.
Если список answer не пуст, добавляешь к этому списку candidates[i] и возвращаешь его сам.
А если перебрал весь список и ничего не подошло, возвращаешь пустой список.

Дальше сам.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы