Вопрос № 90749: Здравствуйте!
Как можно вычислить корень n-ой степени без калькуляторов и подобных средств с максимальной точностью. Нужен сам алгоритм или хотя бы идеи по созданию этого алгоритма.
Ну для примера можно взять алгоритм деления столбиком: делит...
Вопрос № 90.749
Здравствуйте!
Как можно вычислить корень n-ой степени без калькуляторов и подобных средств с максимальной точностью. Нужен сам алгоритм или хотя бы идеи по созданию этого алгоритма.
Ну для примера можно взять алгоритм деления столбиком: делить можно любое число на любое другое, при этом точность зависит только от желания и терпения решающего (1/3=0,3333333333333333... и т.д.).
Думаю, мысль понятна..
Отправлен: 09.06.2007, 20:55
Вопрос задал: Troyan (статус: Студент)
Всего ответов: 2 Мини-форум вопроса >>> (сообщений: 0)
Отвечает: Устинов С.Е.
Здравствуйте, Troyan!
Я так понял, алгоритм нужен именно для подсчета "вручную" - не программа.
Могу предложить такой вариант: алгоритм деления пополам (или еще называют дихотомии).
Допустим, нужно найти корень n-ой степени из числа b. Тогда искать решения будем на отрезке [a;k], где a=0, k=b.
1. Делим отрезок [a;k] пополам точкой c=(a+k)/2.
2. Если cn=b, значит нашли ТОЧНОЕ значение корня, иначе если cn > b рассматриваем дальше отрезок [a;c] если же cn < b, рассматриваем отрезок [c;k]
3. Если длина рассматриваемого отрезка меньше требуемой точности (т.е. например, длина отрезка равна 0,001 - точность - 1 тысячная) - заканчиваем подсчет иначе - идем к пункту 1.
Ответ отправил: Устинов С.Е. (статус: Специалист)
Ответ отправлен: 09.06.2007, 21:11 Оценка за ответ: 5 Комментарий оценки: Спасибо, этот вариант мне известен. Но он слегка не оптимален, нужно что-либо попроще, побыстрее (если придется создавать программу)
Отвечает: SFResid
Здравствуйте, Troyan!
Метод Ньютона:
(Предполагаем, что есть простейший калькулятор – только 4 действия на уровне 2-го класса. У Ньютона и этого не было).
Исходное число – R; показатель – N.
Выбираем начальное приближение X0.
1. Возводим X0 в степень N – 1 (т.е. умножаем на X0 N – 1 раз). Записываем значение X0^(N-1).
2. Это значение X0^(N-1) умножаем на X0 ещё 1 раз. Записываем значение X0^(N).
3. Значение X0^(N-1) умножаем на N. Записываем значение X0^(N-1)*N.
4. Из R вычитаем X^N. Записываем значение R - X^N (не забывая о знаке!)
5. Рез-т п. 4. делим на рез-т п. 3. (с учётом знака!).
6. Рез-т п. 5. прибавляем (с учётом знака!) к X0 – получаем след-е приближение X1
7) Повторяем п.п. 1. – 6. – получаем след-е приближение X2 и т.д. пока рез-т п. 4 станет меньше допустимой погрешности.
(По научному - итерируем формулу X = X + (R - X^N)/(N*X^(N-1)) пока погрешность |R - X^N| не станет меньше заданной - см. http://www.physics.nad.ru/matboard/messages/13606.html)
Ответ отправил: SFResid (статус: Студент)
Ответ отправлен: 11.06.2007, 02:14
