计算 Haskell 给定变化量的最小硬币数量
Calculate the Minimum Number of Coins For Given Amount of Change in Haskell
我正在尝试为 Change-making problem 编写算法。
我假设硬币系统是规范的，这意味着总是选择小于剩余数量的最大硬币的贪婪算法是一个最优算法。
coinChange 是算法的函数。输入是给定硬币系统的货币数量和面额。该函数输出每种面额所需的最少硬币数量。
例如：
Input : coinChange 34 [1, 5, 10, 25, 50, 100]
Output : [4,1,0,1,0,0]
coinChange 的类型声明是：
coinChange :: Integer -> [Integer] -> [Integer]
我找到了这个解决方案并且我明白它为什么有效：
coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds = (coinChange (c `rem` d) (init ds) ) ++ [c `quot` d]
where d = last ds
但是，当我尝试制定自己的解决方案时，我收到了几条错误消息。
起初，我试过：
coinChange c [] = []
coinChange c ds = reverse ( (c `quot` x): coinChange (c `rem` x) xs )
where (x:xs) = reverse ds
我试过颠倒硬币面额的顺序，所以我先从最大的开始。我认为这比使用 last 和 init.
更方便
当我 运行 我得到：
coinChange 64 [1,2,5,10,20,50,100]
[64,0,0,0,0,0,0]
我这里得到64好像很奇怪
如果我使用递归函数，我认为在整个列表上使用 reverse 会造成混淆，因为列表的某些部分会被多次反转。所以我尝试了这个：
coinChange c [] = []
coinChange c ds =reverse( (c `quot` x):(coinChange' (c `rem` x) xs ))
where (x:xs) = (reverse ds)
coinChange' c [] = []
coinChange' c ds = (c`quot`x):(coinChange' (c `rem` x) xs )
where (x:xs) = reverse ds
如果我尝试：
coinChange 64 [1,2,5,10,20,50,100]
我以为我会得到 [0,2,0,1,0,1,0] 作为我的最终输出：
(64 `quot` 100):(coinChange' (64 `rem` 100) [1,2,5,10,20,50])
0:((64`quot`50):coinChange' (64`rem`50) [1,2,5,10,20])
0:(1:coinChange' 14 [1,2,5,10,20])
0:(1:((14`quot` 20):coinChange' (14 `rem` 20) [1,2,5,10]))
0:(1:(0:coinChange 14 [1,2,5,10]))
0:(1:(0:((14`quot` 10) : coinChange' (14 `rem` 10) [1,2,5])))
0:(1:(0:( 1 : coinChange' (14 `rem` 10) [1,2,5])))
0:(1:(0:( 1 : coinChange' 4 [1,2,5])))
0:(1:(0:( 1 : ((4 `quot` 5):coinChange' (4`rem` 5) [1,2]))))
0:(1:(0:( 1 : (0:coinChange' 4 [1,2]))))
0:(1:(0:( 1 : (0:((4`quot`2):coinChange (4`rem`2) [1])))))
0:(1:(0:( 1 : (0:(2:coinChange 0 [1])))))
0:(1:(0:( 1 : (0:(2:((0`quot`1):coinChange' (0`rem` 1) []))))))
0:(1:(0:( 1 : (0:(2:(0:coinChange' 0 []))))))
0:(1:(0:( 1 : (0:(2:(0:[]))))))
reverse [0,1,0,1,0,2,0]
final output: [0,2,0,1,0,1,0]
但是，当我在终端中 运行 这段代码时，我得到：
coinChange 64 [1,2,5,10,20,50,100]
[0,0,0,0,0,64,0]
为什么我的方法不起作用？
然后我尝试了：
coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds = reverse( (c `quot` x): coinChange' (c `rem` x) xs )
where (x:xs) = reverse ds
coinChange' 0 ds = take (length ds) (repeat 0)
coinChange' c ds = (c `quot` x): coinChange' (c `rem` x) xs
where (x:xs) = reverse ds
我从已经可用的解决方案中提取了行 coinChange 0 ds = take (length ds) (repeat 0)。
然而，当我在终端中 运行 这段代码时，我得到了同样的错误：
coinChange 64 [1,2,5,10,20,50,100]
[0,0,0,0,0,64,0]
我认为主要问题在于 where (x:xs) = reverse ds。为什么这部分代码没有按照我预期的方式工作？
当我使用 let 而不是 where 时，我仍然遇到同样的错误。
coinChange 0 ds = take (length ds) (重复0)
coinChange c ds = let (x:xs) = 反转 ds
in reverse( (c quot x): coinChange' (c rem x) xs )
coinChange' 0 ds = take (length ds) (重复0)
coinChange' c ds = let (x:xs) = reverse ds
in (c quot x): coinChange' (c rem x) xs
我认为问题可能是我正在使用 (x:xs)。
所以，我尝试了：
coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds = let xs = reverse ds
in reverse( (c `quot` (head xs)): coinChange' (c `rem` (head xs)) (tail xs) )
coinChange' 0 ds = take (length ds) (repeat 0)
coinChange' c ds = let xs = reverse ds
in (c `quot` (head xs)): coinChange' (c `rem` (head xs)) (tail xs)
这仍然给出了同样的错误。
我尝试使用连接运算符 (++)，而不是前置运算符 :，看看是否有帮助：
coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds = let xs = reverse ds
in coinChange (c `rem` (head xs)) (tail xs) ++ [c `quot` (head xs)]
我在使用这段代码时仍然遇到同样的错误。
看来问题一定出在我反转硬币面额列表的方法上。
为什么我的所有尝试都失败了？当商数应该为 1 时，为什么 64 总是出现此错误？
在这个回答中，我将重点介绍您的尝试：
coinChange c [] = []
coinChange c ds =reverse( (c `quot` x):(coinChange' (c `rem` x) xs ))
where (x:xs) = (reverse ds)
coinChange' c [] = []
coinChange' c ds = (c`quot`x):(coinChange' (c `rem` x) xs )
where (x:xs) = reverse ds
我认为问题确实出在coinChange'函数中的where (x:xs) = reverse ds部分。每个递归调用都会反转面额列表。因此，您从 where 子句中的模式匹配得到的 xs 是没有最大面额的倒序面额列表。但是该列表仍然是相反的，因此您不应将其作为参数再次传递给 coinChange 或 coinChange' 函数。您可以在将其传递给递归调用之前再次反转此列表，但效率不高。我建议只反转 coinChange 函数中的面额。
另外，coinChange函数可以简化，因为它基本上只需要反转面额和结果列表。
这是它的样子：
coinChange c ds = reverse (coinChange' c (reverse ds))
coinChange' c [] = []
coinChange' c (x:xs) = (c `quot` x) : coinChange' (c `rem` x) xs
我正在尝试为 Change-making problem 编写算法。
我假设硬币系统是规范的，这意味着总是选择小于剩余数量的最大硬币的贪婪算法是一个最优算法。
coinChange 是算法的函数。输入是给定硬币系统的货币数量和面额。该函数输出每种面额所需的最少硬币数量。
例如：
Input : coinChange 34 [1, 5, 10, 25, 50, 100]
Output : [4,1,0,1,0,0]
coinChange 的类型声明是：
coinChange :: Integer -> [Integer] -> [Integer]
我找到了这个解决方案并且我明白它为什么有效：
coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds = (coinChange (c `rem` d) (init ds) ) ++ [c `quot` d]
where d = last ds
但是，当我尝试制定自己的解决方案时，我收到了几条错误消息。
起初，我试过：
coinChange c [] = []
coinChange c ds = reverse ( (c `quot` x): coinChange (c `rem` x) xs )
where (x:xs) = reverse ds
我试过颠倒硬币面额的顺序，所以我先从最大的开始。我认为这比使用 last 和 init.
当我 运行 我得到：
coinChange 64 [1,2,5,10,20,50,100]
[64,0,0,0,0,0,0]
我这里得到64好像很奇怪
如果我使用递归函数，我认为在整个列表上使用 reverse 会造成混淆，因为列表的某些部分会被多次反转。所以我尝试了这个：
coinChange c [] = []
coinChange c ds =reverse( (c `quot` x):(coinChange' (c `rem` x) xs ))
where (x:xs) = (reverse ds)
coinChange' c [] = []
coinChange' c ds = (c`quot`x):(coinChange' (c `rem` x) xs )
where (x:xs) = reverse ds
如果我尝试：
coinChange 64 [1,2,5,10,20,50,100]
我以为我会得到 [0,2,0,1,0,1,0] 作为我的最终输出：
(64 `quot` 100):(coinChange' (64 `rem` 100) [1,2,5,10,20,50])
0:((64`quot`50):coinChange' (64`rem`50) [1,2,5,10,20])
0:(1:coinChange' 14 [1,2,5,10,20])
0:(1:((14`quot` 20):coinChange' (14 `rem` 20) [1,2,5,10]))
0:(1:(0:coinChange 14 [1,2,5,10]))
0:(1:(0:((14`quot` 10) : coinChange' (14 `rem` 10) [1,2,5])))
0:(1:(0:( 1 : coinChange' (14 `rem` 10) [1,2,5])))
0:(1:(0:( 1 : coinChange' 4 [1,2,5])))
0:(1:(0:( 1 : ((4 `quot` 5):coinChange' (4`rem` 5) [1,2]))))
0:(1:(0:( 1 : (0:coinChange' 4 [1,2]))))
0:(1:(0:( 1 : (0:((4`quot`2):coinChange (4`rem`2) [1])))))
0:(1:(0:( 1 : (0:(2:coinChange 0 [1])))))
0:(1:(0:( 1 : (0:(2:((0`quot`1):coinChange' (0`rem` 1) []))))))
0:(1:(0:( 1 : (0:(2:(0:coinChange' 0 []))))))
0:(1:(0:( 1 : (0:(2:(0:[]))))))
reverse [0,1,0,1,0,2,0]
final output: [0,2,0,1,0,1,0]
但是，当我在终端中 运行 这段代码时，我得到：
coinChange 64 [1,2,5,10,20,50,100]
[0,0,0,0,0,64,0]
为什么我的方法不起作用？
然后我尝试了：
coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds = reverse( (c `quot` x): coinChange' (c `rem` x) xs )
where (x:xs) = reverse ds
coinChange' 0 ds = take (length ds) (repeat 0)
coinChange' c ds = (c `quot` x): coinChange' (c `rem` x) xs
where (x:xs) = reverse ds
我从已经可用的解决方案中提取了行 coinChange 0 ds = take (length ds) (repeat 0)。
然而，当我在终端中 运行 这段代码时，我得到了同样的错误：
coinChange 64 [1,2,5,10,20,50,100]
[0,0,0,0,0,64,0]
我认为主要问题在于 where (x:xs) = reverse ds。为什么这部分代码没有按照我预期的方式工作？
当我使用 let 而不是 where 时，我仍然遇到同样的错误。
coinChange 0 ds = take (length ds) (重复0)
coinChange c ds = let (x:xs) = 反转 ds
in reverse( (c quot x): coinChange' (c rem x) xs )
coinChange' 0 ds = take (length ds) (重复0)
coinChange' c ds = let (x:xs) = reverse ds
in (c quot x): coinChange' (c rem x) xs
我认为问题可能是我正在使用 (x:xs)。
所以，我尝试了：
coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds = let xs = reverse ds
in reverse( (c `quot` (head xs)): coinChange' (c `rem` (head xs)) (tail xs) )
coinChange' 0 ds = take (length ds) (repeat 0)
coinChange' c ds = let xs = reverse ds
in (c `quot` (head xs)): coinChange' (c `rem` (head xs)) (tail xs)
这仍然给出了同样的错误。
我尝试使用连接运算符 (++)，而不是前置运算符 :，看看是否有帮助：
coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds = let xs = reverse ds
in coinChange (c `rem` (head xs)) (tail xs) ++ [c `quot` (head xs)]
我在使用这段代码时仍然遇到同样的错误。
看来问题一定出在我反转硬币面额列表的方法上。
为什么我的所有尝试都失败了？当商数应该为 1 时，为什么 64 总是出现此错误？
在这个回答中，我将重点介绍您的尝试：
coinChange c [] = []
coinChange c ds =reverse( (c `quot` x):(coinChange' (c `rem` x) xs ))
where (x:xs) = (reverse ds)
coinChange' c [] = []
coinChange' c ds = (c`quot`x):(coinChange' (c `rem` x) xs )
where (x:xs) = reverse ds
我认为问题确实出在coinChange'函数中的where (x:xs) = reverse ds部分。每个递归调用都会反转面额列表。因此，您从 where 子句中的模式匹配得到的 xs 是没有最大面额的倒序面额列表。但是该列表仍然是相反的，因此您不应将其作为参数再次传递给 coinChange 或 coinChange' 函数。您可以在将其传递给递归调用之前再次反转此列表，但效率不高。我建议只反转 coinChange 函数中的面额。
另外，coinChange函数可以简化，因为它基本上只需要反转面额和结果列表。
这是它的样子：
coinChange c ds = reverse (coinChange' c (reverse ds))
coinChange' c [] = []
coinChange' c (x:xs) = (c `quot` x) : coinChange' (c `rem` x) xs