2

我想找到硬币找零的所有组合。1、2、5、10、20、50、100 和 200。（1 美分、2 美分 ..）如果硬币超过 500（5 欧元），它应该给 -1。我的代码与这些测试用例完美配合：numOfSplits 10 (11) numOfSplits 20 (41) numOfSplits 100 (4563)。当我尝试使用测试用例 numOfSplits 200 或 500 时，它会给出 C 堆栈溢出错误。我怎样才能使我的代码更好？

numOfSplits :: Integer -> Integer  
numOfSplits a  
    | (abs a) > 500 = -1  
    | (abs a) == 0 = 0  
    | otherwise = intzahler (makeChange [200,100,50,20,10,5,2,1] (abs a) 200)  

intzahler :: [[Integer]] -> Integer  
intzahler array  
    | array == [] = 0  
    | otherwise = 1 + intzahler (tail array)  

makeChange :: [Integer] -> Integer -> Integer -> [[Integer]]  
makeChange coins amount maxCoins  
    | amount < 0  = []  
    | amount == 0 = [[]]  
    | null coins  = []  
    | amount `div` maximum coins > maxCoins = [] -- optimisation  
    | amount > 0  =  
        do x <- coins  
           xs <- makeChange (filter (<= x) coins)  
                            (amount - x)  
                            (maxCoins - 1)  
           guard (genericLength (x:xs) <= maxCoins)  
           return (x:xs)

我将代码更改为此代码，并且不再出现堆栈溢出错误，但现在我的代码运行缓慢。示例：对于 numOfSplits 500 ，它的时间超过 30 分钟，我怎样才能更快地做到这一点？

     numOfSplits :: Integer -> Integer  
numOfSplits a
    | (abs a) > 500 = -1
    | (abs a) == 0 = 0
    | otherwise = fromIntegral . length $ makeChange [200,100,50,20,10,5,2,1] (abs a) 

makeChange :: [Integer] -> Integer ->  [[Integer]]
makeChange coins amount 
   | amount < 0  = []
   | amount == 0 = [[]]
   | null coins  = []
   | amount > 0  =
        do x <- coins
          xs <- makeChange (filter (<= x) coins) (amount - x)
           return (x:xs)
4

2 回答 2

7

快速解决这个问题，从而避免耗尽计算机的资源，例如堆栈，需要您重用之前计算的部分答案。

假设我们想解决一个类似的问题，即我们试图找出仅使用 1、2 或 5 美分硬币有多少种方法可以赚取 15 美分。我们要解决两个问题——第一个是正确解决问题。二是快速解决问题。

正确解决问题

为了正确解决这个问题，我们需要避免重新计算我们已经计算过的硬币组合。例如，我们可以通过以下方式赚取 15 美分：

  • 2个五分硬币，5个一分硬币
  • 1个五分硬币，5个一分硬币，1个五分硬币
  • 2个一分硬币，1个五分硬币，2个一分硬币，1个五分硬币，1个一分硬币

上述所有示例都使用相同的硬币组合。他们都使用 2 个 5 美分硬币和 5 个 1 美分硬币，按不同的顺序计数。

我们可以通过始终以相同的顺序发行我们的硬币来避免上述问题。这提出了一个简单的算法，我们可以通过多少种方式从硬币列表中进行一定数量的更改。我们可以使用第一种类型的硬币，也可以承诺不再使用那种类型的硬币。

waysToMake 0 _             = 1
waysToMake x _     | x < 0 = 0 
waysToMake x []            = 0
waysToMake x (c:cs)        = waysToMake (x-c) (c:cs) + waysToMake x cs

前面的案例涵盖了边界条件。假设没有有问题的零或负值硬币，有1办法制作0. 有一些0方法可以进行负 ( < 0) 的更改。如果您没有可用来找零的硬币类型，就没有办法找零。

让我们看看如果我们尝试评估会发生什么waysToMake 15 [1,2,5]。我们将评估每个waysToMake步骤以保持简短。

waysToMake 15 [1,2,5]

waysToMake 14 [1,2,5] + waysToMake 15 [2,5]

waysToMake 13 [1,2,5] + waysToMake 14 [2,5] + waysToMake 13 [2,5] + waysToMake 15 [5]

waysToMake 12 [1,2,5] + waysToMake 13 [2,5] + waysToMake 12 [2,5] + waysToMake 14 [5]
+ waysToMake 11 [2,5] + waysToMake 13 [5] + waysToMake 10 [5] + waysToMake 15 []

waysToMake 11 [1,2,5] + waysToMake 12 [2,5] + waysToMake 11 [2,5] + waysToMake 13 [5]
+ waysToMake 10 [2,5] + waysToMake 12 [5] + waysToMake 9 [5] + waysToMake 14 []
+ waysToMake 9 [2,5] + waysToMake 11 [5] + waysToMake 8 [5] + waysToMake 13 []
+ waysToMake 5 [5] + waysToMake 10 [] + 0

