Из заданного числа определите три близких числа, произведение которых является исходным числом.

Question

У меня есть число n, и я хочу найти три числа, произведение которых равно n, но как можно ближе друг к другу.То есть, если n = 12, то я бы хотел получить 3, 2, 2 в результате, а не 6, 1, 2.

Еще один способ думать об этом состоит в том, что если nэто объем кубоида, тогда я хочу найти длины сторон, чтобы сделать кубоид как можно больше похожим на куб (то есть длины как можно ближе).Эти числа должны быть целыми числами.

Я знаю, что вряд ли найдется идеальное решение для этого, и я рад использовать что-то, что дает хороший ответ большую часть времени, но я просто не могу думатькуда идти с придумывать этот алгоритм.Есть идеи?

Answer 1

Вот мой первый набросок алгоритма, при условии, что n относительно мал:

• Вычислить простые множители из n.
• Выберите три самых больших и назначьте их f1, f2, f3. Если факторов меньше трех, присвойте 1.
• Цикл по оставшимся факторам в порядке убывания , умножьте их на самый маленький на данный момент раздел.

---

Редактировать

Давайте возьмем n=60.

Его главные факторы 5 3 2 2.

Набор f1=5, f2=3 и f3=2.

Оставшиеся 2 умножаются на f3, потому что это наименьшее.

Мы получаем 5 * 4 * 3 = 60.

---

Редактировать

Этот алгоритм не найдет оптимальный, обратите внимание btillys комментарий:

Рассмотрим 17550 = 2 * 3 * 3 * 3 * 5 * 5 * 13. Ваш алгоритм выдаст 15, 30, 39, когда лучшим будет 25, 26, 27.

---

Редактировать

Хорошо, вот мой второй набросок алгоритма с немного лучшей эвристикой:

• Установите список L для простых множителей из n.
• Установите r в корень куба из n.
• Создайте набор из трех факторов F, изначально установленный на 1.
• Перебираем простые множители в порядке убывания:
  • Попробуйте умножить текущий коэффициент L[i] на каждый из факторов в порядке убывания.
    • Если результат меньше r, выполнить умножение и перейти к следующему главный фактор.
    • Если нет, попробуйте следующий F. Если из F с, умножьте на наименьшее.

Это будет работать для случая 17550:

n=17550
L=13,5,5,3,3,3,2
r=25.98

F = { 1, 1, 1 }

Итерация 1:

• F[0] * 13 меньше r, установите F на {13,1,1}.

Итерация 2:

• F[0] * 5 = 65 смазан чем r.
• F[1] * 5 = 5 меньше r, установите F на {13,5,1}.

Итерация 3:

• F[0] * 5 = 65 смазано чем r.
• F[1] * 5 = 25 меньше r, установите F на {13,25,1}.

Итерация 4:

• F[0] * 3 = 39 смазано чем r.
• F[1] * 3 = 75 смазано чем r.
• F[2] * 3 = 3 меньше r, установите F на {13,25,3}.

Итерация 5:

• F[0] * 3 = 39 смазано чем r.
• F[1] * 3 = 75 смазано чем r.
• F[2] * 3 = 9 меньше r, установите F на {13,25,9}.

Итерация 6:

• F[0] * 3 = 39 смазан чем r.
• F[1] * 3 = 75 смазано чем r.
• F[2] * 3 = 27 больше r, но это наименьшее число F, которое мы можем получить. Установите F на {13,25,27}.

Итерация 7:

• F[0] * 2 = 26 смазаннее, чем r, но это наименьшее число F, которое мы можем получить. Установите F на {26,25,27}.

Answer 2

Это чисто математический подход, который возвращает оптимальное решение и не требует какой-либо сортировки. Черт, ему даже не нужны главные факторы.

Справочная информация:

1) Напомним, что для полинома

сумма и произведение корней определяются как

где x_i - корни.

2) Напомним еще один элементарный результат теории оптимизации:

Т.е., учитывая две переменные, так что их произведение является константой, сумма является минимальной, когда две переменные равны друг другу. Переменные тильды обозначают оптимальные значения.

Следствием этого будет то, что если сумма двух переменных, произведение которых является постоянным, является минимумом, то эти две переменные равны друг другу.

Переформулируйте исходную задачу:

