Как решается уравнение x^x?

Question

[Артем Парфёнов]

Уважаемые знатоки матана, напомните пожалуйста быдлокодеру как решаются уравнения типа
x^x = c, где с - известная константа
Вопрос задаю в связи с разбором задач из "Алгоритмов..." Кормена. Внезапно выяснилось, что уравнение видаnlogn = 1000вводит отдельных персонажей в ступор.

Answer 1

[Mrrl]

Уравнение x*ln(x)=c решать проще. Можно методом Ньютона. А можно и итерациями: x_{n+1}=c/ln(x_n), сходиться должно очень быстро.
UPD. Хотя нет, оно будет сходиться только при c>e. Метод Ньютона, всё-таки, надёжнее:
x_{n+1}=(c+x_n)/(ln(x_n)+1)

Answer 2

[throughtheether]

напомните пожалуйста быдлокодеру как решаются уравнения типа
x^x = c, где с - известная константа

Я в свое время решал так:
1) перебором находим такие целые i, i+1, что i^i<=c<=(i+1)^(i+1). В случае равенства возвращаем соответствующее значение.
2) продолжаем при помощи метода деления отрезка пополам (он же метод бисекции, решаемое уравнение имеет вид x^x-c=0), пока длина отрезка не станет меньше некоего порога точности (или значение функции x^x в точке не будет в необходимой окрестности константы c).

Answer 3

[Андрей]

Методом Ньютона (либо же касательных) будет категорически быстрее чем половинным делением, при том, что код будет совсем незначительно посложнее.

Answer 4

[Артем Парфёнов]

Большое спасибо. Жутко дельные комментарии. Жаль, что нельзя поставить 2 галки "Решение" - ответ @thousandsofthem показался мне самым простым (как минимум понятным мне). Не сомневаюсь, что ответ @Mrrl также замечателен, но метод Ньютона, увы, надо еще поднимать. Численные методы забыты напрочь :( почему было не учиться нормально в интитуте?

Comments

[Михаил Захаров]

С каких это пор нельзя отметить два решения!? :)

[Артем Парфёнов]

@zzz77 :) спасибо. С чего вдруг взял, что нельзя ума не приложу