algorithm - 找到除以haskell的阶乘的数字的最大幂

Question

所以我正在编写一个 haskell 程序来计算除阶乘的数的最大幂。

largestPower :: Int -> Int -> Int

这里 largestPower a b 找到了 b 的最大幂，它能整除 a!。

现在我明白了它背后的数学原理，找到答案的方法是重复将a(只是a)除以b，忽略余数，最后将所有相加商。所以如果我们有类似的东西

largestPower 10 2

我们应该得到 8 因为 10/2=5/2=2/2=1 并且我们加上 5+2+1=8

但是，我无法弄清楚如何将其作为一个函数来实现，我是使用数组还是只使用一个简单的递归函数。

我倾向于它只是一个普通函数，但我想这可以通过将商存储在数组中并相加来完成。

Answer 1

没有累加器的递归

您可以简单地编写一个递归算法并对每次调用的结果求和。这里我们有两种情况:

• a 小于b，此时最大的幂为0。所以:

  largestPower a b | a < b = 0
  

• a 大于或等于 b，在这种情况下，我们将 a 除以 b >，计算该除法的 largestPower，并将除法添加到结果中。喜欢:

                   | otherwise = d + largestPower d b
                   where d = (div a b)
  

或者放在一起:

largestPower a b | a < b = 1
                 | otherwise = d + largestPower d b
                 where d = (div a b)

使用累加器递归

您还可以将递归与累加器一起使用:您通过递归传递的变量，并相应地进行更新。最后，您返回该累加器(或在该累加器上调用的函数)。

这里的累加器当然是除法的运行乘积，所以:

largestPower = largestPower' <b>0</b>

所以我们将定义一个函数 largestPower'(注意重音)，将累加器作为第一个参数，初始化为 1。

现在在递归中，有两种情况:

• a 小于 b，我们简单地返回累加器:

  largestPower' r a b | a < b = r
  

• 否则，我们将累加器与 b 相乘，并通过递归调用将除法传递给 largestPower':

                      | otherwise = largestPower' (d+r) d b
                      where d = (div a b)
  

或完整版:

largestPower = largestPower' 1

largestPower' r a b | a < b = r
                    | otherwise = largestPower' (d+r) d b
                    where d = (div a b)

朴素的正确算法

算法不正确。一个“天真的”算法是简单地划分每个项目并保持递减直到达到 1，例如:

largestPower 1 _ = 0
largestPower a b = sumPower a + largestPower (a-1) b
    where sumPower n | n `mod` b == 0 = 1 + sumPower (div n b)
                     | otherwise = 0

所以这意味着对于 largestPower 4 2，这可以写成:

largestPower 4 2 = sumPower 4 + sumPower 3 + sumPower 2

和:

sumPower 4 = 1 + sumPower 2
           = 1 + 1 + sumPower 1
           = 1 + 1 + 0
           = 2

sumPower 3 = 0

sumPower 2 = 1 + sumPower 1
           = 1 + 0
           = 1

所以 3。