Найдите {E1, .. En} (E1 + E2 + .. En = N, N задано) со следующим свойством, что E1 * E2 * .. En является максимальным

Question

Учитывая число N, напишите программу, которая вычисляет числа E1, E2, ... En со следующими свойствами:

1) N = E1 + E2 + ... + En;
2) E1 * E2 * ... En - максимум.
3) E1..En - целые числа.Нет отрицательных значений:)

Как бы вы это сделали?У меня есть решение, основанное на деление и имперация , но я хочу проверить, является ли оптимальным.

Example: N=10

5,5        S=10,P=25
3,2,3,2    S=10,P=36

Answer 1

Нет необходимости в алгоритме, математическая интуиция может сделать это самостоятельно:

Шаг 1: докажите, что результирующий набор с номерами, превышающими 3, не лучше, чем результирующий набор только с 3 и 2

Учитывая любое число x в вашем наборе результатов, можно подумать, лучше ли разделить его на два числа.

Сумма все равно должна быть x .

• Когда x является четным, максимальное значение для t ( x - t ) достигается при t = x / 2, за исключением специального случая x = 2, тогда он больше x , а для специального случая x = 4, равно x (см. Примечание 1).
• Когда x нечетно, максимальное значение для t ( x - t ) достигается при t = ( x ± 1) /2.

Что это показывает? Только то, что у вас должно быть только 3 и 2 в вашем окончательном наборе, потому что в противном случае он неоптимален (или эквивалентен оптимальному набору).

Шаг 2: у вас должно быть как можно больше 3-х

Теперь, когда 3²> 2³, у вас должно быть как можно больше 3-х, если остаток не равен 1.

Вывод: для каждого N> = 3:

• Если N = 0 mod 3, тогда набор результатов будет только 3
• Если N = 1 mod 3, то результирующий набор имеет одну пару из 2 (или 4), а остальные - 3
• Если N = 2 mod 3, то в наборе результатов будет один 2, а остальные - 3

Пожалуйста, исправьте этот пост. Время, когда я писал хорошо структурированные математические доказательства, далеко ...

Примечание 1: (2,4) - единственная пара различных целых чисел, такая что x ^ y = y ^ x. Вы можете доказать это с помощью:

x^y = y^x
y ln(x) = x ln(y)
ln(x)/x = ln(y) / y

и функция ln(t)/t строго убывает после своего глобального максимума, достигнутого между 2 и 3, поэтому, если вам нужно два различных целых числа, таких как ln(x)/x = ln(y)/y, одно из них должно быть меньше или равно 2. Из этого вы могу сделать вывод, что только (2,4) работает

Answer 2

Это не полное решение, но может помочь.

Прежде всего, обратите внимание, что если вы исправите n, а два члена E_i и E_j отличаются более чем на один (например, 3 и 8), то вы можете добиться большего успеха, "выровняв" их как можно больше, т. Е. если число p = E_i + E_j является четным, то оба условия лучше на p / 2. Если p нечетно, вам лучше заменить его на p / 2 и p / 2 + 1 (где / - целочисленное деление).

Тем не менее, если бы вы знали, каково оптимальное количество терминов, n, вы бы сделали: пусть все E_i равны N / n и N / n + 1 (снова целочисленное деление), так что их сумма по-прежнему N (теперь это простая проблема).

Так что вопрос сейчас в том, что является оптимальным n. Предположим на данный момент, что вам разрешено использовать реальные цифры. Тогда решение будет N / N для каждого члена, и вы можете написать произведение как (N / N) ^ N. Если вы дифференцируете это по n и найдете его корень, вы обнаружите, что n должно быть равно N / e (где e - число Непера, также известное как число Эйлера, e = 2.71828 ....). Поэтому я бы искал решение, где либо n = floor (N / e), либо n = floor (N / e) +1, а затем выбрал бы все E_i, равные либо N / n, либо N / n + 1, как указано выше.

Надеюсь, это поможет.

Answer 3

Онлайн-энциклопедия целочисленных последовательностей дает рекуррентное отношение для решения этой проблемы.

Я оставлю это на усмотрение кого-то другого, чтобы сравнить сложности.Не уверен, что смогу понять сложность метода ОП.