3968. Квадратный корень

Найдите такое число x, что x² + = C, с точностью не менее 6 десятичных знаков.

Вход. Одно вещественное число C (1.0 ≤ C ≤ 10¹⁰).

Выход.  Выведите искомый корень x с точностью не менее 6 десятичных знаков.

Пример входа	Пример выхода
18.0	4.000000

РЕШЕНИЕ

бинарный поиск

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

Рассмотрим функцию f(x) = x² + . Очевидно, что

· f(0) = 0;

· f(C) = C² + > C;

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

f(x) = С

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

Пример

Рассмотрим график функции f(x) = x² + . Можно заметить что

· f(0) = 0 < C;

· f() = C+ > C;

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

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

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

#define EPS 1e-10

double f(double x)

{

return x * x + sqrt(x);

}

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

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();

}

}