Задача про стадо коров с общим числом ног равным N, при числе ног у отдельных коров от 1 до M
Попалась тут любопытная задача, к счастью, требующая численного решения, с которым я почти справился (алгоритм есть, код попозже допишу).
А вот аналитическое решение не придумал, оно и не нужно, но покоя не даёт уже третий день.
Хочу поделиться.
Дано: в стаде коров ровно N ног. У каждой коровы число ног может быть от 1 до M, где M<=N.
Найти число возможных версий стад, без учета порядка коров, только по числу коров с конкретным числом ног.
Пример: для N = 4 и M = 4 возможные варианты стад — ровно 5 штук
1 1 1 1 (все коровы одноногие)
1 1 2 (две одноногие и одна двуногая)
1 3 (одна одноногая и одна трехногая)
2 2 (две двуногие)
4 (одна четырехногая)
Численно это решаю так: строю дерево с узлами, содержащими значения от 1 до M, от корневого узла — все варианты, а далее у каждого узла добавляю подузлы со значением, не менее значения родительского узла. Если сумма значений узлов от корня до текущего равна N, то сохраняю значения узлов в список как решение и прерываю обработку узла, если больше — то просто прерываю.
Не очень эффективно по памяти и времени, но работает.
Есть идеи по аналитическому решению? Возможно, как-то поиграться с системой счисления по основанию M, чтобы сумма цифр была равна N? Сами комбинации не нужны, решением должно быть просто число стад.
А вот аналитическое решение не придумал, оно и не нужно, но покоя не даёт уже третий день.
Хочу поделиться.
Дано: в стаде коров ровно N ног. У каждой коровы число ног может быть от 1 до M, где M<=N.
Найти число возможных версий стад, без учета порядка коров, только по числу коров с конкретным числом ног.
Пример: для N = 4 и M = 4 возможные варианты стад — ровно 5 штук
1 1 1 1 (все коровы одноногие)
1 1 2 (две одноногие и одна двуногая)
1 3 (одна одноногая и одна трехногая)
2 2 (две двуногие)
4 (одна четырехногая)
Численно это решаю так: строю дерево с узлами, содержащими значения от 1 до M, от корневого узла — все варианты, а далее у каждого узла добавляю подузлы со значением, не менее значения родительского узла. Если сумма значений узлов от корня до текущего равна N, то сохраняю значения узлов в список как решение и прерываю обработку узла, если больше — то просто прерываю.
Не очень эффективно по памяти и времени, но работает.
Есть идеи по аналитическому решению? Возможно, как-то поиграться с системой счисления по основанию M, чтобы сумма цифр была равна N? Сами комбинации не нужны, решением должно быть просто число стад.
— Тевирп. Под тремя спойлерами ниже есть ряд интересных цитат. Но не просто цитат, а искажённых. Например, фраза «привет лунатикам» может стать «первить лунатикает». Сложность нарастает от первой части к третьей, но это неточно. Комменты с ответами прошу заворачивать в спойлер (не в лайт-спойлер). Удачи!
