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

Уважаемые знатоки матана, напомните пожалуйста быдлокодеру как решаются уравнения типа
x^x = c, где с - известная константа
Вопрос задаю в связи с разбором задач из "Алгоритмов..." Кормена. Внезапно выяснилось, что уравнение видаnlogn = 1000вводит отдельных персонажей в ступор.
  • Вопрос задан
  • 2824 просмотра
Решения вопроса 2
Mrrl
@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)
Ответ написан
Комментировать
@throughtheether
human after all
напомните пожалуйста быдлокодеру как решаются уравнения типа
x^x = c, где с - известная константа
Я в свое время решал так:
1) перебором находим такие целые i, i+1, что i^i<=c<=(i+1)^(i+1). В случае равенства возвращаем соответствующее значение.
2) продолжаем при помощи метода деления отрезка пополам (он же метод бисекции, решаемое уравнение имеет вид x^x-c=0), пока длина отрезка не станет меньше некоего порога точности (или значение функции x^x в точке не будет в необходимой окрестности константы c).
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
Методом Ньютона (либо же касательных) будет категорически быстрее чем половинным делением, при том, что код будет совсем незначительно посложнее.
Ответ написан
Комментировать
getmanartem
@getmanartem Автор вопроса
Большое спасибо. Жутко дельные комментарии. Жаль, что нельзя поставить 2 галки "Решение" - ответ @thousandsofthem показался мне самым простым (как минимум понятным мне). Не сомневаюсь, что ответ @Mrrl также замечателен, но метод Ньютона, увы, надо еще поднимать. Численные методы забыты напрочь :( почему было не учиться нормально в интитуте?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы