Учеба и наука

Решено

Алгоритм разбиения натурального числа на сумму зараннее заданных слогаемых. Причем слогаемые должны повторятся как можно реже, а использовать надо максимальное число заданных слагаемых. - вопрос №3032556

Например: даны слогаемые: 1, 5, 10. Разложить надо число 20. В результате получаем: 10, 5, 1, 1, 1, 1, 1 или же даны 2, 6 и 7, разложить надо 30, в результате получаем 2,2,6,6,7,7. Посоветуйте какие-нибудь формулы, или же алгоритм решения. Спасибо.

октябрь 24, 2018 г.

  • Всего ответов: 2

  • HFS - аватарка

    HFS

    5-й в

    без четкого доказательства, но интуитивно, на основе примера

    даны слогаемые: 1, 5, 10. Разложить надо число 20. В результате получаем: 10, 5, 1, 1, 1, 1, 1
    думаю нужна рекурсивная функция подбора, типа такого алгоритма:
    — вычитаем из Х допустимые все допустимые слагаемые начиная с большего (для достижения минимально возможного повторения слагаемых) и по одному (для вовлечения максимально большего числа слагаемых) записываем в список результата
     - если остаток равен 0 работа закончена
     - если остаток отрицательный, надо откатывать на 2 слагаемых, пропускать предпоследнее и пробовать с последним (меньшим, но на котором случился "-") до конца последовательности слагаемых
     - если остаток положительный повторить весь алгоритм для остатка, продолжая добавлять в общий список слагаемые, которые не приходится пропускать из за "-"

    это функциональный стиль, но задачи такого типа разорвут мозг, если пытаться решать их в императивном стиле.
    за символическое награждение, могу набросать прототип на C#. с другими языками будет сложнее, где то с языком сложнее (для меня) где то по тому что среду разработки придется поднимать… и тд. а шарп у меня в повседневной эксплуатации

    октябрь 24, 2018 г.
    Ответ понравился автору
    Лучший ответ по мнению автора
  • HFS - аватарка

    HFS

    5-й в

    вообще тут требуется уточнение приоритетов условий

    слогаемые должны повторятся как можно реже
    и
    использовать надо максимальное число заданных слагаемых
    повторим пример
    даны слогаемые: 1, 5, 10. Разложить надо число 20. В результате получаем: 10, 5, 1, 1, 1, 1, 1
    тут возможен ответ 10,10 или 10,5,5, в обоих всего 2 повторения, а в приведенном варианте, хотя задействованы все слагаемые, но одно из низ повторяется целых 5 раз. приоритет второго условия (максимум вариантов слагаемых) явно не оговорен. его приходится домысливать на основе примера. хотя мой набросок алгоритма исходит именно из такого приоритета

    ps вообще то правильно слагаемые

    октябрь 24, 2018 г.