Основы программирования

         

вычисление квадратного корня методом деления отрезка пополам


Метод вычисления корня функции с помощью деления отрезка пополам в общем случае уже был рассмотрен в разделе 1.5.2. Пусть надо найти квадратный корень из неотрицательного вещественного числа a с заданной точностью ?. Задача сводится к нахождению корня функции

y = x2-a

на отрезке [0,b], где b = max(1,a). На этом отрезке функция имеет ровно один корень, поcкольку она монотонно возрастает и на концах отрезка принимает значения разных знаков (или нулевое значение при a = 0 или a = 1).

Идея алгоритма состоит в том, что отрезок делится пополам и выбирается та половина, на которой функция принимает значения разных знаков. Эта операция повторяется до тех пор, пока длина отрезка не станет меньше, чем ?. Концы текущего отрезка содержатся в переменных x0, x1. В данном случае функция монотонно возрастает при x

0. Инвариантом цикла является утверждение о том, что функция принимает отрицательное или нулевое значение в точке x0 и положительное или нулевое значение в точке x1. Цикл рано или поздно завершается, поскольку после каждого выполнения тела цикла длина отрезка [x0,x1] уменьшается в два раза.

Приведем полный текст программы:

#include <stdio.h> // Описания стандартного ввода-вывода

int main() { double a; // Число, из которого извлекается корень double x, x0, x1; // [x0, x1] - текущий отрезок double y; // Значение ф-ции в точке x double eps = 0.000001; // Точность вычисления корня

printf("Введите число a:\n"); scanf("%lf", &a);

if (a < 0.0) { printf("Число должно быть неотрицательным.\n"); return 1; // Возвращаем код } // некорректного завершения

// Задаем концы отрезка x0 = 0.0; x1 = a; if (a < 1.0) { x1 = 1.0; }

// Утверждение: x0 * x0 - a <= 0, // x1 * x1 - a >= 0

while (x1 - x0 > eps) { // Инвариант: x0 * x0 - a <= 0, // x1 * x1 - a >= 0 x = (x0 + x1) / 2.0; // середина отрезка [x0,x1] y = x * x - a; // значение ф-ции в точке x

if (y >= 0.0) { x1 = x; // выбираем левую половину отрезка } else { x0 = x; // выбираем правую половину отрезка } }

// Утверждение: x0 * x0 - a <= 0, // x1 * x1 - a >= 0, // x1 - x0 <= eps x = (x0 + x1) / 2.0; // Корень := середина отрезка

// Печатаем ответ printf("Квадратный корень = %lf\n", x);

return 0; // Возвращаем код успешного завершения }

Отметим, что существует более быстрый способ вычисления квадратного корня числа - метод итераций Ньютона, или метод касательных к графику функции, но здесь мы его не рассматриваем.



Содержание раздела