Find minimum number of coins that make a given value: Difference between revisions
(Added XPL0 example.) |
|||
(35 intermediate revisions by 23 users not shown) | |||
Line 17: | Line 17: | ||
one coin of 1 |
one coin of 1 |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python_%3A%3A_Procedural}} |
|||
<syntaxhighlight lang="11l">V denominations = [1, 2, 5, 10, 20, 50, 100, 200] |
|||
V total = 988 |
|||
print(‘Available denominations: ’denominations‘. Total is to be: ’total‘.’) |
|||
V (coins, remaining) = (sorted(denominations, reverse' 1B), total) |
|||
L(n) 0 .< coins.len |
|||
(V coinsused, remaining) = divmod(remaining, coins[n]) |
|||
I coinsused > 0 |
|||
print(‘ ’coinsused‘ * ’coins[n])</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Available denominations: [1, 2, 5, 10, 20, 50, 100, 200]. Total is to be: 988. |
|||
4 * 200 |
|||
1 * 100 |
|||
1 * 50 |
|||
1 * 20 |
|||
1 * 10 |
|||
1 * 5 |
|||
1 * 2 |
|||
1 * 1 |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">PROC Main() |
|||
DEFINE LEN="8" |
|||
BYTE ARRAY coins=[200 100 50 20 10 5 2 1],count(LEN) |
|||
BYTE i |
|||
INT value=[988],curr,total |
|||
Zero(count,LEN) |
|||
i=0 total=0 |
|||
curr=value |
|||
WHILE curr>0 |
|||
DO |
|||
IF curr>=coins(i) THEN |
|||
count(i)==+1 |
|||
total==+1 |
|||
curr==-coins(i) |
|||
ELSE |
|||
i==+1 |
|||
FI |
|||
OD |
|||
PrintF("%I coins to make %I:%E",total,value) |
|||
FOR i=0 TO LEN-1 |
|||
DO |
|||
IF count(i) THEN |
|||
PrintF(" %B x %B%E",count(i),coins(i)) |
|||
FI |
|||
OD |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Find_minimum_number_of_coins_that_make_a_given_value.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
11 coins to make 988: |
|||
4 x 200 |
|||
1 x 100 |
|||
1 x 50 |
|||
1 x 20 |
|||
1 x 10 |
|||
1 x 5 |
|||
1 x 2 |
|||
1 x 1 |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
<syntaxhighlight lang="ada"> |
|||
pragma Ada_2022; |
|||
with Ada.Text_IO; use Ada.Text_IO; |
|||
procedure Find_Minimum_Coins is |
|||
COINS : constant array (1 .. 8) of Positive := [200, 100, 50, 20, 10, 5, 2, 1]; |
|||
CHANGE : constant Positive := 988; |
|||
Coins_Used : Natural := 0; |
|||
Owing : Natural := CHANGE; |
|||
Count : Natural; |
|||
begin |
|||
Put_Line ("The minimum number of coins needed to make a value of" & CHANGE'Image & " is..."); |
|||
for Coin of COINS loop |
|||
Count := Owing / Coin; |
|||
if Count /= 0 then |
|||
Coins_Used := @ + Count; |
|||
Put_Line (Count'Image & " x" & Coin'Image); |
|||
Owing := Owing mod Coin; |
|||
exit when Owing = 0; |
|||
end if; |
|||
end loop; |
|||
Put_Line ("A total of" & Coins_Used'Image & " coins."); |
|||
end Find_Minimum_Coins; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The minimum number of coins needed to make a value of 988 is... |
|||
4 x 200 |
|||
1 x 100 |
|||
1 x 50 |
|||
1 x 20 |
|||
1 x 10 |
|||
1 x 5 |
|||
1 x 2 |
|||
1 x 1 |
|||
A total of 11 coins. |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
{{Trans|Wren}} |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # find the minimum number of coins needed to make a given value # |
|||
# translated from the Wren sample # |
|||
[]INT denoms = ( 200, 100, 50, 20, 10, 5, 2, 1 ); |
|||
INT coins := 0; |
|||
INT amount = 988; |
|||
INT remaining := amount; |
|||
print( ( "The minimum number of coins needed to make a value of " ) ); |
|||
print( ( whole( amount, 0 ), " is as follows:", newline ) ); |
|||
FOR d pos FROM LWB denoms TO UPB denoms |
|||
WHILE INT denom = denoms[ d pos ]; |
|||
INT n = remaining OVER denom; |
|||
IF n > 0 THEN |
|||
coins +:= n; |
|||
print( (" ", whole( denom, -3 ), " x ", whole( n, 0 ), newline ) ); |
|||
remaining MODAB denom |
|||
FI; |
|||
remaining > 0 |
|||
DO SKIP OD; |
|||
print( ( newline, "A total of ", whole( coins, 0 ), " coins in all.", newline ) ) |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The minimum number of coins needed to make a value of 988 is as follows: |
|||
200 x 4 |
|||
100 x 1 |
|||
50 x 1 |
|||
20 x 1 |
|||
10 x 1 |
|||
5 x 1 |
|||
2 x 1 |
|||
1 x 1 |
|||
A total of 11 coins in all. |
|||
</pre> |
|||
=={{header|APL}}== |
|||
{{works with|Dyalog APL}} |
|||
<syntaxhighlight lang="apl">coins←{ |
|||
{⍺,≢⍵}⌸⍺[⍒⍺]{ |
|||
coin←⊃(⍵≥⍺)/⍺ |
|||
coin=0:⍬ |
|||
coin,⍺∇⍵-coin |
|||
}⍵ |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> (1 2 5 10 20 50 100 200) coins 988 |
|||
200 4 |
|||
100 1 |
|||
50 1 |
|||
20 1 |
|||
10 1 |
|||
5 1 |
|||
2 1 |
|||
1 1</pre> |
|||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
< |
<syntaxhighlight lang="applescript">----------------- MINIMUM NUMBER OF COINS ---------------- |
||
-- change :: [Int] -> Int -> [(Int, Int)] |
-- change :: [Int] -> Int -> [(Int, Int)] |
||
Line 102: | Line 268: | ||
set my text item delimiters to dlm |
set my text item delimiters to dlm |
||
s |
s |
||
end unlines</ |
end unlines</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Summing to 1024: |
<pre>Summing to 1024: |
||
Line 118: | Line 284: | ||
1 * 2 |
1 * 2 |
||
1 * 1</pre> |
1 * 1</pre> |
||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="arturo">coins: [200 100 50 20 10 5 2 1] |
|||
target: 988 |
|||
print ["Minimum number of coins to make a value of " (to :string target)++":"] |
|||
cnt: 0 |
|||
remaining: new target |
|||
loop coins 'coin [ |
|||
n: remaining / coin |
|||
if not? zero? n [ |
|||
cnt: cnt + n |
|||
print [" coins of" coin "->" n] |
|||
remaining: remaining - n * coin |
|||
if zero? remaining -> break |
|||
] |
|||
] |
|||
print ["\nTotal: " cnt]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Minimum number of coins to make a value of 988: |
|||
coins of 200 -> 4 |
|||
coins of 100 -> 1 |
|||
coins of 50 -> 1 |
|||
coins of 20 -> 1 |
|||
coins of 10 -> 1 |
|||
coins of 5 -> 1 |
|||
coins of 2 -> 1 |
|||
coins of 1 -> 1 |
|||
Total: 11</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<syntaxhighlight lang="autohotkey">coins := [1, 2, 5, 10, 20, 50, 100, 200] |
|||
val := 988 |
|||
result := "" |
|||
while val |
|||
{ |
|||
coin := coins.pop() |
|||
if (val//coin) |
|||
result .= val//coin " * " coin "`n", val -= val//coin * coin |
|||
} |
|||
MsgBox, 262144, , % result |
|||
return</syntaxhighlight> |
|||
{{out}} |
|||
<pre>4 * 200 |
|||
1 * 100 |
|||
1 * 50 |
|||
1 * 20 |
|||
1 * 10 |
|||
1 * 5 |
|||
1 * 2 |
|||
1 * 1</pre> |
|||
=={{header|AWK}}== |
|||
<syntaxhighlight lang="awk"> |
|||
# syntax: GAWK -f FIND_MINIMUM_NUMBER_OF_COINS_THAT_MAKE_A_GIVEN_VALUE.AWK |
|||
BEGIN { |
|||
n = split("200,100,50,20,10,5,2,1",arr,",") |
|||
main(988) |
|||
main(388) |
|||
main(0) |
|||
exit(0) |
|||
} |
|||
function main(arg1, amount,coins,denomination,i,remaining,total) { |
|||
amount = remaining = int(arg1) |
|||
for (i=1; i<=n; i++) { |
|||
denomination = arr[i] |
|||
coins = 0 |
|||
while (remaining >= denomination) { |
|||
remaining -= denomination |
|||
coins++ |
|||
} |
|||
total += coins |
|||
printf("%4d x %2d = %d\n",denomination,coins,denomination*coins) |
|||
} |
|||
printf("%9d coins needed to disperse %s\n\n",total,arg1) |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
200 x 4 = 800 |
|||
100 x 1 = 100 |
|||
50 x 1 = 50 |
|||
20 x 1 = 20 |
|||
10 x 1 = 10 |
|||
5 x 1 = 5 |
|||
2 x 1 = 2 |
|||
1 x 1 = 1 |
|||
11 coins needed to disperse 988 |
|||
200 x 1 = 200 |
|||
100 x 1 = 100 |
|||
50 x 1 = 50 |
|||
20 x 1 = 20 |
|||
10 x 1 = 10 |
|||
5 x 1 = 5 |
|||
2 x 1 = 2 |
|||
1 x 1 = 1 |
|||
8 coins needed to disperse 388 |
|||
200 x 0 = 0 |
|||
100 x 0 = 0 |
|||
50 x 0 = 0 |
|||
20 x 0 = 0 |
|||
10 x 0 = 0 |
|||
5 x 0 = 0 |
|||
2 x 0 = 0 |
|||
1 x 0 = 0 |
|||
0 coins needed to disperse 0 |
|||
</pre> |
|||
=={{header|BASIC256}}== |
|||
<syntaxhighlight lang="basic256">amount = 988 |
|||
sumCoins = 0 |
|||
dim coins = {1, 2, 5, 10, 20, 50, 100, 200} |
|||
print "Make a value of "; amount; " using the coins 1, 2, 5, 10, 20, 50, 100 and 200:" |
|||
for n = coins[?]-1 to 0 step -1 |
|||
tmp = floor(amount/coins[n]) |
|||
if tmp >= 0 then |
|||
print tmp; " * "; coins[n] |
|||
sumCoins = sumCoins + tmp |
|||
amount = amount % coins[n] |
|||
end if |
|||
next n |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Igual que la entrada de FreeBASIC. |
|||
</pre> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="c"> |
|||
#include <stdio.h> |
|||
#define TOTAL 988 |
|||
#define Q_VALUES 8 |
|||
int main() { |
|||
const int kValues[Q_VALUES] = { 200, 100, 50, 20, 10, 5, 2, 1 }; |
|||
int t, q, iv; |
|||
for( t=TOTAL, iv=0; iv<Q_VALUES; t%=kValues[iv], ++iv ) { |
|||
q = t/kValues[iv]; |
|||
printf( "%4d coin%c of %4d\n", q, q!=1?'s':' ', kValues[iv] ); |
|||
} |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
4 coins of 200 |
|||
1 coin of 100 |
|||
1 coin of 50 |
|||
1 coin of 20 |
|||
1 coin of 10 |
|||
1 coin of 5 |
|||
1 coin of 2 |
|||
1 coin of 1 |
|||
</pre> |
|||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
const Coins: array [0..7] of integer = (1,2,5,10,20,50,100,200); |
|||
procedure MinimumCoins(Memo: TMemo; Value: integer); |
|||
var I,C: integer; |
|||
begin |
|||
Memo.Lines.Add('Providing Change for: '+IntToStr(Value)); |
|||
for I:=High(Coins) downto 0 do |
|||
begin |
|||
C:=Value div Coins[I]; |
|||
Value:=Value mod Coins[I]; |
|||
Memo.Lines.Add(IntToStr(C)+' coins of '+IntToStr(Coins[I])); |
|||
end; |
|||
Memo.Lines.Add(''); |
|||
end; |
|||
procedure TestMinimumCoins(Memo: TMemo); |
|||
begin |
|||
MinimumCoins(Memo,988); |
|||
MinimumCoins(Memo,1307); |
|||
MinimumCoins(Memo,37511); |
|||
MinimumCoins(Memo,0); |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Providing Change for: 988 |
|||
4 coins of 200 |
|||
1 coins of 100 |
|||
1 coins of 50 |
|||
1 coins of 20 |
|||
1 coins of 10 |
|||
1 coins of 5 |
|||
1 coins of 2 |
|||
1 coins of 1 |
|||
Providing Change for: 1307 |
|||
6 coins of 200 |
|||
1 coins of 100 |
|||
0 coins of 50 |
|||
0 coins of 20 |
|||
0 coins of 10 |
|||
1 coins of 5 |
|||
1 coins of 2 |
|||
0 coins of 1 |
|||
Providing Change for: 37511 |
|||
187 coins of 200 |
|||
1 coins of 100 |
|||
0 coins of 50 |
|||
0 coins of 20 |
|||
1 coins of 10 |
|||
0 coins of 5 |
|||
0 coins of 2 |
|||
1 coins of 1 |
|||
Providing Change for: 0 |
|||
0 coins of 200 |
|||
0 coins of 100 |
|||
0 coins of 50 |
|||
0 coins of 20 |
|||
0 coins of 10 |
|||
0 coins of 5 |
|||
0 coins of 2 |
|||
0 coins of 1 |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
sum = 988 |
|||
coins[] = [ 200 100 50 20 10 5 2 1 ] |
|||
# |
|||
for coin in coins[] |
|||
n = sum div coin |
|||
if n > 0 |
|||
print "coins of " & coin & ": " & n |
|||
sum -= n * coin |
|||
. |
|||
. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
coins of 200: 4 |
|||
coins of 100: 1 |
|||
coins of 50: 1 |
|||
coins of 20: 1 |
|||
coins of 10: 1 |
|||
coins of 5: 1 |
|||
coins of 2: 1 |
|||
coins of 1: 1 |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
//Find minimum number of coins that make a given value - Nigel Galloway: August 12th., 20 |
//Find minimum number of coins that make a given value - Nigel Galloway: August 12th., 20 |
||
let fN g=let rec fG n g=function h::t->fG((g/h,h)::n)(g%h) t |_->n in fG [] g [200;100;50;20;10;5;2;1] |
let fN g=let rec fG n g=function h::t->fG((g/h,h)::n)(g%h) t |_->n in fG [] g [200;100;50;20;10;5;2;1] |
||
fN 988|>List.iter(fun(n,g)->printfn "Take %d of %d" n g) |
fN 988|>List.iter(fun(n,g)->printfn "Take %d of %d" n g) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 139: | Line 579: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2021-06-02}} |
{{works with|Factor|0.99 2021-06-02}} |
||
< |
<syntaxhighlight lang="factor">USING: assocs kernel math math.order prettyprint sorting ; |
||
: make-change ( value coins -- assoc ) |
: make-change ( value coins -- assoc ) |
||
[ >=< ] sort [ /mod swap ] zip-with nip ; |
[ >=< ] sort [ /mod swap ] zip-with nip ; |
||
988 { 1 2 5 10 20 50 100 200 } make-change .</ |
988 { 1 2 5 10 20 50 100 200 } make-change .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 157: | Line 597: | ||
{ 1 1 } |
{ 1 1 } |
||
} |
} |
||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">#define floor(x) ((x*2.0-0.5) Shr 1) |
|||
Dim As Integer amount = 988 |
|||
Dim As Integer sumCoins = 0 |
|||
Dim As Integer n, tmp |
|||
Dim As Integer coins(8) = {1, 2, 5, 10, 20, 50, 100, 200} |
|||
Print "Make a value of"; amount; " using the coins 1, 2, 5, 10, 20, 50, 100 and 200:" |
|||
For n As Integer = Ubound(coins) To 0 Step -1 |
|||
tmp = floor(amount/coins(n)) |
|||
If tmp >= 0 Then |
|||
Print tmp; " *"; coins(n) |
|||
sumCoins += tmp |
|||
amount Mod= coins(n) |
|||
End If |
|||
Next n |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Make a value of 988 using the coins 1, 2, 5, 10, 20, 50, 100 and 200: |
|||
4 * 200 |
|||
1 * 100 |
|||
1 * 50 |
|||
1 * 20 |
|||
1 * 10 |
|||
1 * 5 |
|||
1 * 2 |
|||
1 * 1</pre> |
|||
=={{header|FutureBasic}}== |
|||
Task solution wrapped into a general purpose function with test examples shown. |
|||
<syntaxhighlight lang="futurebasic"> |
|||
void local fn MinimumCoinsForValue( value as NSUInteger, coins as CFArrayRef ) |
|||
NSUInteger i, count, tmp |
|||
CFStringRef coinStr = fn ArrayComponentsJoinedByString( coins, @", " ) |
|||
printf @"The minimum number of coins valued %@ needed to total %lu is:", coinStr, value |
|||
count = len(coins) |
|||
for i = count to 1 step -1 |
|||
tmp = (NSUInteger)fn floor( value / fn NumberIntegerValue( coins[i-1] ) ) |
|||
if ( tmp > 0 ) |
|||
printf @"%lu * %@", tmp, coins[i-1] |
|||
value = value mod fn NumberIntegerValue( coins[i-1] ) |
|||
end if |
|||
next |
|||
end fn |
|||
fn MinimumCoinsForValue( 988, @[@1, @2, @5, @10, @20, @50, @100, @200] ) |
|||
print : print |
|||
fn MinimumCoinsForValue( 1024, @[@1, @2, @5, @10, @20, @50, @100, @200] ) |
|||
print : print |
|||
print "Currency in this example represents U.S. denominations:" |
|||
print " 1 cent, 5 cents, 10 cents, 25 cents, 50 cents, $1, $5, $10, $20, $50" |
|||
fn MinimumCoinsForValue( 65273, @[@1, @5, @10, @25, @50, @100, @500, @1000, @2000, @5000] ) |
|||
HandleEvents |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
The minimum number of coins valued 1, 2, 5, 10, 20, 50, 100, 200 needed to total 988 is: |
|||
4 * 200 |
|||
1 * 100 |
|||
1 * 50 |
|||
1 * 20 |
|||
1 * 10 |
|||
1 * 5 |
|||
1 * 2 |
|||
1 * 1 |
|||
The minimum number of coins valued 1, 2, 5, 10, 20, 50, 100, 200 needed to total 1024 is: |
|||
5 * 200 |
|||
1 * 20 |
|||
2 * 2 |
|||
Currency in this example represents U.S. denominations: |
|||
1 cent, 5 cents, 10 cents, 25 cents, 50 cents, $1, $5, $10, $20, $50 |
|||
The minimum number of coins valued 1, 5, 10, 25, 50, 100, 500, 1000, 2000, 5000 needed to total 65273 is: |
|||
13 * 5000 |
|||
2 * 100 |
|||
1 * 50 |
|||
2 * 10 |
|||
3 * 1 |
|||
</pre> |
</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 183: | Line 713: | ||
} |
} |
||
fmt.Println("\nA total of", coins, "coins in all.") |
fmt.Println("\nA total of", coins, "coins in all.") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 201: | Line 731: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.List (mapAccumL) |
||
import Data.Tuple (swap) |
import Data.Tuple (swap) |
||
Line 216: | Line 746: | ||
main = |
main = |
||
mapM_ print $ |
mapM_ print $ |
||
change [200, 100, 50, 20, 10, 5, 2, 1] 988</ |
change [200, 100, 50, 20, 10, 5, 2, 1] 988</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>(4,200) |
<pre>(4,200) |
||
Line 229: | Line 759: | ||
Or as a hand-written recursion, defining a slightly more parsimonious listing, and allowing for denomination lists which are ill-sorted or incomplete. |
Or as a hand-written recursion, defining a slightly more parsimonious listing, and allowing for denomination lists which are ill-sorted or incomplete. |
||
< |
<syntaxhighlight lang="haskell">import Data.List (sortOn) |
||
import Data.Ord (Down (Down)) |
import Data.Ord (Down (Down)) |
||
Line 271: | Line 801: | ||
) |
) |
||
) |
) |
||
(change [200, 100, 50, 20, 10, 5, 2, 1] n)</ |
(change [200, 100, 50, 20, 10, 5, 2, 1] n)</syntaxhighlight> |
||
{{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|J}}== |
|||
<syntaxhighlight lang="j">coins=. [ (,: {."1@}:) [: (#: {:)/\. 0 ,. , |
|||
1 2 5 10 20 50 100 200 coins 988</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1 2 5 10 20 50 100 200 |
|||
1 1 1 1 1 1 1 4</pre> |
|||
=={{header|JavaScript}}== |
|||
{{Works with|JavaScript|ES6}} |
|||
<syntaxhighlight lang="javascript">(() => { |
|||
"use strict"; |
|||
// -- MINIMUM NUMBER OF COINS TO MAKE A GIVEN VALUE -- |
|||
// change :: [Int] -> Int -> [(Int, Int)] |
|||
const change = denominations => { |
|||
// A minimum list of (quantity, value) pairs for n. |
|||
// Unused denominations are excluded from the list. |
|||
const go = n => { |
|||
const m = abs(n); |
|||
return 0 < denominations.length && 0 < m ? ( |
|||
() => { |
|||
const [h, ...t] = denominations; |
|||
const q = Math.trunc(m / h); |
|||
return ( |
|||
0 < q ? [ |
|||
[q, h] |
|||
] : [] |
|||
).concat(change(t)(m % h)); |
|||
} |
|||
)() : []; |
|||
}; |
|||
return go; |
|||
}; |
|||
// ---------------------- TEST ----------------------- |
|||
// main :: IO () |
|||
const main = () => { |
|||
// Two sums tested with a set of denominations. |
|||
const f = change([200, 100, 50, 20, 10, 5, 2, 1]); |
|||
return [1024, 988].reduce((acc, n) => { |
|||
const |
|||
report = f(n).reduce( |
|||
(a, [q, u]) => `${a}${q} * ${u}\n`, |
|||
"" |
|||
); |
|||
return `${acc}Summing to ${abs(n)}:\n` + ( |
|||
`${report}\n` |
|||
); |
|||
}, |
|||
"" |
|||
); |
|||
}; |
|||
// --------------------- GENERIC --------------------- |
|||
// abs :: Num -> Num |
|||
const abs = |
|||
// Absolute value - without the sign. |
|||
x => 0 > x ? ( |
|||
-x |
|||
) : x; |
|||
// MAIN --- |
|||
return main(); |
|||
})();</syntaxhighlight> |
|||
{{Out}} |
{{Out}} |
||
<pre>Summing to 1024: |
<pre>Summing to 1024: |
||
Line 291: | Line 912: | ||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq''' |
'''Works with gojq, the Go implementation of jq''' |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
# If $details then provide {details, coins}, otherwise just the number of coins. |
# If $details then provide {details, coins}, otherwise just the number of coins. |
||
def minimum_number($details): |
def minimum_number($details): |
||
Line 319: | Line 940: | ||
| minimum_number(false), # illustrate minimal output |
| minimum_number(false), # illustrate minimal output |
||
task # illustrate detailed output |
task # illustrate detailed output |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 336: | Line 957: | ||
A total of 11 coins in all.</pre> |
A total of 11 coins in all.</pre> |
||
</pre> |
</pre> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
=== Long version === |
=== Long version === |
||
Using a linear optimizer for this is serious overkill, but why not? |
Using a linear optimizer for this is serious overkill, but why not? |
||
< |
<syntaxhighlight lang="julia">using JuMP, GLPK |
||
model = Model(GLPK.Optimizer) |
model = Model(GLPK.Optimizer) |
||
Line 367: | Line 989: | ||
println("Value of ", string(val), " is ", value(val)) |
println("Value of ", string(val), " is ", value(val)) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Optimized total coins: 11.0 |
Optimized total coins: 11.0 |
||
Line 392: | Line 1,014: | ||
(0, (1, 1)) |
(0, (1, 1)) |
||
</pre> |
</pre> |
||
=={{header|Lua}}== |
|||
{{Trans|Wren}} |
|||
<syntaxhighlight lang="lua"> |
|||
do -- find the minimum number of coins needed to make a given value |
|||
-- translated from the Wren sample |
|||
local denoms = { 200, 100, 50, 20, 10, 5, 2, 1 } |
|||
local amount = 988; |
|||
local coins, remaining = 0, amount |
|||
print( "The minimum number of coins needed to make a value of "..amount.." is as follows:" ) |
|||
for _, denom in pairs( denoms ) do |
|||
local n = math.floor( remaining / denom ) |
|||
if n > 0 then |
|||
coins = coins + n |
|||
print( string.format( "%6d", denom ).." x "..n ) |
|||
remaining = remaining % denom |
|||
end |
|||
if remaining == 0 then break end |
|||
end |
|||
print( "A total of "..coins.." coins in all." ) |
|||
end |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The minimum number of coins needed to make a value of 988 is as follows: |
|||
200 x 4 |
|||
100 x 1 |
|||
50 x 1 |
|||
20 x 1 |
|||
10 x 1 |
|||
5 x 1 |
|||
2 x 1 |
|||
1 x 1 |
|||
A total of 11 coins in all. |
|||
</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">coins = {1, 2, 5, 10, 20, 50, 100, 200}; |
|||
out = v /. ConvexOptimization[Total[v], coins . v == 988, v \[Element] Vectors[8, NonNegativeIntegers]]; |
|||
MapThread[Row[{#1, " x ", #2}] &, {out, coins}] // Column</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1 x 1 |
|||
1 x 2 |
|||
1 x 5 |
|||
1 x 10 |
|||
1 x 20 |
|||
1 x 50 |
|||
1 x 100 |
|||
4 x 200</pre> |
|||
=={{header|MiniZinc}}== |
=={{header|MiniZinc}}== |
||
<syntaxhighlight lang="minizinc"> |
|||
<lang MiniZinc> |
|||
%Find minimum number of coins that make a given value. Nigel Galloway, August 11th., 2021 |
%Find minimum number of coins that make a given value. Nigel Galloway, August 11th., 2021 |
||
int: N=988; |
int: N=988; |
||
Line 401: | Line 1,073: | ||
solve minimize sum(n in 1..8)(take[n]); |
solve minimize sum(n in 1..8)(take[n]); |
||
output(["Take "++show(take[n])++" of "++show(coinValue[n])++"\n" | n in 1..8]) |
output(["Take "++show(take[n])++" of "++show(coinValue[n])++"\n" | n in 1..8]) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 416: | Line 1,088: | ||
Finished in 196msec |
Finished in 196msec |
||
</pre> |
</pre> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import strformat |
||
const |
const |
||
Line 434: | Line 1,107: | ||
if remaining == 0: break |
if remaining == 0: break |
||
echo "\nTotal: ", count</ |
echo "\nTotal: ", count</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 448: | Line 1,121: | ||
Total: 11</pre> |
Total: 11</pre> |
||
=={{header|Perl}}== |
|||
<syntaxhighlight lang="perl">use strict; |
|||
use warnings; |
|||
my @denominations = <200 100 50 20 10 5 2 1>; |
|||
sub change { |
|||
my $n = shift; |
|||
my @a; |
|||
push(@a, int $n/$_) and $n %= $_ for @denominations; |
|||
@a |
|||
} |
|||
my @amounts = change 988; |
|||
for (0 .. $#amounts) { |
|||
printf "%1d * %3d\n", $amounts[$_], $denominations[$_] |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>4 * 200 |
|||
1 * 100 |
|||
1 * 50 |
|||
1 * 20 |
|||
1 * 10 |
|||
1 * 5 |
|||
1 * 2 |
|||
1 * 1</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.1"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (lastdelim added to the join() function)</span> |
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.1"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (lastdelim added to the join() function)</span> |
||
Line 469: | Line 1,169: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s coins were used.\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">proper</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">ordinal</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">))})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s coins were used.\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">proper</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">ordinal</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">))})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 486: | Line 1,186: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Python :: Procedural=== |
===Python :: Procedural=== |
||
< |
<syntaxhighlight lang="python">def makechange(denominations = [1,2,5,10,20,50,100,200], total = 988): |
||
print(f"Available denominations: {denominations}. Total is to be: {total}.") |
print(f"Available denominations: {denominations}. Total is to be: {total}.") |
||
coins, remaining = sorted(denominations, reverse=True), total |
coins, remaining = sorted(denominations, reverse=True), total |
||
Line 495: | Line 1,195: | ||
makechange() |
makechange() |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Available denominations: [1, 2, 5, 10, 20, 50, 100, 200]. Total is to be: 988. |
Available denominations: [1, 2, 5, 10, 20, 50, 100, 200]. Total is to be: 988. |
||
Line 509: | Line 1,209: | ||
===Python :: Functional=== |
===Python :: Functional=== |
||
< |
<syntaxhighlight lang="python">'''Minimum number of coins to make a given value''' |
||
Line 549: | Line 1,249: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Summing to 1024: |
<pre>Summing to 1024: |
||
Line 565: | Line 1,265: | ||
1 * 2 |
1 * 2 |
||
1 * 1</pre> |
1 * 1</pre> |
||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="Quackery"> [ ' [ 200 100 50 20 10 5 2 1 ] ] is coins ( --> [ ) |
|||
[ [] swap |
|||
coins witheach |
|||
[ /mod dip join ] |
|||
drop |
|||
witheach |
|||
[ dup 0 > iff |
|||
[ echo say " * " |
|||
coins i^ peek echo |
|||
cr ] |
|||
else drop ] ] is task ( n --> ) |
|||
' [ 988 345 1024 ] |
|||
witheach |
|||
[ say "To make " |
|||
dup echo say ":" cr |
|||
task cr ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>To make 988: |
|||
4 * 200 |
|||
1 * 100 |
|||
1 * 50 |
|||
1 * 20 |
|||
1 * 10 |
|||
1 * 5 |
|||
1 * 2 |
|||
1 * 1 |
|||
To make 345: |
|||
1 * 200 |
|||
1 * 100 |
|||
2 * 20 |
|||
1 * 5 |
|||
To make 1024: |
|||
5 * 200 |
|||
1 * 20 |
|||
2 * 2 |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Since unit denominations are possible, don't bother to check to see if an exact pay-out isn't possible. |
Since unit denominations are possible, don't bother to check to see if an exact pay-out isn't possible. |
||
<lang |
<syntaxhighlight lang="raku" line>my @denominations = 200, 100, 50, 20, 10, 5, 2, 1; |
||
sub change (Int $n is copy where * >= 0) { gather for @denominations { take $n div $_; $n %= $_ } } |
sub change (Int $n is copy where * >= 0) { gather for @denominations { take $n div $_; $n %= $_ } } |
||
Line 576: | Line 1,321: | ||
say "\n$amount:"; |
say "\n$amount:"; |
||
printf "%d × %d\n", |$_ for $amount.&change Z @denominations; |
printf "%d × %d\n", |$_ for $amount.&change Z @denominations; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>988: |
<pre>988: |
||
Line 617: | Line 1,362: | ||
0 × 2 |
0 × 2 |
||
0 × 1</pre> |
0 × 1</pre> |
||
=={{header|Red}}== |
|||
<syntaxhighlight lang="rebol">Red[] |
|||
value: 988 |
|||
foreach denomination [200 100 50 20 10 5 2 1][ |
|||
quantity: to-integer value / denomination |
|||
unless 0 = quantity [print [quantity "*" denomination]] |
|||
value: value % denomination |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
4 * 200 |
|||
1 * 100 |
|||
1 * 50 |
|||
1 * 20 |
|||
1 * 10 |
|||
1 * 5 |
|||
1 * 2 |
|||
1 * 1 |
|||
</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Line 622: | Line 1,388: | ||
The total number of coins paid out is also shown. |
The total number of coins paid out is also shown. |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm finds & displays the minimum number of coins which total to a specified value*/ |
||
parse arg $ coins /*obtain optional arguments from the CL*/ |
parse arg $ coins /*obtain optional arguments from the CL*/ |
||
if $='' | $="," then $= 988 /*Not specified? Then use the default.*/ |
if $='' | $="," then $= 988 /*Not specified? Then use the default.*/ |
||
Line 649: | Line 1,415: | ||
say 'number of coins dispensed: ' koins |
say 'number of coins dispensed: ' koins |
||
if $>0 then say 'exact payout not possible.' /*There a residue? Payout not possible*/ |
if $>0 then say 'exact payout not possible.' /*There a residue? Payout not possible*/ |
||
exit 0 /*stick a fork in it, we're all done. */</ |
exit 0 /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 670: | Line 1,436: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
Line 691: | Line 1,457: | ||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 705: | Line 1,471: | ||
1*1 |
1*1 |
||
done... |
done... |
||
</pre> |
|||
=={{header|RPL}}== |
|||
{{works with|HP|48G}} |
|||
« { 200 100 50 20 10 5 2 1 } { } |
|||
→ coinset result |
|||
« 1 coinset SIZE '''FOR''' j |
|||
coinset j GET |
|||
MOD LASTARG / IP |
|||
'result' SWAP STO+ |
|||
'''NEXT''' |
|||
DROP result DUP ∑LIST "coins" →TAG |
|||
» » '<span style="color:blue">COINS</span>' STO |
|||
988 <span style="color:blue">COINS</span> |
|||
{{out}} |
|||
<pre> |
|||
2: { 4 1 1 1 1 1 1 1 } |
|||
1: coins: 11 |
|||
</pre> |
|||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust"> |
|||
fn main() { |
|||
let denoms = vec![200, 100, 50, 20, 10, 5, 2, 1]; |
|||
let mut coins = 0; |
|||
let amount = 988; |
|||
let mut remaining = 988; |
|||
println!("The minimum number of coins needed to make a value of {} is as follows:", amount); |
|||
for denom in denoms.iter() { |
|||
let n = remaining / denom; |
|||
if n > 0 { |
|||
coins += n; |
|||
println!(" {} x {}", denom, n); |
|||
remaining %= denom; |
|||
if remaining == 0 { |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
println!("\nA total of {} coins in all.", coins); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The minimum number of coins needed to make a value of 988 is as follows: |
|||
200 x 4 |
|||
100 x 1 |
|||
50 x 1 |
|||
20 x 1 |
|||
10 x 1 |
|||
5 x 1 |
|||
2 x 1 |
|||
1 x 1 |
|||
A total of 11 coins in all. |
|||
</pre> |
|||
=={{header|V (Vlang)}}== |
|||
<syntaxhighlight lang="Rust"> |
|||
fn main() { |
|||
denoms := [200, 100, 50, 20, 10, 5, 2, 1] |
|||
amount := 988 |
|||
mut coins := 0 |
|||
mut remaining := 988 |
|||
mut n := 0 |
|||
println("The minimum number of coins needed to make a value of ${amount} is as follows:") |
|||
for denom in denoms { |
|||
n = remaining / denom |
|||
if n > 0 { |
|||
coins += n |
|||
print(" ${denom} x ${n}" + "\n") |
|||
remaining %= denom |
|||
if remaining == 0 {break} |
|||
} |
|||
} |
|||
println("\nA total of ${coins} coins in all.") |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The minimum number of coins needed to make a value of 988 is as follows: |
|||
200 x 4 |
|||
100 x 1 |
|||
50 x 1 |
|||
20 x 1 |
|||
10 x 1 |
|||
5 x 1 |
|||
2 x 1 |
|||
1 x 1 |
|||
A total of 11 coins in all. |
|||
</pre> |
</pre> |
||
Line 710: | Line 1,570: | ||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
As there is, apparently, an unlimited supply of coins of each denomination, it follows that any amount can be made up. |
As there is, apparently, an unlimited supply of coins of each denomination, it follows that any amount can be made up. |
||
< |
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
||
var denoms = [200, 100, 50, 20, 10, 5, 2, 1] |
var denoms = [200, 100, 50, 20, 10, 5, 2, 1] |
||
Line 726: | Line 1,586: | ||
} |
} |
||
} |
} |
||
System.print("\nA total of %(coins) coins in all.")</ |
System.print("\nA total of %(coins) coins in all.")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 745: | Line 1,605: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="xpl0">int Denom, Denoms, Coins, Amount, Remaining, I, N; |
||
[Denoms:= [200, 100, 50, 20, 10, 5, 2, 1]; |
[Denoms:= [200, 100, 50, 20, 10, 5, 2, 1]; |
||
Coins:= 0; |
Coins:= 0; |
||
Line 767: | Line 1,627: | ||
A total of "); IntOut(0, Coins); Text(0, " coins in all. |
A total of "); IntOut(0, Coins); Text(0, " coins in all. |
||
"); |
"); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 782: | Line 1,642: | ||
A total of 11 coins in all. |
A total of 11 coins in all. |
||
</pre> |
|||
=={{header|Yabasic}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="yabasic">amount = 988 |
|||
sumCoins = 0 |
|||
dim coins(7) |
|||
coins(0) = 1 |
|||
coins(1) = 2 |
|||
coins(2) = 5 |
|||
coins(3) = 10 |
|||
coins(4) = 20 |
|||
coins(5) = 50 |
|||
coins(6) = 100 |
|||
coins(7) = 200 |
|||
print "Make a value of ", amount, " using the coins 1, 2, 5, 10, 20, 50, 100 and 200:" |
|||
for n = arraysize(coins(),1) to 0 step -1 |
|||
tmp = floor(amount/coins(n)) |
|||
if tmp >= 0 then |
|||
print tmp, " * ", coins(n) |
|||
sumCoins = sumCoins + tmp |
|||
amount = mod(amount, coins(n)) |
|||
end if |
|||
next n |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Igual que la entrada de FreeBASIC. |
|||
</pre> |
</pre> |
Latest revision as of 09:49, 17 June 2024
- Task
Find and show here on this page the minimum number of coins that can make a value of 988.
Available coins are: 1, 2, 5, 10, 20, 50, 100, and 200.
The coins that would be dispensed are:
four coins of 200 one coin of 100 one coin of 50 one coin of 20 one coin of 10 one coin of 5 one coin of 2 one coin of 1
11l
V denominations = [1, 2, 5, 10, 20, 50, 100, 200]
V total = 988
print(‘Available denominations: ’denominations‘. Total is to be: ’total‘.’)
V (coins, remaining) = (sorted(denominations, reverse' 1B), total)
L(n) 0 .< coins.len
(V coinsused, remaining) = divmod(remaining, coins[n])
I coinsused > 0
print(‘ ’coinsused‘ * ’coins[n])
- Output:
Available denominations: [1, 2, 5, 10, 20, 50, 100, 200]. Total is to be: 988. 4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1
Action!
PROC Main()
DEFINE LEN="8"
BYTE ARRAY coins=[200 100 50 20 10 5 2 1],count(LEN)
BYTE i
INT value=[988],curr,total
Zero(count,LEN)
i=0 total=0
curr=value
WHILE curr>0
DO
IF curr>=coins(i) THEN
count(i)==+1
total==+1
curr==-coins(i)
ELSE
i==+1
FI
OD
PrintF("%I coins to make %I:%E",total,value)
FOR i=0 TO LEN-1
DO
IF count(i) THEN
PrintF(" %B x %B%E",count(i),coins(i))
FI
OD
RETURN
- Output:
Screenshot from Atari 8-bit computer
11 coins to make 988: 4 x 200 1 x 100 1 x 50 1 x 20 1 x 10 1 x 5 1 x 2 1 x 1
Ada
pragma Ada_2022;
with Ada.Text_IO; use Ada.Text_IO;
procedure Find_Minimum_Coins is
COINS : constant array (1 .. 8) of Positive := [200, 100, 50, 20, 10, 5, 2, 1];
CHANGE : constant Positive := 988;
Coins_Used : Natural := 0;
Owing : Natural := CHANGE;
Count : Natural;
begin
Put_Line ("The minimum number of coins needed to make a value of" & CHANGE'Image & " is...");
for Coin of COINS loop
Count := Owing / Coin;
if Count /= 0 then
Coins_Used := @ + Count;
Put_Line (Count'Image & " x" & Coin'Image);
Owing := Owing mod Coin;
exit when Owing = 0;
end if;
end loop;
Put_Line ("A total of" & Coins_Used'Image & " coins.");
end Find_Minimum_Coins;
- Output:
The minimum number of coins needed to make a value of 988 is... 4 x 200 1 x 100 1 x 50 1 x 20 1 x 10 1 x 5 1 x 2 1 x 1 A total of 11 coins.
ALGOL 68
BEGIN # find the minimum number of coins needed to make a given value #
# translated from the Wren sample #
[]INT denoms = ( 200, 100, 50, 20, 10, 5, 2, 1 );
INT coins := 0;
INT amount = 988;
INT remaining := amount;
print( ( "The minimum number of coins needed to make a value of " ) );
print( ( whole( amount, 0 ), " is as follows:", newline ) );
FOR d pos FROM LWB denoms TO UPB denoms
WHILE INT denom = denoms[ d pos ];
INT n = remaining OVER denom;
IF n > 0 THEN
coins +:= n;
print( (" ", whole( denom, -3 ), " x ", whole( n, 0 ), newline ) );
remaining MODAB denom
FI;
remaining > 0
DO SKIP OD;
print( ( newline, "A total of ", whole( coins, 0 ), " coins in all.", newline ) )
END
- Output:
The minimum number of coins needed to make a value of 988 is as follows: 200 x 4 100 x 1 50 x 1 20 x 1 10 x 1 5 x 1 2 x 1 1 x 1 A total of 11 coins in all.
APL
coins←{
{⍺,≢⍵}⌸⍺[⍒⍺]{
coin←⊃(⍵≥⍺)/⍺
coin=0:⍬
coin,⍺∇⍵-coin
}⍵
}
- Output:
(1 2 5 10 20 50 100 200) coins 988 200 4 100 1 50 1 20 1 10 1 5 1 2 1 1 1
AppleScript
----------------- MINIMUM NUMBER OF COINS ----------------
-- change :: [Int] -> Int -> [(Int, Int)]
on change(units, n)
if {} = units or 0 = n then
{}
else
set {x, xs} to {item 1 of units, rest of units}
set q to n div x
if 0 = q then
change(xs, n)
else
{{q, x}} & change(xs, n mod x)
end if
end if
end change
--------------------------- TEST -------------------------
on run
set coinReport to ¬
showChange({200, 100, 50, 20, 10, 5, 2, 1})
unlines(map(coinReport, {1024, 988}))
end run
-- showChange :: [Int] -> Int -> String
on showChange(units)
script
on |λ|(n)
script go
on |λ|(qd)
set {q, d} to qd
(q as text) & " * " & d as text
end |λ|
end script
unlines({("Summing to " & n as text) & ":"} & ¬
map(go, change(units, n))) & linefeed
end |λ|
end script
end showChange
------------------------- GENERIC ------------------------
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation
-- of a list of strings with the newline character.
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set s to xs as text
set my text item delimiters to dlm
s
end unlines
- Output:
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
Arturo
coins: [200 100 50 20 10 5 2 1]
target: 988
print ["Minimum number of coins to make a value of " (to :string target)++":"]
cnt: 0
remaining: new target
loop coins 'coin [
n: remaining / coin
if not? zero? n [
cnt: cnt + n
print [" coins of" coin "->" n]
remaining: remaining - n * coin
if zero? remaining -> break
]
]
print ["\nTotal: " cnt]
- Output:
Minimum number of coins to make a value of 988: coins of 200 -> 4 coins of 100 -> 1 coins of 50 -> 1 coins of 20 -> 1 coins of 10 -> 1 coins of 5 -> 1 coins of 2 -> 1 coins of 1 -> 1 Total: 11
AutoHotkey
coins := [1, 2, 5, 10, 20, 50, 100, 200]
val := 988
result := ""
while val
{
coin := coins.pop()
if (val//coin)
result .= val//coin " * " coin "`n", val -= val//coin * coin
}
MsgBox, 262144, , % result
return
- Output:
4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1
AWK
# syntax: GAWK -f FIND_MINIMUM_NUMBER_OF_COINS_THAT_MAKE_A_GIVEN_VALUE.AWK
BEGIN {
n = split("200,100,50,20,10,5,2,1",arr,",")
main(988)
main(388)
main(0)
exit(0)
}
function main(arg1, amount,coins,denomination,i,remaining,total) {
amount = remaining = int(arg1)
for (i=1; i<=n; i++) {
denomination = arr[i]
coins = 0
while (remaining >= denomination) {
remaining -= denomination
coins++
}
total += coins
printf("%4d x %2d = %d\n",denomination,coins,denomination*coins)
}
printf("%9d coins needed to disperse %s\n\n",total,arg1)
}
- Output:
200 x 4 = 800 100 x 1 = 100 50 x 1 = 50 20 x 1 = 20 10 x 1 = 10 5 x 1 = 5 2 x 1 = 2 1 x 1 = 1 11 coins needed to disperse 988 200 x 1 = 200 100 x 1 = 100 50 x 1 = 50 20 x 1 = 20 10 x 1 = 10 5 x 1 = 5 2 x 1 = 2 1 x 1 = 1 8 coins needed to disperse 388 200 x 0 = 0 100 x 0 = 0 50 x 0 = 0 20 x 0 = 0 10 x 0 = 0 5 x 0 = 0 2 x 0 = 0 1 x 0 = 0 0 coins needed to disperse 0
BASIC256
amount = 988
sumCoins = 0
dim coins = {1, 2, 5, 10, 20, 50, 100, 200}
print "Make a value of "; amount; " using the coins 1, 2, 5, 10, 20, 50, 100 and 200:"
for n = coins[?]-1 to 0 step -1
tmp = floor(amount/coins[n])
if tmp >= 0 then
print tmp; " * "; coins[n]
sumCoins = sumCoins + tmp
amount = amount % coins[n]
end if
next n
end
- Output:
Igual que la entrada de FreeBASIC.
C
#include <stdio.h>
#define TOTAL 988
#define Q_VALUES 8
int main() {
const int kValues[Q_VALUES] = { 200, 100, 50, 20, 10, 5, 2, 1 };
int t, q, iv;
for( t=TOTAL, iv=0; iv<Q_VALUES; t%=kValues[iv], ++iv ) {
q = t/kValues[iv];
printf( "%4d coin%c of %4d\n", q, q!=1?'s':' ', kValues[iv] );
}
return 0;
}
- Output:
4 coins of 200 1 coin of 100 1 coin of 50 1 coin of 20 1 coin of 10 1 coin of 5 1 coin of 2 1 coin of 1
Delphi
const Coins: array [0..7] of integer = (1,2,5,10,20,50,100,200);
procedure MinimumCoins(Memo: TMemo; Value: integer);
var I,C: integer;
begin
Memo.Lines.Add('Providing Change for: '+IntToStr(Value));
for I:=High(Coins) downto 0 do
begin
C:=Value div Coins[I];
Value:=Value mod Coins[I];
Memo.Lines.Add(IntToStr(C)+' coins of '+IntToStr(Coins[I]));
end;
Memo.Lines.Add('');
end;
procedure TestMinimumCoins(Memo: TMemo);
begin
MinimumCoins(Memo,988);
MinimumCoins(Memo,1307);
MinimumCoins(Memo,37511);
MinimumCoins(Memo,0);
end;
- Output:
Providing Change for: 988 4 coins of 200 1 coins of 100 1 coins of 50 1 coins of 20 1 coins of 10 1 coins of 5 1 coins of 2 1 coins of 1 Providing Change for: 1307 6 coins of 200 1 coins of 100 0 coins of 50 0 coins of 20 0 coins of 10 1 coins of 5 1 coins of 2 0 coins of 1 Providing Change for: 37511 187 coins of 200 1 coins of 100 0 coins of 50 0 coins of 20 1 coins of 10 0 coins of 5 0 coins of 2 1 coins of 1 Providing Change for: 0 0 coins of 200 0 coins of 100 0 coins of 50 0 coins of 20 0 coins of 10 0 coins of 5 0 coins of 2 0 coins of 1
EasyLang
sum = 988
coins[] = [ 200 100 50 20 10 5 2 1 ]
#
for coin in coins[]
n = sum div coin
if n > 0
print "coins of " & coin & ": " & n
sum -= n * coin
.
.
- Output:
coins of 200: 4 coins of 100: 1 coins of 50: 1 coins of 20: 1 coins of 10: 1 coins of 5: 1 coins of 2: 1 coins of 1: 1
F#
//Find minimum number of coins that make a given value - Nigel Galloway: August 12th., 20
let fN g=let rec fG n g=function h::t->fG((g/h,h)::n)(g%h) t |_->n in fG [] g [200;100;50;20;10;5;2;1]
fN 988|>List.iter(fun(n,g)->printfn "Take %d of %d" n g)
- Output:
Take 1 of 1 Take 1 of 2 Take 1 of 5 Take 1 of 10 Take 1 of 20 Take 1 of 50 Take 1 of 100 Take 4 of 200
Factor
USING: assocs kernel math math.order prettyprint sorting ;
: make-change ( value coins -- assoc )
[ >=< ] sort [ /mod swap ] zip-with nip ;
988 { 1 2 5 10 20 50 100 200 } make-change .
- Output:
{ { 200 4 } { 100 1 } { 50 1 } { 20 1 } { 10 1 } { 5 1 } { 2 1 } { 1 1 } }
FreeBASIC
#define floor(x) ((x*2.0-0.5) Shr 1)
Dim As Integer amount = 988
Dim As Integer sumCoins = 0
Dim As Integer n, tmp
Dim As Integer coins(8) = {1, 2, 5, 10, 20, 50, 100, 200}
Print "Make a value of"; amount; " using the coins 1, 2, 5, 10, 20, 50, 100 and 200:"
For n As Integer = Ubound(coins) To 0 Step -1
tmp = floor(amount/coins(n))
If tmp >= 0 Then
Print tmp; " *"; coins(n)
sumCoins += tmp
amount Mod= coins(n)
End If
Next n
Sleep
- Output:
Make a value of 988 using the coins 1, 2, 5, 10, 20, 50, 100 and 200: 4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1
FutureBasic
Task solution wrapped into a general purpose function with test examples shown.
void local fn MinimumCoinsForValue( value as NSUInteger, coins as CFArrayRef )
NSUInteger i, count, tmp
CFStringRef coinStr = fn ArrayComponentsJoinedByString( coins, @", " )
printf @"The minimum number of coins valued %@ needed to total %lu is:", coinStr, value
count = len(coins)
for i = count to 1 step -1
tmp = (NSUInteger)fn floor( value / fn NumberIntegerValue( coins[i-1] ) )
if ( tmp > 0 )
printf @"%lu * %@", tmp, coins[i-1]
value = value mod fn NumberIntegerValue( coins[i-1] )
end if
next
end fn
fn MinimumCoinsForValue( 988, @[@1, @2, @5, @10, @20, @50, @100, @200] )
print : print
fn MinimumCoinsForValue( 1024, @[@1, @2, @5, @10, @20, @50, @100, @200] )
print : print
print "Currency in this example represents U.S. denominations:"
print " 1 cent, 5 cents, 10 cents, 25 cents, 50 cents, $1, $5, $10, $20, $50"
fn MinimumCoinsForValue( 65273, @[@1, @5, @10, @25, @50, @100, @500, @1000, @2000, @5000] )
HandleEvents
- Output:
The minimum number of coins valued 1, 2, 5, 10, 20, 50, 100, 200 needed to total 988 is: 4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1 The minimum number of coins valued 1, 2, 5, 10, 20, 50, 100, 200 needed to total 1024 is: 5 * 200 1 * 20 2 * 2 Currency in this example represents U.S. denominations: 1 cent, 5 cents, 10 cents, 25 cents, 50 cents, $1, $5, $10, $20, $50 The minimum number of coins valued 1, 5, 10, 25, 50, 100, 500, 1000, 2000, 5000 needed to total 65273 is: 13 * 5000 2 * 100 1 * 50 2 * 10 3 * 1
Go
package main
import "fmt"
func main() {
denoms := []int{200, 100, 50, 20, 10, 5, 2, 1}
coins := 0
amount := 988
remaining := 988
fmt.Println("The minimum number of coins needed to make a value of", amount, "is as follows:")
for _, denom := range denoms {
n := remaining / denom
if n > 0 {
coins += n
fmt.Printf(" %3d x %d\n", denom, n)
remaining %= denom
if remaining == 0 {
break
}
}
}
fmt.Println("\nA total of", coins, "coins in all.")
}
- Output:
The minimum number of coins needed to make a value of 988 is as follows: 200 x 4 100 x 1 50 x 1 20 x 1 10 x 1 5 x 1 2 x 1 1 x 1 A total of 11 coins in all.
Haskell
import Data.List (mapAccumL)
import Data.Tuple (swap)
----------------------- FIND CHANGE ----------------------
change :: [Int] -> Int -> [(Int, Int)]
change xs n = zip (snd $ mapAccumL go n xs) xs
where
go m v = swap (quotRem m v)
--------------------------- TEST -------------------------
main :: IO ()
main =
mapM_ print $
change [200, 100, 50, 20, 10, 5, 2, 1] 988
- Output:
(4,200) (1,100) (1,50) (1,20) (1,10) (1,5) (1,2) (1,1)
Or as a hand-written recursion, defining a slightly more parsimonious listing, and allowing for denomination lists which are ill-sorted or incomplete.
import Data.List (sortOn)
import Data.Ord (Down (Down))
---------- MINIMUM NUMBER OF COINS TO MAKE A SUM ---------
change :: [Int] -> Int -> Either String [(Int, Int)]
change units n
| 0 == mod n m = Right $ go (sortOn Down units) (abs n)
| otherwise =
Left $
concat
[ "Residue of ",
show (mod n m),
" - no denomination smaller than ",
show m,
"."
]
where
m = minimum units
go _ 0 = []
go [] _ = []
go (x : xs) n
| 0 == q = go xs n
| otherwise = (q, x) : go xs r
where
(q, r) = quotRem n x
--------------------------- TEST -------------------------
main :: IO ()
main = mapM_ putStrLn $ test <$> [1024, 988]
where
test n =
either
id
( concat
. (:) ("Summing to " <> show n <> ":\n")
. fmap
( \(q, v) ->
concat
[show q, " * ", show v, "\n"]
)
)
(change [200, 100, 50, 20, 10, 5, 2, 1] n)
- Output:
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
J
coins=. [ (,: {."1@}:) [: (#: {:)/\. 0 ,. ,
1 2 5 10 20 50 100 200 coins 988
- Output:
1 2 5 10 20 50 100 200 1 1 1 1 1 1 1 4
JavaScript
(() => {
"use strict";
// -- MINIMUM NUMBER OF COINS TO MAKE A GIVEN VALUE --
// change :: [Int] -> Int -> [(Int, Int)]
const change = denominations => {
// A minimum list of (quantity, value) pairs for n.
// Unused denominations are excluded from the list.
const go = n => {
const m = abs(n);
return 0 < denominations.length && 0 < m ? (
() => {
const [h, ...t] = denominations;
const q = Math.trunc(m / h);
return (
0 < q ? [
[q, h]
] : []
).concat(change(t)(m % h));
}
)() : [];
};
return go;
};
// ---------------------- TEST -----------------------
// main :: IO ()
const main = () => {
// Two sums tested with a set of denominations.
const f = change([200, 100, 50, 20, 10, 5, 2, 1]);
return [1024, 988].reduce((acc, n) => {
const
report = f(n).reduce(
(a, [q, u]) => `${a}${q} * ${u}\n`,
""
);
return `${acc}Summing to ${abs(n)}:\n` + (
`${report}\n`
);
},
""
);
};
// --------------------- GENERIC ---------------------
// abs :: Num -> Num
const abs =
// Absolute value - without the sign.
x => 0 > x ? (
-x
) : x;
// MAIN ---
return main();
})();
- Output:
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
jq
Works with gojq, the Go implementation of jq
# If $details then provide {details, coins}, otherwise just the number of coins.
def minimum_number($details):
. as $amount
| [200, 100, 50, 20, 10, 5, 2, 1] as $denoms
| {coins: 0, remaining: 988, details: []}
| label $out
| foreach $denoms[] as $denom (.;
((.remaining / $denom)|floor) as $n
| if $n > 0
then .coins += $n
| if $details then .details += [{$denom, $n}] else . end
| .remaining %= $denom
else . end;
if .remaining == 0 then ., break $out else empty end)
| if $details then {details, coins} else .coins end ;
# Verbose mode:
def task:
"\nThe minimum number of coins needed to make a value of \(.) is as follows:",
(minimum_number(true)
| .details[],
"\nA total of \(.coins) coins in all." );
988
| minimum_number(false), # illustrate minimal output
task # illustrate detailed output
- Output:
11 The minimum number of coins needed to make a value of 988 is as follows: {"denom":200,"n":4} {"denom":100,"n":1} {"denom":50,"n":1} {"denom":20,"n":1} {"denom":10,"n":1} {"denom":5,"n":1} {"denom":2,"n":1} {"denom":1,"n":1} A total of 11 coins in all.
Julia
Long version
Using a linear optimizer for this is serious overkill, but why not?
using JuMP, GLPK
model = Model(GLPK.Optimizer)
@variable(model, ones, Int)
@variable(model, twos, Int)
@variable(model, fives, Int)
@variable(model, tens, Int)
@variable(model, twenties, Int)
@variable(model, fifties, Int)
@variable(model, onehundreds, Int)
@variable(model, twohundreds, Int)
@constraint(model, ones >= 0)
@constraint(model, twos >= 0)
@constraint(model, fives >= 0)
@constraint(model, tens >= 0)
@constraint(model, twenties >= 0)
@constraint(model, fifties >= 0)
@constraint(model, onehundreds >= 0)
@constraint(model, twohundreds >= 0)
@constraint(model, 988 == 1ones +2twos + 5fives + 10tens + 20twenties + 50fifties + 100onehundreds + 200twohundreds)
@objective(model, Min, ones + twos + fives + tens + twenties + fifties + onehundreds + twohundreds)
optimize!(model)
println("Optimized total coins: ", objective_value(model))
for val in [ones, twos, fives, tens, twenties, fifties, onehundreds, twohundreds]
println("Value of ", string(val), " is ", value(val))
end
- Output:
Optimized total coins: 11.0 Value of ones is 1.0 Value of twos is 1.0 Value of fives is 1.0 Value of tens is 1.0 Value of twenties is 1.0 Value of fifties is 1.0 Value of onehundreds is 1.0 Value of twohundreds is 4.0
Brief REPL command version
julia> accumulate((x, y) -> (x[1] % y, (y, x[1] ÷ y)), [200, 100, 50, 20, 10, 5, 2, 1], init=(988, 0)) 8-element Vector{Tuple{Int64, Tuple{Int64, Int64}}}: (188, (200, 4)) (88, (100, 1)) (38, (50, 1)) (18, (20, 1)) (8, (10, 1)) (3, (5, 1)) (1, (2, 1)) (0, (1, 1))
Lua
do -- find the minimum number of coins needed to make a given value
-- translated from the Wren sample
local denoms = { 200, 100, 50, 20, 10, 5, 2, 1 }
local amount = 988;
local coins, remaining = 0, amount
print( "The minimum number of coins needed to make a value of "..amount.." is as follows:" )
for _, denom in pairs( denoms ) do
local n = math.floor( remaining / denom )
if n > 0 then
coins = coins + n
print( string.format( "%6d", denom ).." x "..n )
remaining = remaining % denom
end
if remaining == 0 then break end
end
print( "A total of "..coins.." coins in all." )
end
- Output:
The minimum number of coins needed to make a value of 988 is as follows: 200 x 4 100 x 1 50 x 1 20 x 1 10 x 1 5 x 1 2 x 1 1 x 1 A total of 11 coins in all.
Mathematica/Wolfram Language
coins = {1, 2, 5, 10, 20, 50, 100, 200};
out = v /. ConvexOptimization[Total[v], coins . v == 988, v \[Element] Vectors[8, NonNegativeIntegers]];
MapThread[Row[{#1, " x ", #2}] &, {out, coins}] // Column
- Output:
1 x 1 1 x 2 1 x 5 1 x 10 1 x 20 1 x 50 1 x 100 4 x 200
MiniZinc
%Find minimum number of coins that make a given value. Nigel Galloway, August 11th., 2021
int: N=988;
array [1..8] of int: coinValue=[1,2,5,10,20,50,100,200];
array [1..8] of var 0..N: take; constraint sum(n in 1..8)(take[n]*coinValue[n])=N;
solve minimize sum(n in 1..8)(take[n]);
output(["Take "++show(take[n])++" of "++show(coinValue[n])++"\n" | n in 1..8])
- Output:
Take 1 of 1 Take 1 of 2 Take 1 of 5 Take 1 of 10 Take 1 of 20 Take 1 of 50 Take 1 of 100 Take 4 of 200 ---------- ========== Finished in 196msec
Nim
import strformat
const
Coins = [200, 100, 50, 20, 10, 5, 2, 1]
Target = 988
echo &"Minimal number of coins to make a value of {Target}:"
var count = 0
var remaining = Target
for coin in Coins:
let n = remaining div coin
if n != 0:
inc count, n
echo &"coins of {coin:3}: {n}"
dec remaining, n * coin
if remaining == 0: break
echo "\nTotal: ", count
- Output:
Minimal number of coins to make a value of 988: coins of 200: 4 coins of 100: 1 coins of 50: 1 coins of 20: 1 coins of 10: 1 coins of 5: 1 coins of 2: 1 coins of 1: 1 Total: 11
Perl
use strict;
use warnings;
my @denominations = <200 100 50 20 10 5 2 1>;
sub change {
my $n = shift;
my @a;
push(@a, int $n/$_) and $n %= $_ for @denominations;
@a
}
my @amounts = change 988;
for (0 .. $#amounts) {
printf "%1d * %3d\n", $amounts[$_], $denominations[$_]
}
- Output:
4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1
Phix
with javascript_semantics requires("1.0.1") -- (lastdelim added to the join() function) sequence coins = {1,2,5,10,20,50,100,200} string strc = join(apply(coins,sprint),", ", ", and ") atom total = 988 printf(1,"Make a value of %d using the coins %s:\n",{total,strc}) integer count = 0 for i=length(coins) to 1 by -1 do integer ci = coins[i], c = floor(total/ci) if c then printf(1,"%6s coin%s of %3d\n",{ordinal(c,true),iff(c>1?"s":" "),ci}) count += c total = remainder(total,ci) if total=0 then exit end if end if end for printf(1,"%s coins were used.\n",{proper(ordinal(count,true))})
- Output:
Make a value of 988 using the coins 1, 2, 5, 10, 20, 50, 100, and 200: four coins of 200 one coin of 100 one coin of 50 one coin of 20 one coin of 10 one coin of 5 one coin of 2 one coin of 1 Eleven coins were used.
Python
Python :: Procedural
def makechange(denominations = [1,2,5,10,20,50,100,200], total = 988):
print(f"Available denominations: {denominations}. Total is to be: {total}.")
coins, remaining = sorted(denominations, reverse=True), total
for n in range(len(coins)):
coinsused, remaining = divmod(remaining, coins[n])
if coinsused > 0:
print(" ", coinsused, "*", coins[n])
makechange()
- Output:
Available denominations: [1, 2, 5, 10, 20, 50, 100, 200]. Total is to be: 988. 4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1
Python :: Functional
'''Minimum number of coins to make a given value'''
# change :: [Int] -> Int -> [(Int, Int)]
def change(xs):
'''A list of (quantity, denomination) pairs.
Unused denominations are excluded from the list.
'''
def go(n):
if xs and n:
h, *t = xs
q, r = divmod(n, h)
return ([(q, h)] if q else []) + (
change(t)(r)
)
else:
return []
return go
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''Testing a set of denominations with two sums'''
f = change([200, 100, 50, 20, 10, 5, 2, 1])
print(
"\n".join([
f'Summing to {n}:\n' + "\n".join([
f'{qu[0]} * {qu[1]}' for qu in f(n)]
) + "\n"
for n in [1024, 988]
])
)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
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
Quackery
[ ' [ 200 100 50 20 10 5 2 1 ] ] is coins ( --> [ )
[ [] swap
coins witheach
[ /mod dip join ]
drop
witheach
[ dup 0 > iff
[ echo say " * "
coins i^ peek echo
cr ]
else drop ] ] is task ( n --> )
' [ 988 345 1024 ]
witheach
[ say "To make "
dup echo say ":" cr
task cr ]
- Output:
To make 988: 4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1 To make 345: 1 * 200 1 * 100 2 * 20 1 * 5 To make 1024: 5 * 200 1 * 20 2 * 2
Raku
Since unit denominations are possible, don't bother to check to see if an exact pay-out isn't possible.
my @denominations = 200, 100, 50, 20, 10, 5, 2, 1;
sub change (Int $n is copy where * >= 0) { gather for @denominations { take $n div $_; $n %= $_ } }
for 988, 1307, 37511, 0 -> $amount {
say "\n$amount:";
printf "%d × %d\n", |$_ for $amount.&change Z @denominations;
}
- Output:
988: 4 × 200 1 × 100 1 × 50 1 × 20 1 × 10 1 × 5 1 × 2 1 × 1 1307: 6 × 200 1 × 100 0 × 50 0 × 20 0 × 10 1 × 5 1 × 2 0 × 1 37511: 187 × 200 1 × 100 0 × 50 0 × 20 1 × 10 0 × 5 0 × 2 1 × 1 0: 0 × 200 0 × 100 0 × 50 0 × 20 0 × 10 0 × 5 0 × 2 0 × 1
Red
Red[]
value: 988
foreach denomination [200 100 50 20 10 5 2 1][
quantity: to-integer value / denomination
unless 0 = quantity [print [quantity "*" denomination]]
value: value % denomination
]
- Output:
4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1
REXX
A check was made to see if an exact pay─out isn't possible.
The total number of coins paid out is also shown.
/*REXX pgm finds & displays the minimum number of coins which total to a specified value*/
parse arg $ coins /*obtain optional arguments from the CL*/
if $='' | $="," then $= 988 /*Not specified? Then use the default.*/
if coins='' | coins="," then coins= 1 2 5 10 20 50 100 200 /* ... " " " " */
#= words(coins) /*#: is the number of allowable coins.*/
w= 0 /*width of largest coin (for alignment)*/
do j=1 for #; @.j= word(coins, j) /*assign all coins to an array (@.). */
w= max(w, length(@.j) ) /*find the width of the largest coin. */
end /*j*/
say 'available coin denominations: ' coins /*shown list of available denominations*/
say
say center(' making change for ' $, 30 ) /*display title for the upcoming output*/
say center('' , 30, "─") /* " sep " " " " */
koins= 0 /*the total number of coins dispensed. */
paid= 0 /*the total amount of money paid so far*/
do k=# by -1 for #; z= $ % @.k /*start with largest coin for payout. */
if z<1 then iterate /*if Z is not positive, then skip coin.*/
koins= koins + z
paid= z * @.k /*pay out a number of coins. */
$= $ - paid /*subtract the pay─out from the $ total*/
say right(z,9) ' of coin ' right(@.k, w) /*display how many coins were paid out.*/
end /*k*/
say center('' , 30, "─") /* " sep " " " " */
say
say 'number of coins dispensed: ' koins
if $>0 then say 'exact payout not possible.' /*There a residue? Payout not possible*/
exit 0 /*stick a fork in it, we're all done. */
- output when using the default inputs:
available coin denominations: 1 2 5 10 20 50 100 200 making change for 988 ────────────────────────────── 4 of coin 200 1 of coin 100 1 of coin 50 1 of coin 20 1 of coin 10 1 of coin 5 1 of coin 2 1 of coin 1 ────────────────────────────── number of coins dispensed: 11
Ring
load "stdlib.ring"
see "working..." + nl
see "Coins are:" + nl
sum = 988
sumCoins = 0
coins = [1,2,5,10,20,50,100,200]
coins = reverse(coins)
for n = 1 to len(coins)
nr = floor(sum/coins[n])
if nr > 0
sumCoins= nr*coins[n]
sum -= sumCoins
see "" + nr + "*" + coins[n] + nl
ok
next
see "done..." + nl
- Output:
working... Coins are: 4*200 1*100 1*50 1*20 1*10 1*5 1*2 1*1 done...
RPL
« { 200 100 50 20 10 5 2 1 } { }
→ coinset result
« 1 coinset SIZE FOR j
coinset j GET
MOD LASTARG / IP
'result' SWAP STO+
NEXT
DROP result DUP ∑LIST "coins" →TAG
» » 'COINS' STO
988 COINS
- Output:
2: { 4 1 1 1 1 1 1 1 } 1: coins: 11
Rust
fn main() {
let denoms = vec![200, 100, 50, 20, 10, 5, 2, 1];
let mut coins = 0;
let amount = 988;
let mut remaining = 988;
println!("The minimum number of coins needed to make a value of {} is as follows:", amount);
for denom in denoms.iter() {
let n = remaining / denom;
if n > 0 {
coins += n;
println!(" {} x {}", denom, n);
remaining %= denom;
if remaining == 0 {
break;
}
}
}
println!("\nA total of {} coins in all.", coins);
}
- Output:
The minimum number of coins needed to make a value of 988 is as follows: 200 x 4 100 x 1 50 x 1 20 x 1 10 x 1 5 x 1 2 x 1 1 x 1 A total of 11 coins in all.
V (Vlang)
fn main() {
denoms := [200, 100, 50, 20, 10, 5, 2, 1]
amount := 988
mut coins := 0
mut remaining := 988
mut n := 0
println("The minimum number of coins needed to make a value of ${amount} is as follows:")
for denom in denoms {
n = remaining / denom
if n > 0 {
coins += n
print(" ${denom} x ${n}" + "\n")
remaining %= denom
if remaining == 0 {break}
}
}
println("\nA total of ${coins} coins in all.")
}
- Output:
The minimum number of coins needed to make a value of 988 is as follows: 200 x 4 100 x 1 50 x 1 20 x 1 10 x 1 5 x 1 2 x 1 1 x 1 A total of 11 coins in all.
Wren
As there is, apparently, an unlimited supply of coins of each denomination, it follows that any amount can be made up.
import "./fmt" for Fmt
var denoms = [200, 100, 50, 20, 10, 5, 2, 1]
var coins = 0
var amount = 988
var remaining = 988
System.print("The minimum number of coins needed to make a value of %(amount) is as follows:")
for (denom in denoms) {
var n = (remaining / denom).floor
if (n > 0) {
coins = coins + n
Fmt.print(" $3d x $d", denom, n)
remaining = remaining % denom
if (remaining == 0) break
}
}
System.print("\nA total of %(coins) coins in all.")
- Output:
The minimum number of coins needed to make a value of 988 is as follows: 200 x 4 100 x 1 50 x 1 20 x 1 10 x 1 5 x 1 2 x 1 1 x 1 A total of 11 coins in all.
XPL0
int Denom, Denoms, Coins, Amount, Remaining, I, N;
[Denoms:= [200, 100, 50, 20, 10, 5, 2, 1];
Coins:= 0;
Amount:= 988;
Remaining:= 988;
Text(0, "The minimum number of coins needed to make a value of ");
IntOut(0, Amount); Text(0, " is as follows:
");
Format(3, 0);
for I:= 0 to 7 do
[Denom:= Denoms(I);
N:= Remaining/Denom;
if N > 0 then
[Coins:= Coins + N;
RlOut(0, float(Denom)); Text(0, " x "); IntOut(0, N); CrLf(0);
Remaining:= rem(Remaining/Denom);
if Remaining = 0 then I:= 7;
];
];
Text(0, "
A total of "); IntOut(0, Coins); Text(0, " coins in all.
");
]
- Output:
The minimum number of coins needed to make a value of 988 is as follows: 200 x 4 100 x 1 50 x 1 20 x 1 10 x 1 5 x 1 2 x 1 1 x 1 A total of 11 coins in all.
Yabasic
amount = 988
sumCoins = 0
dim coins(7)
coins(0) = 1
coins(1) = 2
coins(2) = 5
coins(3) = 10
coins(4) = 20
coins(5) = 50
coins(6) = 100
coins(7) = 200
print "Make a value of ", amount, " using the coins 1, 2, 5, 10, 20, 50, 100 and 200:"
for n = arraysize(coins(),1) to 0 step -1
tmp = floor(amount/coins(n))
if tmp >= 0 then
print tmp, " * ", coins(n)
sumCoins = sumCoins + tmp
amount = mod(amount, coins(n))
end if
next n
end
- Output:
Igual que la entrada de FreeBASIC.