Задача 255
Округленные квадратные корни

Определим округленный квадратный корень положительного целого числа n как квадратный корень n, округленный в сторону ближайшего целого числа.

Следующая процедура (по-существу, это - применение метода Герона для целочисленной арифметики) находит округленный квадратный корень числа n:

Пусть d - количество цифр числа n.
Если d нечетное число, x_(0) = 2×10^((d-1)⁄2).
Если d четное число, x_(0) = 7×10^( (d-2)⁄2).
Повторять цикл:

до тех пор, пока не будет достигнуто x_(k +1) = x_(k).

В качестве примера, рассмотрим округленный квадратный корень n = 4321.
n состоит из 4 цифр, так что x_(0) = 7×10^((4-2)⁄2) = 70.

Поскольку x_(2) = x_(1), то здесь мы и останавливаемся.
Таким образом, по завершении всего двух итераций нам удалось найти округленный квадратный корень числа 4321, равный 66 (точное значение корня составляет 65.7343137…).

Число необходимых итераций для данного метода на удивление невелико.
К примеру, мы можем найти округленное значение квадратного корня для числа из 5 цифр (10 000 ≤ n ≤ 99 999), выполнив в среднем 3.2102888889 итераций (среднее значение округлено до 10 знаков после десятичной точки).

Используя описанную выше процедуру, определите, чему равно среднее число итераций при нахождении округленного значения квадратного корня для 14-значного числа (10^(13)n < 10^(14))?
Ответ округлите с точностью до 10 знаков после десятичной точки.

Примечание: Символами ⌊x⌋ и ⌈x⌉ обозначают функции округления вниз и округления вверх, соответственно.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net