2

Дан массив чисел вида: a0^(a1^(a2^((...)^ak))), где k<10. ( ^ - операция возведения в степень). Каждое из чисел ai <100. Необходимо отсортировать данные числа по возрастанию. Ну вычислять такие огромные числа, я считаю, это не решение, ну потому что как минимум ограничения на время работы 2 секунды. Мой вариант решения. Допустим если ввести в wolfram, например, число 5^4^3^2, то он его преобразует в 10^10^(5.26299...). Завести какую-нибудь структуру, которая будет хранить количество "этажей" и значение самой верхней степени. Ну в таком виде отсортировать уже не предоставит сложности. Вопрос, как представить числа в таком виде? Я пробовал вывести формулы через десятичный логарифм, но у меня получалось что-то 10^(log(ai) + 10^(...)). Ну и в итоге из-за этого слагаемого все равно пришлось бы вычислять предыдущие этажи. Подскажите, каким образом вольфрам преобразовывает числа в такой вид. Ну или предложите свой вариант решения

1 ответ 1

2

Вы прикиньте только что-то типа 50^(50^(50^/* и так 10 раз */...) - тут для получения значения вас не спасет никакое логарифмирование... Кстати, Wolfram тоже не в состоянии оценить, скажем, 50^50^50...

Да и зачем? Вам для упорядочения нужно просто сравнивать числа, и не более того. Попробуйте сравнивать их, логарифмируя (благо логарифм - функция монотонно возрастающая при основании > 1). Первый логарифм все еще дает огромные числа? логарифмируем их второй раз... третий... - словом, пока не станет очевидно, что одно меньше второго.

При этом сами значения логарифмов вам не нужны - только представленные в том же виде приведенные к одному основанию показатели степени.

Игрушечный пример.

10^20^40^30 и 5^40^80^10  

Первое логарифмирование (для определенности - по основанию 10)

20^40^30 и 0.699 * 40^80^10

Второе логарифмирование

1.301*40^30 и -0.15+ 1.602*80^10 - пренебрегаем -0.15

Третье логарифмирование

0.114+1.602*30 и 0.205+1.903*10

Уже можно вычислять и сравнивать :) - понятно, что первое больше...

Примерно так.

6
  • Не сильно понял, что логарифмировать. У меня ведь есть только значения степеней, самого числа у меня нет. Если можно, приведите какой-нибудь игрушечный пример
    – 9Pasha
    17 авг 2017 в 16:34
  • См. дополненный ответ
    – Harry
    17 авг 2017 в 17:03
  • Ну вот когда я пытался вывести формулу, то у меня как раз что-то похожее было - оставалось слагаемое, и я не знал, что с ним делать. Пренебречь? Ну мне почему-то кажется, что при большом количестве степеней это даст большую погрешность. Ну хорошо, я попробую. Спасибо за ответ!
    – 9Pasha
    17 авг 2017 в 17:15
  • При таких числах, грубо говоря, приходится говорить о погрешности в степени степени :), ну, т.е. какова погрешность N в 10^10^10^N... Вряд ли у вас настолько близкие числа, чтобы было нельзя пренебрегать значением порядка единиц по сравнению с 10 в какой-нибудь 20 степени :)
    – Harry
    17 авг 2017 в 17:28
  • Вот снова же, может я что-то не так понял. Но по идее, рано или поздно эти слагаемые станут близки к нулю, то в принципе их можно и не считать? Будет ли корректно, если я напишу что-то типа: double a[len]; //массив значений степеней for(int i=0; i<len-1;i++) a[i+1] = a[i+1] * log(a[i]);
    – 9Pasha
    17 авг 2017 в 17:50

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.