Ваш вопрос выше теперь может быть переформулирован как полиномиальное упражнение по поиску корней. Мы построим полином, который удовлетворяет вашим условиям, и корни этого полинома будут вашим ответом. Если вам нужно k чисел, которые являются оптимальными, у вас будет многочлен степени k. В этом случае мы можем говорить в терминах кубического уравнения

Мы знаем, что:

1. c является отрицательным значением введенного числа (предположим, положительным)
2. a является целым и отрицательным (поскольку все факторы положительны)
3. b является целым числом (которое является суммой корней, взятых по два за раз) и является положительным.
4. Корни p должны быть реальными (и положительными, но это уже было решено).

Чтобы решить проблему, нам просто нужно максимизировать a с учетом вышеуказанного набора условий. Единственная часть, которая прямо не известна прямо сейчас, это условие 4, которое мы можем легко выполнить, используя дискриминант полинома .

Для кубического полинома p дискриминант равен

и p имеют действительные и отличные корни, если ∆>0, и действительные и совпадающие (либо два, либо все три), если ∆=0. Итак, ограничение 4 теперь читается как ∆>=0. Теперь это просто и легко программировать.

Решение в Mathematica

Вот решение в Mathematica, которое реализует это.

А вот проверка некоторых чисел, использованных в других ответах / комментариях.

Столбец слева - это список, а соответствующая строка в столбце справа - оптимальное решение.

Примечание:

Я только что заметил, что OP никогда не упоминал, что эти 3 числа должны быть целыми числами, хотя каждый (включая меня до сих пор) предполагал, что они были (вероятно, из-за его первого примера). Перечитывая вопрос и следуя примеру куба, кажется, что OP не зациклен на целых числах.

Это важный момент, который решает, какой класс алгоритмов использовать и который необходимо определить. Если они не должны быть целыми числами, существует несколько решений на основе полиномов, одно из которых моё (после ослабления целочисленного ограничения). Если они должны быть целыми числами, то, возможно, подход с использованием ветви-n-границ / ветвей-n-вырезать / разрезать более уместен.

Следующее было написано, предполагая, что ОП означало, что три числа были целыми числами.

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

Причина, по которой это дает нецелочисленные решения для x, заключается в том, что я только максимизировал a, тогда как на самом деле b также должен быть минимальным (не только это, но и потому, что я не поместил ограничение на x_i, являющееся целыми числами. Можно использовать целочисленную корневую теорему , которая включала бы поиск простых факторов, но усложняла ситуацию.)

Mathematica код в тексте

Clear[poly, disc, f]
poly = x^3 + a x^2 + b x + c;
disc = Discriminant[poly, x];
f[n_Integer] := 
 Module[{p, \[CapitalDelta] = disc /. c -> -n}, 
  p = poly /. 
     Maximize[{a, \[CapitalDelta] >= 0, 
        b > 0 && a < 0 && {a, b} \[Element] Integers}, {a, b}][[
      2]] /. c -> -n;
  Solve[p == 0]
  ]

Answer 3

Может быть умный способ найти самый плотный триплет, как Андерс Линдал преследует, но я остановлюсь на более базовом подходе.

Если я сгенерирую всех триплетов, тогдаЯ могу отфильтровать их потом, как захочу, поэтому начну с них.Наилучший из известных мне способов их генерации использует рекурсию:

---

f[n_, 1] := {{n}}

