Find minimum number of coins that make a given value: Difference between revisions
Find minimum number of coins that make a given value (view source)
Revision as of 22:22, 11 August 2021
, 2 years ago→{{header|Haskell}}: Added a variant (hand-written recursion, rather than standard recursion scheme)
(→{{header|Python}}: Added a functionally composed variant.) |
(→{{header|Haskell}}: Added a variant (hand-written recursion, rather than standard recursion scheme)) |
||
Line 107:
(1,2)
(1,1)</pre>
Or as a hand-written recursion, defining a slightly more parsimonious listing:
<lang haskell>---------- MINIMUM NUMBER OF COINS TO MAKE A SUM ---------
change :: [Int] -> Int -> [(Int, Int)]
change [] n = []
change _ 0 = []
change (x : xs) n
| 0 == q = change xs n
| otherwise = (q, x) : change xs r
where
(q, r) = quotRem n x
--------------------------- TEST -------------------------
main :: IO ()
main = do
let f = change [200, 100, 50, 20, 10, 5, 2, 1]
mapM_ putStrLn $
fmap
( \n ->
concat $
"Summing to " <> show n <> ":\n" :
fmap
( \(q, v) ->
show q
<> " * "
<> show v
<> "\n"
)
(f n)
)
[1024, 988]</lang>
{{Out}}
<pre>Summing to 1024:
5 * 200
1 * 20
2 * 2
Summing to 988:
4 * 200
1 * 100
1 * 50
1 * 20
1 * 10
1 * 5
1 * 2
1 * 1
</pre>
=={{header|Julia}}==
|