#algorithm #math #mathematical-optimization
#алгоритм #математика #математическая оптимизация
Вопрос:
Я пытался решить проблему codechef:http://www.codechef.com/MAY11/problems/TPRODUCT /
Они привели анализ после конкурса здесь:http://www.codechef.com/wiki/may-2011-contest-problem-editorials
Мне нужна некоторая помощь в понимании логики, обсуждаемой там: они говорят об использовании логарифма вместо функции
Pi=max(Vi*PL, Vi*PR)
Математика — не моя сильная сторона. [Я пытался совершенствоваться, участвуя в подобных конкурсах]. Если кто-нибудь может дать очень упрощенное объяснение этой проблемы, это было бы полезно для таких смертных, как я. Спасибо.
Ответ №1:
Одна большая проблема с умножением заключается в том, что числа становятся очень большими очень быстро, и возникают проблемы с достижением верхних границ int или long и переходом к отрицательным значениям. Логарифмирование позволяет нам уменьшить объем вычислений, а затем получить ответ обратно по модулю n.
При воспроизведении результата, найденного с помощью динамического программирования, наивным решением является умножение всех значений вместе, а затем изменение:
(x0 * x1 * x2 * ... * xk) (mod n)
это заменяется серией меньших вычислений, которые позволяют избежать связанного переполнения:
z1 = e^(log(x0) log(x1)) modulo n
z2 = e^(log(x2) log(z1)) modulo n
...
zk = e^(log(xk) log(z{k-1})) modulo n
и затем zk содержит результат.
Комментарии:
1. Это верно, но, как написано, ваш код не имеет преимуществ перед
z1 = (x0 * x1) mod n
,z2 = (x2 * z1) mod n
и т.д.2. Верно, но единственными данными, которые были сохранены в алгоритме, были журналы исходных чисел, поэтому это необходимо. Я включил лишние выражения log () для педантичности.
3. опять же, кажется глупым хранить журналы только тогда, когда, если x1 * x2 слишком велико, то, очевидно, также и e ^ (log (x1) log(x2)) = x1 * x2
Ответ №2:
Предположительно, они полагаются на простое математическое наблюдение, что если:
z = y * x
затем:
log(z) = log(y) log(x)
Таким образом, умножение превращается в сложение.
Комментарии:
1. Спасибо Oli Charlesworth!. Это имеет смысл.