Many mathematical problems are solved in programming not precisely, but approximately, by several computations of the result, each of which is more and more close to the goal.
Let us practice the method of approximate calculation of the square root with the following approach:
rof the given value
r = 1as the first approximation (surely it is too rough).
r = X / rshould hold.
d = X / r(it would not be equal to
ris not precise root).
das the new approximation.
E.g. overall formula of the calculation step is (here
:= is an assignment):
r + X / r r := ------------- 2
Refer to Square Root Approximation article for more details on the Heron's Method.
So we are given values
X for which to perform calculations and number of steps
N to perform.
r = 1 at the beginning, and output resulting approximation (after
Input data will give the number of test-cases in first line.
Next lines will contain test-cases themselves, each containing the value
X for which square root should
be calculated and
N - the number of calculation steps.
Answer should contain calculated approximations for each case, separated by space.
input data: 3 150 0 5 1 10 3 answer: 1 3 3.196
Results should have precision of
1e-7 = 0.0000001 or better!