你怎么能写一个带'm'和'n'的函数然后乘以'm','n'次？

Question

这是问题:声明类型并定义一个函数,它将2个正数(比如m和n)作为输入,并将m增加到n的幂.请仅使用递归.不要使用幂运算符或库函数,只需使用递归.

到目前为止这是我的代码:

sqr :: Int - > Int - > Int

sqr mn

   | m > 0 && n > 0   = sqr (m * m) (n - 1)
   | otherwise        = m

出于某种原因,当我做sqr 10 2时,它给了我1000或者其他东西.有谁知道我做错了什么？

Answer 1

让我们扩大.此外,您的功能应该被调用pow,而不是sqr,但这并不重要.

sqr 10 2 = sqr (10 * 10) (2 - 1)
         = sqr 100 1
         = sqr (100 * 100) (1 - 1)
         = sqr 10000 0
         = 10000

这证明了原因sqr 10 2 = 10000.

每次你递归,都有不同的价值m.所以你需要以某种方式考虑到这一点:

1. 您可以编写一个有效的版本,即使m每次都有不同的值,或者,

2. 你找到了一种方法来保持m周围的原始值.

我会说最简单的方法使用的事实是m^n = m * m^(n-1),和m^0 = 1.

如果你聪明,那么有一种方法要快得多,这也取决于这个事实m^2n = (m^n)^2.

剧透

我上面写的一些数学公式实际上是有效的Haskell代码.

import Prelude hiding ((^))
infixr 8 ^
(^) :: Int -> Int -> Int
-- Do these two lines look familiar?
m^0 = 1
m^n = m * m^(n-1)

这只是函数的中缀版本.您可以将中缀运算符更改为正常函数,

pow :: Int -> Int -> Int
pow m 0 = 1
pow m n = m * pow m (n - 1)

更快的版本:

pow :: Int -> Int -> Int
pow m 0 = 1
pow m n
  | even n = x * x where x = pow m (n `quot` 2)
  | otherwise = m * pow m (n - 1)