前三个步骤看起来并不太可疑，但我们已经遇到过waysToMake 13 [2,5]两次。在第四步中，我们看到waysToMake 12 [2, 5], waysToMake 11 [2, 5]，waysToMake 13 [5]所有这些都是我们之前看到的。我们可以看到我们将重复我们生成的大多数其他表达式，这些表达式本身将生成重复表达式的表达式。啊; 我有限的脑力计算机已经在抱怨要做的工作太多了。我们可以寻找更好的顺序来使用（有一个）中的硬币，但它仍然会重复子问题，而子问题本身也会重复子问题等。

快速解决问题

有一种更快的方法可以做到这一点。每一步，我们将使用较少硬币和不使用硬币的数字相加。让我们做一个表格，并在计算时记录每个结果。每一步，我们都需要表格左侧的数字（使用第一个硬币中的一个）和表格下方的一个（不要使用任何第一个硬币）。我们最终将探索整个表格。我们可以从填充边界条件覆盖的左边缘和下边缘的数字开始。

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1  
  [2,5]       1 
    [5]       1 
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

现在我们将添加所有可以从表中已有数字计算的数字。使用 5 美分硬币需要左边的第 5 个位置，以及下方的第 1 个位置。

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1  
  [2,5]       1 
    [5]       1 0 0 0 0 1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

使用 2 美分硬币需要左边的 2 号运动，以及向下的第 1 点。

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1  
  [2,5]       1 0 1
    [5]       1 0 0 0 0 1 0 0 0 0  1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

使用 1 美分硬币需要左边的第 1 点，以及下面的第 1 点。

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1 1 
  [2,5]       1 0 1 0 1
    [5]       1 0 0 0 0 1 0 0 0 0  1  0  0  0  0  1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

我们再走一步。我们可以看到，在另外 13 个简单的步骤中，我们将计算出第一行中 15 的数字，我们就完成了。

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1 1 2 
  [2,5]       1 0 1 0 1 1 1
    [5]       1 0 0 0 0 1 0 0 0 0  1  0  0  0  0  1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

这是所有步骤之后的表格。我的心算机毫不费力地计算出来waysToMake 15 [1,2,5] = 18。

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1 1 2 2 3 4 5 6 7 8 10 11 13 14 16 18
  [2,5]       1 0 1 0 1 1 1 1 1 1  2  1  2  1  2  2
    [5]       1 0 0 0 0 1 0 0 0 0  1  0  0  0  0  1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

如果我们找到更好的顺序来使用（有一个）中的硬币，我们就不需要填写所有表格，但工作量大致相同。

我们可以使用数组包Array中的fromData.Array在Haskell 中制作这样的表。

使用表的一般计划是根据我们的函数定义一个表waysToMake。无论在哪里waysToMake递归到自身，都可以在表格中查找结果。我们在途中有两个皱纹要处理。

第一个问题是 anArray要求数组中的索引是 的实例Ix。我们的硬币列表没有很好的数组索引。相反，我们可以用我们跳过的硬币数量替换硬币列表。0第一行，1第二行，最后一行的硬币列表的长度。

第二个问题是我们想要超越桌子的边缘。我们可以定义一个特殊的查找过程来用 0 填充表外的部分，我们可以更改代码使其永远不会在表外查找，或者我们可以制作一个两倍大的超大表。我将跳过所有这些路线，并检查该值是否属于表的责任部分。

waysToMake x coins = waysToMake' (x,0)
    where
        tabled = tableRange ((0,0),(x,length coins)) waysToMake'
        waysToMake' (n, s) = waysToMake'' n (drop s coins)
            where                    
                waysToMake'' 0  _              = 1
                waysToMake'' n  _     | n <  0 = 0
                waysToMake'' n []              = 0
                waysToMake'' n (c:cs)          = tabled (n-c, s) + tabled (n, s+1)

tableRange创建一个在一定范围内记忆其结果的函数。它构建了Array一个在这些范围内保存函数的惰性求值结果。它返回的函数检查参数是否在边界范围内，如果是，则从表中查找结果，否则直接询问原始函数。

tableRange :: Ix a => (a, a) -> (a -> b) -> (a -> b)
tableRange bounds f = lookup
    where
        lookup x = if inRange bounds x then table ! x else f x
        table = makeArray bounds f

makeArray是一个便利函数，它使包含所提供函数的数组f应用于所提供的每个索引bounds。

makeArray :: Ix i => (i, i) -> (i -> e) -> Array i e
makeArray bounds f = listArray bounds . map f $ range bounds

我们的代码现在几乎可以立即运行，即使对于像waysToMake 10000 [200,100,50,20,10,5,2,1].

我们可以继续讨论如何使递归函数的这种“表格”或“备忘录”或“记忆”或“动态编程”代码通用，但我认为讨论属于不同的问题。如果您想了解函数不动点的非常实际的使用，这是一个很好的主题。

于 2014-11-11T03:06:07.853 回答
0

您是在编译程序还是只是在其中运行它ghci？还有你在什么平台？

numOfSplits 200编译时应该只需要大约 6 秒。

这是您在ideaone.com 上的代码：

https://ideone.com/sBWsvP

对于 180 的输入，它的运行时间不到 5 秒（这是该站点允许的最大运行时间。）

正如Andrew Lorente指出的那样，您的intzahler功能与genericLength甚至相同length，尽管在这种情况下它似乎并没有太大的区别。

于 2014-11-11T01:08:29.553 回答