我想找到所有找零的组合。 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 package中
Array中的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”代码通用，但是我认为讨论将属于另一个问题。如果您想了解功能固定点的非常实际的用法，这是一个很好的主题。