UniLecs #128. "Максимальное" разбиение числа
UniLecs
Задача: дано натуральное числа N. Необходимо разложить его на натуральные слагаемые таким образом, чтобы их произведение было максимальным.
Входные данные: N - натуральное число от 4 до 100
Вывод: максимальное произведение слагаемых при разбиении числа N
Пример:
N = 5
Answer = 6 (5 = 2 + 3 -> 2 * 3 = 6)
Идея: рассмотрим первые цифры: 1, 2, 3, 4, 5, ...
Цифры 1 (0 + 1), 2 (1 + 1), 3(1 + 2 или 1 + 1 + 1) мы не можем разложить на такие слагаемые, произведение ктр было бы больше самих цифр.
Для числа 4 (2 + 2) макс.произведение его слагаемых будет равно самому числу 4.
Но начиная с цифры 5 макс.произведение его слагаемых уже будет больше самого числа. 5 = 2 + 3 -> 2 * 3 = 6.
6 = 3 + 3 -> 3 * 3 = 9.
7 = 2 + 2 + 3 -> 2 * 2 * 3 = 12
8 = 3 + 3 + 2 -> 3 * 3 * 2 = 18
9 = 3 + 3 + 3 -> 3 * 3 * 3 = 27
10 = 3 + 3 + 2 + 2 -> 3 * 3 * 4 = 36
Как не трудно догадаться, любое число мы можем разложить на сумму чисел 1, 2, 3. В нашем случае мы будем стараться использовать как можно больше цифр 3.
Если же есть остаток, то
1. Остаток кратен 2, то представляем остаток в виде двойки
2. Остаток кратен 1, то забираем одну тройку из пред.разложения и прибавляем к остатку (сумма двух нечетных чисел всегд равна четному) и снова представляем в виде суммы двоек. Очевидно, что 2 * 2 > 3 * 1.
Важно заметить, что единицу в разложении мы не используем, т.к. она не увеличивает произведение.
В итоге получится разложение на слагаемые из чисел 3, 2.
Реализация:
https://gist.github.com/unilecs/668d9c700fac5dfd473e195f943c66f5
Test: