Квадратный корень (#3968)

Анализ алгоритма

Рассмотрим функцию $f (x) = x^{2} + x$ . Очевидно, что:

$f (0) = 0$ ;
$f (C) = C^{2} + C > C$ .

То есть корень уравнения

f (x) = С

лежит на промежутке $[0; C]$ . Функция $f (x)$ строго возрастающая. Ищем корень $x$ бинарным поиском.

Пример

Рассмотрим график функции $f (x) = x^{2} + x$ . Можно заметить что:

$f (0) = 0 < C$ ;
$f (C) = C + C > C$ .

Следовательно корень уравнения $f (x) = С$ лежит на промежутке $[0; C]$ и может быть найден бинарным поиском.

Реализация алгоритма

Объявим константу EPS и функцию f(x).

#define EPS 1e-10

double f(double x)
{
    return x * x + sqrt(x);
}

Основная часть программы. Читаем значение $C$ .

scanf("%lf", &c);

Устанавливаем границы бинарного поиска [left; right] = [0; C].

left = 0; right = c;

Запускаем бинарный поиск.

while (right - left > EPS)
{
    middle = (left + right) / 2;
    y = f(middle);
    if (y > c) right = middle; else left = middle;
}

Выводим ответ.

printf("%lf\n", left);

Java реализация

import java.util.*;

public class Main
{
    static double f(double x)
    {
        return x * x + Math.sqrt(x);
    }

    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        double c = con.nextDouble();
        double left = 0, right = c;

        while (right - left > 1e-10)
        {
            double middle = (left + right) / 2;
            double y = f(middle);
            if (y > c) right = middle; else left = middle;
        }
        System.out.println(left);
        con.close();
    }
}