Номер 2.2, страница 424 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

2.2.!* В языке программирования нет операции извлечения корня $n$-й степени. Пользуясь определением корня $n$-й степени, запишите алгоритм для нахождения корня $n$-й степени из данного числа (считайте, что искомый корень найден, если $n$-я степень найденного корня отличается от данного числа менее чем на 0,01).

Задача состоит в том, чтобы найти такое число $x$, которое является корнем $n$-й степени из числа $A$. По определению, это означает, что $x^n = A$. Поскольку в языке программирования нет операции извлечения корня, мы должны найти $x$ итерационно. Условие остановки алгоритма — когда $n$-я степень найденного нами приближения $x$ отличается от исходного числа $A$ менее чем на 0,01. Математически это записывается как $|x^n - A| < 0.01$.

Для решения этой задачи идеально подходит метод двоичного поиска (дихотомии). Мы будем искать корень $x$ на некотором числовом отрезке $[L, R]$, постоянно сужая его в два раза.

Принцип работы алгоритма:

1. Определяем начальный отрезок поиска $[L, R]$. Если мы ищем корень из числа $A \ge 1$, то очевидно, что корень будет находиться в диапазоне от 0 до $A$. Если же $0 \le A < 1$, то корень будет находиться в диапазоне от $A$ до 1. Чтобы учесть оба случая, можно взять начальный отрезок $[0, \max(A, 1.0)]$.
2. Находим середину этого отрезка: $M = (L + R) / 2$. Это наше текущее предположение для корня $x$.
3. Возводим $M$ в степень $n$ и сравниваем результат $M^n$ с исходным числом $A$.
4. • Если $M^n$ больше $A$, значит, наше предположение $M$ слишком велико. Искомый корень находится левее, поэтому мы сужаем диапазон поиска до $[L, M]$.
   • Если $M^n$ меньше $A$, значит, наше предположение $M$ слишком мало. Искомый корень находится правее, поэтому мы сужаем диапазон поиска до $[M, R]$.
5. Мы повторяем шаги 2-4 до тех пор, пока не будет выполнено условие $|M^n - A| < 0.01$. Как только условие выполнено, $M$ является искомым корнем с заданной точностью.

Словесный алгоритм:

1. Ввод: Получить на вход неотрицательное число $A$ и натуральную степень корня $n$.
2. Инициализация:
   • Установить левую границу поиска $L = 0$.
   • Установить правую границу поиска $R = A$, если $A \ge 1$, или $R = 1.0$, если $A < 1$. (Универсально: $R = \max(A, 1.0)$).
   • Задать требуемую точность $E = 0.01$.
3. Основной цикл:
   1. Вычислить середину текущего отрезка: $X = (L + R) / 2$.
   2. Вычислить $P = X^n$. Для этого можно использовать цикл, умножая $X$ само на себя $n$ раз, или встроенную функцию возведения в степень (которая обычно доступна).
   3. Проверить условие остановки: если $|P - A| < E$, то перейти к шагу 5.
   4. Скорректировать границы поиска:
      • Если $P > A$, то присвоить $R = X$.
      • Иначе (если $P < A$), присвоить $L = X$.
   5. Вернуться к шагу 3(a).
4. Вывод: Вывести значение $X$ как результат.

Ответ: Алгоритм для нахождения корня $n$-й степени, основанный на методе двоичного поиска, заключается в итеративном сужении диапазона возможных значений корня. На каждом шаге вычисляется середина диапазона $X$, возводится в степень $n$, и в зависимости от сравнения $X^n$ с исходным числом $A$, отбрасывается либо левая, либо правая половина диапазона. Процесс повторяется до тех пор, пока не будет достигнута заданная точность $|X^n - A| < 0.01$.