Integer 数字的平方根

Question

并不是我不明白如何求一个数的整数平方根。我知道使用 Python 和 C++ 找到它们的几种方法。

只是这个算法实在是太伤脑筋了。不得不用 SML 编写它是另一个令人头疼的问题。

请帮助我理解这个算法。请注意，这应该使用递归：

The integer square root of is the integer such that ²≤<(+1)². The integer square root can be computed using the following inductive process:

Compute the integer square root of = div 4 recursively. We then have that ²≤<(+1)².

Since and are integers, we have that (+1)≤(+1)². We thus have (2)²≤4≤<4+4≤(2+2)².

Hence we have that the integer square root of is either 2 or 2+1.

Write a recursive ML program corresponding to the above algorithm.

Answer 1

描述中缺少的部分是递归的so-called 基本情况。这是微不足道的，但有必要指定：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;

Integer 数字的平方根

Integer Square root of a number

algorithm

recursion

sml

smlnj

square-root