Алгоритм для задачи ProjectEuler 99
От http://projecteuler.net/index.php?section=problems&id=99
Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 37 = 2187.
However, confirming that 632382518061 > 519432525806 would be much more difficult, as both numbers contain over three million digits.
Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.
Как я могу подойти к этому?
@Alnitak: Думаю, готово.
Ответы 4
Не полное решение, но некоторые идеи. Вы можете использовать следующую формулу:
log(ax) = x*loga
Log10 можно легко оценить как количество цифр. Log2 можно легко оценить, посчитав правые сдвиги.
Исходя из вышеизложенного, вы можете значительно сузить список. Для остальных чисел вам нужно будет провести полные вычисления. Разрешены ли математические функции в проекте Эйлер? Если да, то лучше использовать логарифмы.
Здесь журнал вроде отсутствует.
+1. Я перевел его на Python, и он работает как шарм. Примерно так: reduce (lambda a, b: a if a [1] * log (a [0])> b [1] * log (b [0]) else b, base_exp)
nice ~ должен был увидеть возможность формы x * logA
Один из возможных подходов - использовать логарифмические идентификаторы (т. Е. Ab идентичен eb * ln a). Фактически, ab идентичен baseb * logbase a для всех баз, кроме 0 и 1.
Поскольку логарифм является монотонной функцией, вместо ax вы можете сравнить x * log a, чтобы найти максимум. Однако вам может потребоваться числовая точность.
Сравнение экспоненты * log (base) вместо base ^ exponent для каждой строки в файле работает для этой проблемы без учета точности. Это, безусловно, лучшее решение с математической точки зрения, но я просто хотел указать, что в этом нет необходимости.
Другое возможное решение - разделить каждое число в файле на некоторую константу (скажем, 100000) перед выполнением возведения в степень для теперь меньших чисел. Поскольку вы сравниваете все значения друг с другом, уменьшение их всех на постоянный коэффициент не влияет на конечный результат.
Я попытался масштабировать и ошибся. exp * log (base) дал мне правильный ответ за 45 мс. Спасибо!
переформатируйте, чтобы формулы отображались правильно.