我想找到所有找零的组合。 1,2,5,10,20,50,100 und 200.(1 cent,2cent ..)
如果硬币超过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)

最佳答案

快速解决此问题,从而避免耗尽诸如堆栈之类的计算机资源,要求您重新使用以前计算的部分答案。

让我们假装我们想解决一个类似的问题,我们试图找出仅用1、2或5美分硬币就能赚多少钱的15种方法。我们有两个需要解决的问题-第一个是正确解决问题。二是迅速解决问题。

正确解决问题

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


2 5美分硬币,5 1美分硬币
1个5分硬币,5个1分硬币,1个5分硬币
2个1分硬币,1个5分硬币,2个1分硬币,1个5分硬币,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 packageArray中的Data.Array在Haskell中创建这样的表。

使用表格的总体计划将是-根据我们的函数waysToMake定义表格。 waysToMake会递归到其自身的任何位置,请改为在表中查找结果。在此过程中,我们要处理两个问题。

第一个难题是Array要求数组中的索引是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]

我们可以继续讨论如何使递归函数的“ tabling”,“ memoing”,“ memoizing”或“ dynamic programming”代码通用,但是我认为讨论将属于另一个问题。如果您想了解功能固定点的非常实际的用法,这是一个很好的主题。

10-06 10:16