← 完整题目索引

PROJECT EULER · #0255

舍入平方根

Rounded Square Roots

仅题目 · 已解决原题 ↗

我们将正整数 n舍入平方根定义为四舍五入到最接近整数的 n 的平方根。

以下过程(本质上是适用于整数算术的 Heron 方法)查找 n 的舍入平方根:

d 为号码 n 的位数。
如果d为奇数,则设置x0=2×10(d1)/2
如果 d 为偶数,则设置 x0=7×10(d2)/2
重复:

xk+1=xk+n/xk2

直到 xk+1=xk

作为示例,让我们求 n=4321 的舍入平方根。
n 具有 4 数字,因此 x0=7×10(42)/2=70
x1=70+4321/702=66 x2=66+4321/662=66x2=x1 开始,我们就到此为止。
因此,经过两次迭代,我们发现 4321 的舍入平方根是 66(实际平方根是 65.7343137)。

使用此方法时所需的迭代次数非常低。
例如,我们可以找到 5 位整数 (10000n99999) 的舍入平方根,其平均值为 3.2102888889 次迭代(平均值四舍五入到 10 小数位)。

使用上述过程,找到 14 位数 (1013n<1014) 的舍入平方根所需的平均迭代次数是多少?
将您的答案四舍五入到 10 小数位。

注:符号xx代表下限函数不大于x的最大整数上限函数不小于x的最小整数分别。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。