← 完整题目索引

PROJECT EULER · #0255

舍入平方根

Rounded Square Roots

仅题目 · 已解决原题 ↗

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

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

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

xk+1=⌊xk+⌈n/xk⌉2⌋

直到 xk+1=xk。

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

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

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

注:符号⌊x⌋和⌈x⌉代表下限函数不大于x的最大整数和上限函数不小于x的最小整数分别。

题解待补充

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