Алгоритм для задачи ProjectEuler 99

Question

С http://projecteuler.net/index.php?section=problems&id=99

Сравнение двух чисел, записанных в индексе форма как 2 ¹¹ и 3 ⁷ не сложно, как и любой калькулятор подтвердит, что 2 ¹¹ = 2048 3 ⁷ = 2187.

Однако, подтверждая, что 632382 ⁵¹⁸⁰⁶¹ > 519432 ⁵²⁵⁸⁰⁶ было бы много сложнее, так как оба числа содержит более трех миллионов цифр.

Использование base_exp.txt (щелкните правой кнопкой мыши и «Сохранить ссылку / цель как ...»), 22K текстовый файл, содержащий тысячу линии с парой база / экспонента на в каждой строке определить, какой номер строки имеет наибольшее числовое значение.

Как я могу подойти к этому?

Answer 1

Не полное решение, но некоторые идеи. Вы можете использовать следующую формулу:

log (a ^x ) = x * loga

Log10 легко оценить как количество цифр. Log2 можно легко оценить, посчитав правые сдвиги.

Исходя из вышеизложенного, вы можете значительно сузить список. Для остальных чисел вам придется сделать полные расчеты. Разрешены ли математические функции в проекте Эйлера? Если да, то лучше использовать логарифмы.

Answer 2

Поскольку логарифм является монотонной функцией, вместо ^x вы можете сравнить x * log a, чтобы найти максимум. Возможно, вам придется учитывать числовую точность.

Answer 3

Сравнение показателя степени * log (base) вместо base ^ exponent для каждой строки в файле работает для этой проблемы без учета точности. Это, безусловно, лучшее решение с математической точки зрения, но я просто хотел подчеркнуть, что в этом нет необходимости.

Другое возможное решение состоит в том, чтобы разделить каждое число в файле на некоторую константу (скажем, 100 000) перед выполнением возведения в степень для теперь меньших чисел. Поскольку вы сравниваете все значения друг с другом, уменьшение их всех на постоянный коэффициент не влияет на конечный результат.

Answer 4

Один из возможных подходов - использовать логарифмические тождества (то есть a ^b идентичен e ^{b * ln a} ). Фактически, a ^b идентичен базе ^{b * log _base a} для всех баз, кроме 0 и 1.