f[n_, k_] := Join @@
    Table[
      {q, ##} & @@@ Select[f[n/q, k - 1], #[[1]] >= q &],
      {q, #[[2 ;; ⌈ Length@#/k ⌉ ]] & @ Divisors @ n}
    ]

Эта функция f принимает два целочисленных аргумента: число для множителя n и число факторов для получения k.

Секция #[[2 ;; ⌈ Length@#/k ⌉ ]] & @ Divisors @ n использует Divisors для получения списка всех делителей n (включая 1), а затем берет из них второй (чтобы сбросить 1)) до потолка числа делителей, деленного на k.

Например, для {n = 240, k = 3} вывод равен {2, 3, 4, 5, 6, 8}

Команда Table выполняет итерации по этому списку, поканакапливая результаты, присваивая каждому элементу q.

Тело Table равно Select[f[n/q, k - 1], #[[1]] >= q &].Это вызывает f рекурсивно, а затем выбирает из результата все списки, которые начинаются с номера >= q.

{q, ##} & @@@ (также в теле), а затем «предваряют» q к каждому из этихвыбранные списки.

Наконец, Join @@ объединяет списки этих выбранных списков, которые создаются каждым циклом Table.

---

Результатом являются все целочисленные множителиn на k частей, в лексикографическом порядке.Пример:

In[]:= f[240, 3]

Out[]= {{2, 2, 60}, {2, 3, 40}, {2, 4, 30}, {2, 5, 24}, {2, 6, 20},
        {2, 8, 15}, {2, 10, 12}, {3, 4, 20}, {3, 5, 16}, {3, 8, 10},
        {4, 4, 15}, {4, 5, 12}, {4, 6, 10}, {5, 6, 8}}

---

С выходом функции / алгоритма, приведенным выше, можно затем протестировать триплеты на качество как угодно.

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

Если должен быть найден истинный оптимум, имеет смысл проверить, начиная с правой стороны списка, отказавшись от поиска.если лучший результат не может быть быстро найден, так как качество результатов уменьшается при перемещении влево.

---

Очевидно, что этот метод основан на быстрой Divisors функции, но я предполагаю, что это либостандартная функция библиотеки, или вы можете найти хорошую реализацию здесь, на StackOverflow.С этим на месте это должно быть довольно быстро.Код выше находит все триплеты для n от 1 до 10000 за 1,26 секунды на моей машине.

Answer 4

Вместо того, чтобы заново изобретать колесо, следует признать это как вариацию хорошо известной NP-полной проблемы.

• Вычислить основные факторы n.
• Вычислить логарифмы этих факторов
• Проблема переводится в разделение этих журналов на три суммы, которые являются максимально близкими.
• Эта проблема известна как изменение Bin Packing проблема, известная как Многопроцессорное планирование

Учитывая тот факт, что проблема многопроцессорного планирования является NP-полный, неудивительно, что трудно найти алгоритм, который не ищет всю проблемную область и находит оптимальное решение.

Но я думаю, что уже есть несколько алгоритмов, которые имеют дело с Bin-Packing или Multiprocessor-Планирование и поиск почти оптимальных решений эффективным способом.

Другая связанная проблема (обобщение) - это Планирование работы магазина .См. Описание википедии со многими ссылками на известные алгоритмы.

---

Что википедия описывает как (часто используемый алгоритм LPT (самое длительное время обработки) именно то, что придумал Андерс Линдаль первым.

Answer 5

РЕДАКТИРОВАТЬ Вот более короткое объяснение с использованием более эффективного кода, KSetPartitions значительно упрощает работу.Так же поступили некоторые предложения от мистера В.Общая логика остается той же.

Предполагая, что есть хотя бы 3 простых множителя n ,

1. Найдите список триплетов KSetPartitions для простого числафакторы n .
2. Умножьте каждый из элементов (простых факторов) в каждом подмножестве, чтобы получить все возможные комбинации для трех делителей n (при умножении они дают п ).Вы можете думать о делителях как о длине, ширине и высоте ортогонального параллелепипеда.
3. Ближайший к кубу параллелепипед будет иметь самую короткую диагональ.Суммируйте квадраты трех делителей для каждого случая и выберите наименьшее.

---

Вот код в Mathematica:

Needs["Combinatorica`"]
g[n_] := Module[{factors = Join @@ ConstantArray @@@ FactorInteger[n]},
  Sort[Union[Sort /@ Apply[Times, Union[Sort /@ 
      KSetPartitions[factors, 3]], {2}]] 
      /. {a_Integer, b_Integer, c_Integer} :>  
           {Total[Power[{a, b, c}, 2]], {a, b, c}}][[1, 2]]]

---

Он может обрабатывать довольно большие числа, но значительно замедляется по мере роста числа факторов n.В приведенных ниже примерах показано время для 240, 2400, ... 24000000.В принципе это можно ускорить, принимая во внимание случаи, когда главный фактор появляется в делителе более одного раза.У меня пока нет ноу-хау, чтобы это сделать.

In[28]:= g[240]

Out[28]= {5, 6, 8}

In[27]:= t = Table[Timing[g[24*10^n]][[1]], {n, 6}]

Out[27]= {0.001868, 0.012734, 0.102968, 1.02469, 10.4816, 105.444}