5

正整数 n 的整数平方根是平方小于或等于 n 的最大整数。（例如，7 的整数平方根为 2，9 的整数平方根为 3）。

这是我的尝试：

intSquareRoot :: Int -> Int
intSquareRoot n
    | n*n > n   = intSquareRoot (n - 1) 
    | n*n <= n  = n

我猜它不起作用，因为 n 根据需要随着递归而减小，但是由于这是 Haskell，您不能使用变量来保留原始 n。

4

4 回答 4

8

...但是由于这是 Haskell，您不能使用变量来保留原始 n。

我不知道是什么让你这么说。以下是你如何实现它：

intSquareRoot :: Int -> Int
intSquareRoot n = aux n
  where
    aux x
      | x*x > n = aux (x - 1)
      | otherwise = x

这足以玩转，但它不是一个非常有效的实现。可以在Haskell 的 wiki上找到更好的：

(^!) :: Num a => a -> Int -> a
(^!) x n = x^n

squareRoot :: Integer -> Integer
squareRoot 0 = 0
squareRoot 1 = 1
squareRoot n =
   let twopows = iterate (^!2) 2
       (lowerRoot, lowerN) =
          last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows
       newtonStep x = div (x + div n x) 2
       iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot)
       isRoot r  =  r^!2 <= n && n < (r+1)^!2
  in  head $ dropWhile (not . isRoot) iters
于 2013-11-13T22:08:18.693 回答
6

您可能没有可编辑的变量，但您可以递归地传递参数......

intSquareRoot :: Int -> Int
intSquareRoot n = try n where
  try i   | i*i > n   = try (i - 1) 
          | i*i <= n  = i

给予

ghci> intSquareRoot 16
4
ghci> intSquareRoot 17
4
于 2013-11-13T22:06:13.593 回答
2

您最初的尝试，以及对 user2989737 的良好修正，尝试了从 n 到解决方案的每个数字。大数字非常慢，复杂度为 O(n)。最好从 0 开始直到解，这将复杂度提高到 O(sqrt n)：

intSquareRoot :: Int -> Int
intSquareRoot n = try 0 where
  try i   | i*i <= n    = try (i + 1) 
          | True        = i - 1

但这是一个使用巴比伦方法（牛顿方法应用于平方根）的更有效的代码：

squareRoot :: Integral t => t -> t
squareRoot n 
   | n > 0    = babylon n
   | n == 0   = 0
   | n < 0    = error "Negative input"
   where
   babylon a   | a > b  = babylon b
               | True   = a
      where b  = quot (a + quot n a) 2

它不如 Pedro Rodrigues 解决方案（GNU 的多精度库算法）快，但它更简单且更易于理解。它还需要使用内部递归来保持原来的 n。

为了使其完整，我将其推广到任何 Integral 类型，检查负输入，并检查 n == 0 以避免除以 0。

于 2014-12-14T00:04:17.473 回答
0

建议的解决方案不起作用，因为n在每个递归调用中都重叠了参数。

以下解决方案使用二进制搜索并在 中找到整数平方根O(log(n))：

intSquareRoot :: Int -> Int
intSquareRoot n = bbin 0 (n+1)
    where bbin a b | a + 1 == b = a
                   | otherwise = if m*m > n
                                 then bbin a m
                                 else bbin m b
                               where m = (a + b) `div` 2

根据平方根所在的位置，[a,b)在每个递归调用（[a,m)或）上将范围除以二。[m,b)

于 2018-08-15T04:44:38.857 回答