Square Root

Problem #18

Tags: mathematics arithmetic loops classical

Who solved this?

Back to English version

Многие математические задачи в программировании решаются не точно, а приближённо, за несколько повторяющихся операций каждая из которых получает все лучшее приближение.

Давайте рассмотрим этот приём на примере вычисления квадратного корня по следующему способу:

  1. Пусть мы ищем неизвестный корень r из заданного значения X.
  2. Возьмём некоторое начальное приближение, например r = 1 (конечно, это весьма грубо).
  3. Для точного квадратного корня было бы справедливо r = X / r.
  4. Поэтому вычислим d = X / r (оно не будет равно r поскольку r не является точным значением корня).
  5. И возьмём среднее между r и d в качестве нового приближения.

Т.е. полностью формула одного вычислительного шага выглядит так (здесь := означает присваивание):

      r  +  X / r
r := -------------
           2

Вы можете обратиться к статье Square Root Approximation за большими подробностями о вычислении квадратного корня по Методу Герона.

Итак, нам будут даны значение X для которого нужно посчитать приближение квадратного корня и N - количество шагов.
Используем r = 1 как первое приближение и выведем результат после N шагов.

Входные данные содержат количество тест-кейсов в первой строке.
Следующие строки содержат сами тест-кейсы - в каждой будет значение X, корень из которого мы ищем и N - количество шагов.
Ответ должен содержать вычисленные приближения через пробел (с точностью не хуже 1e-7).

Пример:

входные данные:
3
150 0
5 1
10 3

ответ:
1 3 3.196
You need to login to get test data and submit solution.