понимание математического алгоритма, лежащего в основе проблемы TPRODUCT

#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)

Таким образом, умножение превращается в сложение.