On a calculator without a square-root button, find square roots with the Babylonian method (Newton's method).
The first line gives the count t, and each of the next t lines gives one positive integer a.
For each a, calculate as follows.
The first estimate x is a.
Compute the new estimate y = (x + a ÷ x) ÷ 2 and add 1 to the iteration count.
Every division is a floating-point division that keeps the fractional part, and floating-point numbers are double precision.
Stop if the absolute value of the difference between y and x is less than 0.000000001, or if the iteration count reaches 100.
Otherwise replace x with y and calculate again.
So the calculation runs at least once.
For each a, print the iteration count and the last y on one line, separated by one space.
Print y rounded to six decimal places.
So that rounding never sits on a boundary, no a is given for which the fractional part of the last y times 1000000 is between 0.499 and 0.501 inclusive.
Input
1 ≤ t ≤ 100, 1 ≤ a ≤ 10^12, no a makes the fractional part of y × 10^6 fall in 0.499–0.501
Output
one line per a: the iteration count and y with six decimals
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
This loop calculates once and only then asks whether to stop, so do-while fits exactly. C, C++, Java, C#, JS and TS have do { … } while (cond);, and the condition is the condition to continue, so it uses >=. Python and Craykon have no do-while, so enter with while True:/while (true) and leave at the end with break. A plain while that asks first never calculates at all, because x and y start equal. Division trap: Python / and / in JS, TS and Craykon are always floating-point division, but Python // is the integer quotient. In Java, C#, C and C++, a / x is floating-point only if one side is a double, so keep x a double (two integers keep only the quotient). Absolute value trap: the estimate approaches from above, so y - x is negative. Asking y - x < 1e-9 without the absolute value stops on the first round. Floating-point absolute value is Python abs, JS/TS Math.abs, Java Math.abs, C# Math.Abs, C++ std::abs (<cmath>), Craykon Mathf.Abs. C's abs is for int (<stdlib.h>), so a difference of 0.5 becomes 0 and it stops early. In C use fabs (<math.h>). Printing six decimals is Python f"{y:.6f}", JS/TS y.toFixed(6), C/C++ printf("%.6f"), Craykon Str.Fixed(y, 6). Java String.format("%.6f") and C# ToString("F6") follow the machine's regional settings and may print a comma, so pass Locale.ROOT / CultureInfo.InvariantCulture. With a up to 10^12 the last two estimates differ by one double step (about 10^-10), so it always stops, but for much larger a that step is bigger than 10^-9 and the loop might never stop. The limit of 100 rounds is the safety net. Why rounding boundaries are excluded: √999999999999 = 999999.99999949999…, and for this double C, C++, Python, JS and C# round the exact value to 999999.999999, while Java String.format and Craykon Str.Fixed round the shortest form "999999.9999995" and print 1000000.000000.
Pythonmain.py · 13 lines
t = int(input())for _ in range(t): a = int(input()) x = float(a) count = 0 # 파이썬에는 do-while이 없다: while True로 들어가서 끝에서 멈출지 묻는다 while True: y = (x + a / x) / 2 # /는 늘 실수 나눗셈 count += 1 if abs(y - x) < 1e-9 or count == 100: break x = y print(count, f"{y:.6f}")
JavaScriptmain.js · 16 lines
const [t, ...nums] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out = [];for (let i = 0; i < t; i++) { const a = nums[i]; let x = a; let y = a; let count = 0; // 한 번은 꼭 계산한 뒤 멈출지 묻는다 do { x = y; y = (x + a / x) / 2; count++; } while (Math.abs(y - x) >= 1e-9 && count < 100); out.push(count + " " + y.toFixed(6));}console.log(out.join("\n"));
TypeScriptmain.ts · 17 lines
import { readFileSync } from "node:fs";const [t, ...nums]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out: string[] = [];for (let i = 0; i < t; i++) { const a: number = nums[i]; let x: number = a; let y: number = a; let count = 0; // 한 번은 꼭 계산한 뒤 멈출지 묻는다 do { x = y; y = (x + a / x) / 2; count++; } while (Math.abs(y - x) >= 1e-9 && count < 100); out.push(count + " " + y.toFixed(6));}console.log(out.join("\n"));
JavaMain.java · 24 lines
import java.util.Locale;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); StringBuilder out = new StringBuilder(); for (int i = 0; i < t; i++) { long a = sc.nextLong(); double x; double y = a; int count = 0; // 한 번은 꼭 계산한 뒤 멈출지 묻는다 do { x = y; y = (x + a / x) / 2; // x가 double이라 a / x도 실수 나눗셈 count++; } while (Math.abs(y - x) >= 1e-9 && count < 100); out.append(count).append(' ').append(String.format(Locale.ROOT, "%.6f", y)).append('\n'); } System.out.print(out); }}
C#Main.cs · 28 lines
using System;using System.Globalization;using System.Text;class Program{ static void Main() { int t = int.Parse(Console.ReadLine()); var sb = new StringBuilder(); for (int i = 0; i < t; i++) { long a = long.Parse(Console.ReadLine()); double x; double y = a; int count = 0; // 한 번은 꼭 계산한 뒤 멈출지 묻는다 do { x = y; y = (x + a / x) / 2; // x가 double이라 a / x도 실수 나눗셈 count++; } while (Math.Abs(y - x) >= 1e-9 && count < 100); sb.Append(count).Append(' ').Append(y.ToString("F6", CultureInfo.InvariantCulture)).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 22 lines
#include <cmath>#include <cstdio>#include <iostream>int main() { int t; std::cin >> t; for (int i = 0; i < t; i++) { long long a; std::cin >> a; double x; double y = static_cast<double>(a); int count = 0; // 한 번은 꼭 계산한 뒤 멈출지 묻는다 do { x = y; y = (x + a / x) / 2; // x가 double이라 a / x도 실수 나눗셈 count++; } while (std::abs(y - x) >= 1e-9 && count < 100); std::printf("%d %.6f\n", count, y); }}
Cmain.c · 22 lines
#include <math.h>#include <stdio.h>int main(void) { int t; scanf("%d", &t); for (int i = 0; i < t; i++) { long long a; scanf("%lld", &a); double x; double y = (double)a; int count = 0; // 한 번은 꼭 계산한 뒤 멈출지 묻는다 do { x = y; y = (x + a / x) / 2; // x가 double이라 a / x도 실수 나눗셈 count++; } while (fabs(y - x) >= 1e-9 && count < 100); // 실수 절댓값은 fabs printf("%d %.6f\n", count, y); } return 0;}
Craykonmain.cray · 20 lines
t = Console.ReadLine().ToNumber();for (i = 0; i < t; i++){ a = Console.ReadLine().ToNumber(); x = a; y = a; count = 0; // 크레이콘에는 do-while이 없다: 동안 (참)으로 들어가서 끝에서 멈출지 묻는다 while (true) { y = (x + a / x) / 2; // /는 늘 실수 나눗셈 count += 1; if (Mathf.Abs(y - x) < 1e-9 || count == 100) { break; } x = y; } Console.WriteLine(count + " " + Str.Fixed(y, 6));}