Haskell中的整数平方根函数

Question

正整数n的整数平方根是最大整数,其平方小于或等于n.(例如,7的整数平方根是2,而9的整数平方根是3).

这是我的尝试:

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

我猜它不起作用,因为n随着递归的增加而减少,但是由于这是Haskell,你不能使用变量来保持原始的n.

Answer 1

...但由于这是Haskell,你不能使用变量来保留原始的n.

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

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

这足以让你玩,但它不是一个非常有效的实现.在Haskell的维基上可以找到更好的一个:

(^!) :: 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

Answer 2

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

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