Art*_*que 2 algorithm recursion sml smlnj square-root
并不是我不明白如何求一个数的整数平方根。我知道使用 Python 和 C++ 查找它们的几种方法。
\n只是这个算法实在是太伤脑筋了。而且必须用 SML 编写它是另一个令人头疼的问题。
\n请帮助我理解这个算法。请注意，这应该使用递归：
\n\n\n的整数平方根是满足 \xc2\xb2\xe2\x89\xa4<(+1)\xc2\xb2 的整数。\n可以使用以下归纳过程计算整数平方根：
\n\n
\n- 递归计算 = div 4 的整数平方根。然后我们有 \xc2\xb2\xe2\x89\xa4<(+1)\xc2\xb2。
\n- 由于 和 是整数，所以我们有 (+1)\xe2\x89\xa4(+1)\xc2\xb2。因此我们有 (2)\xc2\xb2\xe2\x89\xa44\xe2\x89\xa4<4+4\xe2\x89\xa4(2+2)\xc2\xb2。
\n- 因此我们知道 的整数平方根是 2 或 2+1。
\n编写与上述算法相对应的递归 ML 程序。
\n
描述中缺少的部分是所谓的递归的基本情况。这很简单，但有必要指定：0 的整数平方根是 0。通过使用当前值的四分之一（整数除法）的值重复递归，您最终将得到该基本情况。
我对 SML 不太熟悉，但我相信它应该是这样的：
fun intSquareRoot 0 = 0
| intSquareRoot n =
let
val m = n div 4
val i = intSquareRoot m
val k = 2 * i + 1
in
if k * k <= n then k
else k - 1
end;