Count the coins: Difference between revisions
m
→{{header|Delphi}}
(38 intermediate revisions by 18 users not shown) | |||
Line 34:
=={{header|11l}}==
{{trans|Python}}
<
V ways = [Int64(0)] * (amount + 1)
ways[0] = 1
Line 43:
print(changes(100, [1, 5, 10, 25]))
print(changes(100000, [1, 5, 10, 25, 50, 100]))</
Output:
Line 53:
=={{header|360 Assembly}}==
{{trans|AWK}}
<
COINS CSECT
USING COINS,R12
Line 111:
PG DS CL12
YREGS
END COINS</
{{out}}
<pre>
Line 121:
{{Works with|gnat/gcc}}
<
procedure Count_The_Coins is
Line 152:
Print(Count( 1_00, (25, 10, 5, 1)));
Print(Count(1000_00, (100, 50, 25, 10, 5, 1)));
end Count_The_Coins;</
Output:<pre> 242
13398445413854501</pre>
Alternate method that keeps track of the specific combinations of coins:
<syntaxhighlight lang="ada">
with Ada.Text_IO; use Ada.Text_IO;
procedure Main is
count: Integer;
begin
count := 0;
for penny in 0 .. 100 loop
for nickel in 0 .. 20 loop
for dime in 0 .. 10 loop
for quarter in 0 .. 4 loop
if (penny + 5 * nickel + 10 * dime + 25 * quarter = 100)
then
Put_Line(Integer'Image(count+1) & ": " &
Integer'Image(penny) & " pennies, " &
Integer'Image(nickel) & " nickels, " &
Integer'Image(dime) & " dimes, " &
Integer'Image(quarter) & " quarters");
count := count + 1;
end if;
end loop;
end loop;
end loop;
end loop;
Put_Line("The number of ways to make change for a dollar is: " & Integer'Image(count));
end Main;
</syntaxhighlight>
Output:<pre>
1: 0 pennies, 0 nickels, 0 dimes, 4 quarters
2: 0 pennies, 0 nickels, 5 dimes, 2 quarters
3: 0 pennies, 0 nickels, 10 dimes, 0 quarters
4: 0 pennies, 1 nickels, 2 dimes, 3 quarters
5: 0 pennies, 1 nickels, 7 dimes, 1 quarters
.....................
239: 90 pennies, 0 nickels, 1 dimes, 0 quarters
240: 90 pennies, 2 nickels, 0 dimes, 0 quarters
241: 95 pennies, 1 nickels, 0 dimes, 0 quarters
242: 100 pennies, 0 nickels, 0 dimes, 0 quarters
The number of ways to make change for a dollar is: 242
</pre>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.4.1}}
{{trans|Haskell}}
<syntaxhighlight lang="algol68">
#
Rosetta Code "Count the coins"
Line 192 ⟶ 235:
print((ways to make change(denoms, 100), newline))
END
</syntaxhighlight>
Output:<pre>
+242
Line 198 ⟶ 241:
{{works with|ALGOL 68G|Any - tested with release 2.8.4}}
{{trans|Haskell}}
<syntaxhighlight lang="algol68">
#
Rosetta Code "Count the coins"
Line 231 ⟶ 274:
print((ways to make change((1, 5, 10, 25, 50, 100), 100000), newline))
END
</syntaxhighlight>
Output:<pre>
+242
Line 242 ⟶ 285:
{{trans|Phix}}
<
on countCoins(amount, denominations)
-- Potentially long list of counters, initialised with 1 (result for amount 0) and 'amount' zeros.
Line 271 ⟶ 314:
set c1 to countCoins(100, {25, 10, 5, 1})
set c2 to countCoins(1000 * 100, {100, 50, 25, 10, 5, 1})
return {c1, c2}</
{{output}}
<syntaxhighlight lang
=={{header|Applesoft BASIC}}==
{{trans|Commodore BASIC}}
<syntaxhighlight lang="gwbasic">C=0:M=100:F=25:T=10:S=5:Q=INT(M/F):FORI=0TOQ:D=INT((M-I*F)/T):FORJ=0TOD:N=INT((M-J*T)/S):FORK=0TON:P=M-K*S:FORL=0TOPSTEPS:C=C+(L+K*S+J*T+I*F=M):NEXTL,K,J,I:?C;</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">changes: function [amount coins][
ways: map 0..amount+1 [x]-> 0
ways\0:
loop coins
loop coin..amount
set ways
]
ways\[amount]
]
print changes 100 [1 5 10 25]
print changes 100000 [1 5 10 25 50 100]</syntaxhighlight>
=={{header|AutoHotkey}}==
{{trans|Go}}
{{Works with|AutoHotkey_L}}
<
return cc(amount, 4)
}
Line 318 ⟶ 357:
return [1, 5, 10, 25][kindsOfCoins]
}
MsgBox % countChange(100)</
=={{header|AWK}}==
Line 324 ⟶ 363:
Iterative implementation, derived from Run BASIC:
<
BEGIN {
Line 350 ⟶ 389:
return count;
}
</syntaxhighlight>
Run time:
Line 362 ⟶ 401:
Recursive implementation (derived from Scheme example):
<
BEGIN {
Line 389 ⟶ 428:
return koins[1]
}
</syntaxhighlight>
Run time:
Line 403 ⟶ 442:
=={{header|BBC BASIC}}==
Non-recursive solution:
<
uscoins%() = 1, 5, 10, 25
PRINT FNchange(100, uscoins%()) " ways of making $1"
Line 439 ⟶ 478:
NEXT
= table(P%-1)
</syntaxhighlight>
Output (BBC BASIC does not have large enough integers for the optional task):
<pre> 242 ways of making $1
Line 448 ⟶ 487:
=={{header|C}}==
Using some crude 128-bit integer type.
<
#include <stdlib.h>
#include <stdint.h>
Line 547 ⟶ 586:
return 0;
}</
13398445413854501
1333983445341383545001
Line 555 ⟶ 594:
10056050940818192726001
99341140660285639188927260001
992198221207406412424859964272600001</
=={{header|C sharp|C#}}==
<
// Adapted from http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
class Program
Line 580 ⟶ 619:
}
}
</syntaxhighlight>
=={{header|C++}}==
<
#include <iostream>
#include <stack>
Line 617 ⟶ 656:
std::cout << ways << std::endl;
return 0;
}</
{{out}}
Line 623 ⟶ 662:
=={{header|Clojure}}==
<
(defn- cc [amount denominations]
Line 636 ⟶ 675:
(cc amount denominations))
(count-change 15 denomination-kind) ; = 6 </
=={{header|COBOL}}==
{{trans|C#}}
<
identification division.
program-id. CountCoins.
Line 672 ⟶ 711:
end-perform
.
</syntaxhighlight>
{{out}}
<pre>242</pre>
Line 680 ⟶ 719:
{{trans|Python}}
<
ways = [1].concat [0] * amount
for coin of coins
Line 687 ⟶ 726:
ways[amount]
console.log changes 100, [1 5 10 25]</
=={{header|Commodore BASIC}}==
Line 702 ⟶ 741:
<
10 print chr$(147);chr$(14);"This program will calculate the number"
11 print "of combinations of 'change' that can be"
Line 728 ⟶ 767:
265 print left$(en$,2);":";mid$(en$,3,2);":";right$(en$,2);"."
270 end
1000 print count;tab(6);pc;tab(11);nc;tab(16);dc;tab(21);qc:return</
'''Example 2:''' Commodore 64 with Screen Blanking
Line 736 ⟶ 775:
Enabling screen blanking (and therefore not printing each result) results in a total time of 1:44.
<
245 en$=ti$:if not yn then poke 53265,peek(53265) or 16</
'''Example 3:''' Commodore 128 with VIC-II blanking, 2MHz fast mode.
Line 743 ⟶ 782:
Similar to above, however the Commodore 128 is capable of using a faster clock speed at the expense of any VIC-II graphics display. Timed result is 1:18. Add/change the following lines on the Commodore 128:
<
245 en$=ti$:if not yn then slow</
=={{header|Common Lisp}}==
===Recursive Version With Cache===
<
&optional
(length (1- (length coins)))
Line 765 ⟶ 804:
(print (count-change 100 '(25 10 5 1))) ; = 242
(print (count-change 100000 '(100 50 25 10 5 1))) ; = 13398445413854501
(terpri)</
===Iterative Version===
<
(setf (aref ways 0) 1)
(loop for coin in coins do
(loop for j from coin upto amount
do (incf (aref ways j) (aref ways (- j coin)))))
(aref ways amount))</
=={{header|D}}==
===Basic Version===
{{trans|Go}}
<
auto changes(int amount, int[] coins) {
Line 792 ⟶ 831:
changes( 1_00, [25, 10, 5, 1]).writeln;
changes(1000_00, [100, 50, 25, 10, 5, 1]).writeln;
}</
{{out}}
<pre>242
Line 799 ⟶ 838:
===Safe Ulong Version===
This version is very similar to the precedent, but it uses a faster ulong type, and performs a checked sum to detect overflows at run-time.
<
auto changes(int amount, int[] coins, ref bool overflow) {
Line 819 ⟶ 858:
if (overflow)
"Overflow".puts;
}</
The output is the same.
===Faster Version===
{{trans|C}}
<
BigInt countChanges(in int amount, in int[] coins) pure /*nothrow*/ {
Line 865 ⟶ 904:
writeln;
}
}</
{{out}}
<pre>242
Line 880 ⟶ 919:
A much faster version that mixes high-level and low-level style programming. This version uses basic 128-bit unsigned integers, like the C version. The output is the same as the second D version.
{{trans|C}}
<
struct Ucent { /// Simplified 128-bit integer (like ucent).
Line 939 ⟶ 978:
writeln;
}
}</
===Printing Version===
This version prints all the solutions (so it can be used on the smaller input):
<
void printChange(in uint tot, in uint[] coins)
Line 974 ⟶ 1,013:
void main() {
printChange(1_00, [1, 5, 10, 25]);
}</
{{out}}
<pre>1:5 5:1 10:4 25:2
Line 1,003 ⟶ 1,042:
=={{header|Dart}}==
Simple recursive version plus cached version using a map.
=== Dart 1 version: ===
<syntaxhighlight lang="dart">
var cache = new Map();
Line 1,060 ⟶ 1,101:
return(count);
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,067 ⟶ 1,108:
... completed in 3.604 seconds
</pre>
=== Dart 2 version: ===
<syntaxhighlight lang="dart">
/// Provides the same result and performance as the Dart 1 version
/// but using the Dart 2 specifications.
Map<String, int> cache = {};
void main() {
Stopwatch stopwatch = Stopwatch()..start();
/// Use the brute-force recursion for the small problem
int amount = 100;
List<int> coinTypes = [25,10,5,1];
print ("${coins(amount,coinTypes)} ways for $amount using $coinTypes coins.");
/// Use the cache version for the big problem
amount = 100000;
coinTypes = [100,50,25,10,5,1];
print ("${cachedCoins(amount,coinTypes)} ways for $amount using $coinTypes coins.");
stopwatch.stop();
print ("... completed in ${stopwatch.elapsedMilliseconds/1000} seconds");
}
int cachedCoins(int amount, List<int> coinTypes) {
int count = 0;
/// This is more efficient, looks at last two coins.
/// But not fast enough for the optional exercise.
if(coinTypes.length == 2) return (amount ~/ coinTypes[0] + 1);
/// Looks like "100.[25,10,5,1]"
String key = "$amount.$coinTypes";
/// Check whether we have seen this before
var cacheValue = cache[key];
if(cacheValue != null) return(cacheValue);
count = 0;
/// Same recursion as simple method, but caches all subqueries too
for(int i=0; i<=amount ~/ coinTypes[0]; i++){
count += cachedCoins(amount-(i*coinTypes[0]),coinTypes.sublist(1)); // sublist(1) is like lisp's '(rest ...)'
}
/// add this to the cache
cache[key] = count;
return count;
}
int coins(int amount, List<int> coinTypes) {
int count = 0;
/// Just pennies available, so only one way to make change
if(coinTypes.length == 1) return (1);
/// Brute force recursion
for(int i=0; i<=amount ~/ coinTypes[0]; i++){
/// sublist(1) is like lisp's '(rest ...)'
count += coins(amount - (i*coinTypes[0]),coinTypes.sublist(1));
}
/// Uncomment if you want to see intermediate steps
/// print("there are " + count.toString() +" ways to count change for ${amount.toString()} using ${coinTypes} coins.");
return count;
}
</syntaxhighlight>
{{out}}
<pre>
242 ways for 100 using [25, 10, 5, 1] coins.
13398445413854501 ways for 100000 using [100, 50, 25, 10, 5, 1] coins.
... completed in 2.921 seconds
Process finished with exit code 0
</pre>
=={{header|Delphi}}==
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Count_the_coins;
Line 1,099 ⟶ 1,217:
Readln;
end.
</syntaxhighlight>
{{out}}
<pre>242</pre>
=={{header|Draco}}==
<syntaxhighlight lang="draco">proc main() void:
[4]byte coins = (1, 5, 10, 25);
[101]byte tab;
word m, n;
for n from 1 upto 100 do tab[n] := 0 od;
tab[0] := 1;
for m from 0 upto 3 do
for n from coins[m] upto 100 do
tab[n] := tab[n] + tab[n - coins[m]]
od
od;
writeln(tab[100])
corp</syntaxhighlight>
{{out}}
<pre>242</pre>
=={{header|Dyalect}}==
<
var xs = Array.
xs[0] = 1
for c in coins {
Line 1,116 ⟶ 1,257:
var coins = [1, 5, 10, 25]
print(countCoins(coins, 100))</
{{out}}
<pre>242</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
len cache[] 100000 * 7 + 6
val[] = [ 1 5 10 25 50 100 ]
func count sum kind .
if sum = 0
return 1
.
if sum < 0 or kind = 0
return 0
.
chind = sum * 7 + kind
if cache[chind] > 0
return cache[chind]
.
r2 = count (sum - val[kind]) kind
r1 = count sum (kind - 1)
r = r1 + r2
cache[chind] = r
return r
.
print count 100 4
print count 10000 6
print count 100000 6
# this is not exact, since numbers
# are doubles and r > 2^53
</syntaxhighlight>
=={{header|EchoLisp}}==
Recursive solution using memoization, adapted from CommonLisp and Racket.
<
(lib 'compile) ;; for (compile)
(lib 'bigint) ;; integer results > 32 bits
Line 1,145 ⟶ 1,315:
(compile 'ways) ;; speed-up things
</syntaxhighlight>
{{out}}
<
(define change '(25 10 5 1))
(define c-1 (list-tail change -1)) ;; pointer to (1)
Line 1,180 ⟶ 1,350:
→ 13398445413854501
</syntaxhighlight>
=={{header|EDSAC order code}}==
The program solves the first task for the US dollar and UK pound, using an algorithm copied from the C# and Delphi solutions. The second task is not attempted.
Note: When the table is initialized, not only must the first entry be set to 1, but the other entries must be set to 0. It seems that the C# and Delphi solutions rely on the compiler to do this. In other languages, it may need to be done by the program.
<syntaxhighlight lang="edsac">
["Count the coins" problem for Rosetta Code.]
[EDSAC program, Initial Orders 2.]
T51K P56F [G parameter: print subroutine]
T54K P94F [C parameter: coins subroutine]
T47K P200F [M parameter: main routine]
[========================== M parameter ===============================]
E25K TM GK
[Parameter block for US coins. For convenience, all numbers
are in the address field, e.g. 25 cents is P25F not P12D.]
[0] UF SF [2-letter ID]
P100F [amount to be made with coins]
P4F [number of coin values]
P1F P5F P10F P25F [list of coin values]
[8] P@ [address of US parameter block]
[Parameter block for UK coins]
[9] UF KF
P100F
P7F
P1F P2F P5F P10F P20F P50F P100F
[20] P9@ [address of UK parameter block]
[Enter with acc = 0]
[21] A8@ [load address of parameter block for US coins]
T4F [pass to subroutine in 4F]
[23] A23@ [call subroutine to calculate and print result]
G13C
A20@ [same for UK coins]
T4F
[27] A27@
G13C
ZF [halt program]
[========================== C parameter ===============================]
[Subroutine to calculate and print the result for the given amount and
set of coins. Address of parameter block (see above) is passed in 4F.]
E25K TC GK
[0] SF [S order for start of coin list]
[1] A1023F [start table at top of memory and work downwarda]
[2] PF [S order for exclusive end of coin list]
[3] P2F [to increment address by 2]
[4] OF [(1) add to address to make O order
(2) add to A order to make T order with same address]
[5] SF [add to address to make S order]
[6] K4095F [add to S order to make A order, dec address]
[7] K2048F [set teleprinter to letters]
[8] #F [set teleprinter to figures]
[9] !F [space character]
[10] @F [carriage return]
[11] &F [line feed]
[12] K4096F [teleprinter null]
[Subroutine entry. In this EDSAC program, the table used
in the algorithm grows downward from the top of memory.]
[13] A3F [plant jump back to caller, as usual]
T89@
A4F [load address of parameter block]
A3@ [skip 2-letter ID]
A5@ [make S order for amount]
U27@ [plant in code]
A3@ [make S order for first coin value]
U@ [store it]
A6@ [make A order for number of coins]
T38@ [plant in code]
A2F [load 1 (in address field)]
[24] T1023F [store at start of table]
[Set all other table entries to 0]
A24@
T32@
[27] SF [acc := -amount]
[28] TF [set negative count in 0F]
A32@ [decrement address in manufactured order]
S2F
T32@
[32] TF [manufactured: set table entry to 0]
AF [update negative count]
A2F
G28@ [loop until count = 0]
[Here acc = 0. Manufactured order (4 lines up) is T order
for inclusive end of table; this is used again below.]
A@ [load S order for first coin value]
U43@ [plant in code]
[38] AF [make S order for exclusive end of coin list]
T2@ [store for comparison]
[Start of outer loop, round coin values]
[40] TF [clear acc]
A1@ [load A order for start of table]
U48@ [plant in code]
[43] SF [manufactured order: subtract coin value]
[Start of inner loop, round table entries]
[44] U47@ [plant A order in code]
A4@ [make T order for same address]
T49@ [plant in code]
[The next 3 orders are manufactured at run time]
[47] AF [load table entry]
[48] AF [add earlier table entry]
[49] TF [update table entry]
A32@ [load T order for inclusive end of table]
S49@ [reached end of table?]
E60@ [if yes, jump out of inner loop]
TF [clear acc]
A48@ [update the 3 manufactured instructions]
S2F
T48@
A47@
S2F
G44@ [always loops back, since A < 0]
[End of inner loop]
[60] TF [clear acc]
A43@ [update S order for coin value]
A2F
U43@
S2@ [reached exclusive end?]
G40@ [if no, loop back]
[End of outer loop]
[Here with acc = 0 and result at end of table]
[Value is in address field, so shift 1 right for printing]
A32@ [load T order for end of tab;e]
S4@ [make A order for same address]
T79@ [plant in code]
A4F [load address of parameter block]
A4@ [make O order for 1st char of ID]
U75@ [plant in code]
A2F [same for 2nd char]
T76@
O7@ [set teleprinter to letters]
[75] OF [print ID, followed by space]
[76] OF O9@
O8@ [set teleprinter to figures]
[79] AF [maunfactured order to load result]
RD [shift 1 right for printing]
TF [pass to print routine]
A9@ [replace leading 0's with space]
T1F
[84] A84@ [call print routine]
GG
O10@ O11@ [print CR, LF]
O12@ [print null to flush teleprinter buffer]
[89] ZF [replaced by jump back to caller]
[============================= G parameter ===============================]
E25K TG GK
[Subroutine to print non-negative 17-bit integer. Always prints 5 chars.
Caller specifies character for leading 0 (typically 0, space or null).
Parameters: 0F = integer to be printed (not preserved)
1F = character for leading zero (preserved)
Workspace: 4F..7F, 38 locations]
A3FT34@A1FT7FS35@T6FT4#FAFT4FH36@V4FRDA4#FR1024FH37@E23@O7FA2F
T6FT5FV4#FYFL8FT4#FA5FL1024FUFA6FG16@OFTFT7FA6FG17@ZFP4FZ219DTF
[========================== M parameter again ===============================]
E25K TM GK
E21Z [define entry point]
PF [enter with acc = 0]
</syntaxhighlight>
{{out}}
<pre>
US 242
UK 4563
</pre>
=={{header|Elixir}}==
Recursive Dynamic Programming solution in Elixir
<
def find(coins,lim) do
vals = Map.new(0..lim,&{&1,0}) |> Map.put(0,1)
Line 1,207 ⟶ 1,544:
Coins.find([1,5,10,25],100)
Coins.find([1,5,10,25,50,100],100_000)</
{{out}}
Line 1,216 ⟶ 1,553:
=={{header|Erlang}}==
<
-module(coins).
-compile(export_all).
Line 1,248 ⟶ 1,585:
A2 = 100000, C2 = [100, 50, 25, 10, 5, 1],
print(A2,C2).
</syntaxhighlight>
{{out}}
Line 1,259 ⟶ 1,596:
{{trans|OCaml}}
<p>Forward iteration, which can also be seen in Scala.</p>
<
let ways = Array.zeroCreate (amount + 1)
ways.[0] <- 1L
Line 1,271 ⟶ 1,608:
printfn "%d" (changes 100 [25; 10; 5; 1]);
printfn "%d" (changes 100000 [100; 50; 25; 10; 5; 1]);
0</
{{out}}
<pre>242
Line 1,277 ⟶ 1,614:
=={{header|Factor}}==
<
IN: rosetta.coins
Line 1,312 ⟶ 1,649:
: make-change ( cents coins -- ways )
members [ ] inv-sort-with ! Sort coins in descending order.
recursive-count ;</
From the listener:
Line 1,325 ⟶ 1,662:
One might make use of the rosetta-code.count-the-coins vocabulary as shown:
<syntaxhighlight lang="text">
IN: scratchpad [ 100000 { 1 5 10 25 50 100 } make-change . ] time
13398445413854501
Running time: 0.020869274 seconds
</syntaxhighlight>
For reference, the implementation is shown next.
<syntaxhighlight lang="text">
USING: arrays locals math math.ranges sequences sets sorting ;
IN: rosetta-code.count-the-coins
Line 1,352 ⟶ 1,689:
: make-change ( cents coins -- ways )
members [ ] inv-sort-with (make-change) ;
</syntaxhighlight>
Or one could implement the algorithm like described in http://www.cdn.geeksforgeeks.org/dynamic-programming-set-7-coin-change.
<
USE: math.ranges
Line 1,375 ⟶ 1,712:
13398445413854501
Running time: 0.029163549 seconds
</syntaxhighlight>
=={{header|FOCAL}}==
<syntaxhighlight lang="focal">01.10 S C(1)=1;S C(2)=5;S C(3)=10;S C(4)=25
01.20 F N=1,100;S T(N)=0
01.30 S T(0)=1
01.40 F M=1,4;F N=C(M),100;S T(N)=T(N)+T(N-C(M))
01.50 T %3,T(100),!
01.60 Q</syntaxhighlight>
{{out}}
<pre>= 242</pre>
=={{header|Forth}}==
<
: table create does> swap cells + @ ;
Line 1,393 ⟶ 1,740:
then then ;
100 5 count-change .</
=={{header|FreeBASIC}}==
Translation from "Dynamic Programming Solution: Python version" on this webside [http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/]
<
' compile with: fbc -s console
Line 1,462 ⟶ 1,809:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>
Line 1,472 ⟶ 1,819:
=={{header|FutureBasic}}==
<
void local fn Doit
long penny, nickel, dime, quarter, count = 0
NSLogSetTabInterval(30)
for penny = 0 to 100
for nickel = 0 to 20
for dime = 0 to 10
next dime
next nickel
next penny
NSLog(@"\n%ld ways to make a dollar",count)
end fn
fn DoIt
HandleEvents</syntaxhighlight>
Output:
<pre>0 pennies 0 nickels 0 dimes 4 quarters
0 pennies
0 pennies 0 nickels
0 pennies
......
65 pennies 5 nickels 1 dimes 0 quarters
65 pennies 7 nickels 0 dimes 0 quarters
70 pennies 0 nickels 3 dimes 0 quarters
70 pennies 1 nickels 0 dimes 1 quarters
242 ways to make a dollar</pre>
=={{header|Go}}==
{{trans|lisp}}
<
import "fmt"
Line 1,551 ⟶ 1,897:
}
panic(kindsOfCoins)
}</
Output:
<pre>
Line 1,557 ⟶ 1,903:
</pre>
Alternative algorithm, practical for the optional task.
<
import "fmt"
Line 1,575 ⟶ 1,921:
}
return ways[amount]
}</
Output:
<pre>
Line 1,584 ⟶ 1,930:
{{trans|Go}}
Intuitive Recursive Solution:
<
ccR = { BigInteger tot, List<BigInteger> coins ->
BigInteger n = coins.size()
Line 1,596 ⟶ 1,942:
ccR(tot - coins[0], coins)
}
}</
Fast Iterative Solution:
<
List<BigInteger> ways = [0g] * (tot+1)
ways[0] = 1g
Line 1,608 ⟶ 1,954:
}
ways[tot]
}</
Test:
<
[iterative: ccI, recursive: ccR].each { label, cc ->
print "${label} "
Line 1,624 ⟶ 1,970:
def ways = ccI(1000g * 100, [100g, 50g, 25g, 10g, 5g, 1g])
def elapsed = System.currentTimeMillis() - start
println ("answer: ${ways} elapsed: ${elapsed}ms")</
Output:
Line 1,636 ⟶ 1,982:
=={{header|Haskell}}==
Naive implementation:
<
count 0 _ = 1
count _ [] = 0
Line 1,645 ⟶ 1,991:
main :: IO ()
main = print (count 100 [1, 5, 10, 25])</
Much faster, probably harder to read, is to update results from bottom up:
<
count = foldr addCoin (1 : repeat 0)
where
Line 1,658 ⟶ 2,004:
main = do
print (count [25, 10, 5, 1] !! 100)
print (count [100, 50, 25, 10, 5, 1] !! 10000)</
Or equivalently, (reformulating slightly, and adding a further test):
<
count
Line 1,683 ⟶ 2,029:
, ([100, 50, 25, 10, 5, 1], 1000000)
]
</syntaxhighlight>
{{Out}}
<pre>242
Line 1,690 ⟶ 2,036:
=={{header|Icon}} and {{header|Unicon}}==
<
US_coins := [1, 5, 10, 25]
Line 1,708 ⟶ 2,054:
every (s := "[ ") ||:= !L || " "
return s || "]"
end</
This is a naive implementation and very slow.
{{improve|Icon|Needs a better algorithm.}}
<
local count
static S
Line 1,730 ⟶ 2,076:
return (amt ~= 0) | 1
}
end</
{{libheader|Icon Programming Library}}
Line 1,740 ⟶ 2,086:
Another one:
<syntaxhighlight lang="icon">
# coin.icn
# usage: coin value
Line 1,759 ⟶ 2,105:
write(" coins in ", count(coins, money), " different ways.")
end
</syntaxhighlight>
Output:
<pre>
Line 1,767 ⟶ 2,113:
=={{header|IS-BASIC}}==
<
110 LET MONEY=100
120 LET COUNT=0
Line 1,784 ⟶ 2,130:
270 NEXT
280 NEXT
290 PRINT COUNT;"different combinations found."</
=={{header|J}}==
Line 1,790 ⟶ 2,136:
In this draft intermediate results are a two column array. The first column is tallies -- the number of ways we have for reaching the total represented in the second column, which is unallocated value (which we will assume are pennies). We will have one row for each different in-range value which can be represented using only nickles (0, 5, 10, ... 95, 100).
<
count=: {.@] <@,. {:@] - [ * [ i.@>:@<.@%~ {:@]
init=: (1 ,. ,.)^:(0=#@$)
nsplits=: 0 { [: +/ [: (merge@:(count"1) init)/ }.@/:~@~.@,</
This implementation special cases the handling of pennies and assumes that the lowest coin value in the argument is 1. If I needed additional performance, I would next special case the handling of nickles/penny combinations...
Line 1,799 ⟶ 2,145:
Thus:
<
242</
And, on a 64 bit machine with sufficient memory:
<
13398445413854501</
Warning: the above version can miss one when the largest coin is equal to the total value.
Line 1,811 ⟶ 2,157:
For British viewers change from £10 using £10 £5 £2 £1 50p 20p 10p 5p 2p and 1p
<
length1 =: 4 : '1=#y'
f =: 4 : ',/ +/\ (-x) ]\ y'
Line 1,819 ⟶ 2,165:
NB. this is a foldLeft once initialised the intermediate right arguments are arrays
1000 f 500 f 200 f 100 f 50 f 20 f 10 f 5 f 2 f (1000 init 0)</
=={{header|Java}}==
{{trans|D}}
{{works with|Java|1.5+}}
<
import java.math.BigInteger;
Line 1,869 ⟶ 2,215:
}
}
}</
Output:
<pre>242
Line 1,887 ⟶ 2,233:
Efficient iterative algorithm (cleverly calculates number of combinations without permuting them)
<
'use strict';
var targetsLength = t + 1;
Line 1,905 ⟶ 2,251:
return t[targetsLength - 1];
}</
{{out}}
JavaScript hits integer limit for optional task
<
242</
===Recursive===
Line 1,916 ⟶ 2,262:
Inefficient recursive algorithm (naively calculates number of combinations by actually permuting them)
<
'use strict';
var operandsLength = o.length;
Line 1,940 ⟶ 2,286:
permutate(0, 0);
return solutions;
}</
{{Out}}
Too slow for optional task
<
242</
===Iterative again===
{{Trans|C#}}
<
coin = [1, 5, 10, 25]
var t = [1];
Line 1,957 ⟶ 2,303:
for (var ci = coin[i], a = ci; a <= amount; a++)
t[a] += t[a - ci]
document.write(t[amount])</
{{Out}}
<pre>242</pre>
Line 1,963 ⟶ 2,309:
=={{header|jq}}==
Currently jq uses IEEE 754 64-bit numbers. Large integers are approximated by floats, and therefore the answer that the following program provides for the optional task is only correct for the first 15 digits.
<
# denominations as input.
# The strategy is to record at total[n] the number of ways to make n cents.
Line 1,978 ⟶ 2,324:
end
end ) )
| .[target] ;</
'''Example''':
[1,5,10,25] | countcoins(100)
Line 1,986 ⟶ 2,332:
=={{header|Julia}}==
{{trans|Python}}
<
ways = zeros(Int128, amount + 1)
ways[1] = 1
Line 1,996 ⟶ 2,342:
@show changes(100, [1, 5, 10, 25])
@show changes(100000, [1, 5, 10, 25, 50, 100])</
{{out}}
Line 2,004 ⟶ 2,350:
=={{header|Kotlin}}==
{{trans|C#}}
<
fun countCoins(c: IntArray, m: Int, n: Int): Long {
Line 2,018 ⟶ 2,364:
println(countCoins(c, 4, 100))
println(countCoins(c, 6, 1000 * 100))
}</
{{out}}
Line 2,028 ⟶ 2,374:
=={{header|Lasso}}==
Inspired by the javascript iterative example for the same task
<
target::integer,
operands::array
Line 2,057 ⟶ 2,403:
cointcoins(100, array(1,5,10,25,))
'<br />'
cointcoins(100000, array(1, 5, 10, 25, 50, 100))</
Output:
<pre>242
Line 2,064 ⟶ 2,410:
=={{header|Lua}}==
Lua uses one-based indexes but table keys can be any value so you can define an element 0 just as easily as you can define an element "foo"...
<
local t = {}
for i = 1, amount do t[i] = 0 end
Line 2,075 ⟶ 2,421:
print(countSums(100, {1, 5, 10, 25}))
print(countSums(100000, {1, 5, 10, 25, 50, 100}))</
{{out}}
<pre>242
Line 2,083 ⟶ 2,429:
===Fast O(n*m)===
Works with decimals in table()
<syntaxhighlight lang="m2000 interpreter">
Module FindCoins {
Function count(c(), n) {
Line 2,098 ⟶ 2,444:
}
FindCoins
</syntaxhighlight>
{{out}}
<pre>
Line 2,107 ⟶ 2,453:
Using an inventory (a kind of vector) to save first search (but is slower than previous one)
<syntaxhighlight lang="m2000 interpreter">
Module CheckThisToo {
inventory c=" 0 0":=1@
Line 2,122 ⟶ 2,468:
}
CheckThisToo
</syntaxhighlight>
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
DIMENSION TAB(101)
THROUGH ZERO, FOR N = 1, 1, N.G.100
ZERO TAB(N) = 0
TAB(0) = 1
THROUGH STEP, FOR VALUES OF COIN = 1, 5, 10, 25
THROUGH STEP, FOR N = COIN, 1, N.G.100
STEP TAB(N) = TAB(N) + TAB(N - COIN)
VECTOR VALUES FMT = $I3*$
PRINT FORMAT FMT, TAB(100)
END OF PROGRAM</syntaxhighlight>
{{out}}
<pre>242</pre>
=={{header|Maple}}==
Line 2,128 ⟶ 2,492:
Straightforward implementation with power series. Not very efficient for large amounts. Note that in the following, all amounts are in '''cents'''.
<
coin:=unapply(sum(x^(p*n),n=0..infinity),p):
ways:=(amount,purse)->coeff(series(mul(coin(k),k in purse),x,amount+1),x,amount):
Line 2,142 ⟶ 2,506:
ways(100000,[1,5,10,25,50,100]);
# 13398445413854501</
A faster implementation.
<
local a,n,k;
a:=Array(1..amount);
Line 2,183 ⟶ 2,547:
ways2(100000000,[1,5,10,25,50,100]);
# 13333398333445333413833354500001</
Additionally, while it's not proved as is, we can see that the first values for an amount 10^k obey the following simple formula:
<
for k from 2 to 8 do lprint(P(10^k)) od:
Line 2,196 ⟶ 2,560:
1333983445341383545001
133339833445334138335450001
13333398333445333413833354500001</
The polynomial P(n) seems to give the correct number of ways iff n is a multiple of 100 (tested up to n=10000000), i.e. the number of ways for 100n is
<
=={{header|Mathematica}} / {{header|Wolfram Language}}==
{{trans|Go}}
<
Do[For[j = coin, j <= amount, j++,
If[ j - coin == 0,
Line 2,211 ⟶ 2,575:
]]
, {coin, coinlist}];
ways[[amount]])</
Example usage:
<pre>CountCoins[100, {25, 10, 5}]
Line 2,220 ⟶ 2,584:
=={{header|MATLAB}} / {{header|Octave}}==
<syntaxhighlight lang="matlab">
%% Count_The_Coins
clear;close all;clc;
Line 2,251 ⟶ 2,615:
end % End for
toc
</syntaxhighlight>
Example Output:
<pre>Main Challenge: 242
Line 2,258 ⟶ 2,622:
=={{header|Mercury}}==
<
:- interface.
:- import_module int, io.
Line 2,305 ⟶ 2,669:
show([P|T], !IO) :-
io.write(P, !IO), io.nl(!IO),
show(T, !IO).</
=={{header|Nim}}==
{{trans|Python}}
<
var ways = @[1]
ways.setLen(amount+1)
Line 2,318 ⟶ 2,682:
echo changes(100, [1, 5, 10, 25])
echo changes(100000, [1, 5, 10, 25, 50, 100])</
Output:
<pre>242
Line 2,327 ⟶ 2,691:
Translation of the D minimal version:
<
let ways = Array.make (amount + 1) 0L in
ways.(0) <- 1L;
Line 2,340 ⟶ 2,704:
Printf.printf "%Ld\n" (changes 1_00 [25; 10; 5; 1]);
Printf.printf "%Ld\n" (changes 1000_00 [100; 50; 25; 10; 5; 1]);
;;</
Output:
Line 2,349 ⟶ 2,713:
=={{header|PARI/GP}}==
<
ways(v,n)=polcoeff(coins(v)+O('x^(n+1)),n);
ways([1,5,10,25],100)
ways([1,5,10,25,50,100],100000)</
Output:
<pre>%1 = 242
%2 = 13398445413854501</pre>
=={{header|Pascal}}==
<syntaxhighlight lang="Pascal">
program countTheCoins;
{$mode objfpc}{$H+}
var
count, quarter, dime, nickel, penny: integer;
begin
count := 0;
for penny := 0 to 100 do
for nickel := 0 to 20 do
for dime := 0 to 10 do
for quarter := 0 to 4 do
if (penny + 5 * nickel + 10 * dime + 25 * quarter = 100) then
begin
writeln(penny, ' pennies ', nickel, ' nickels ', dime, ' dimes ', quarter, ' quarters');
count := count + 1;
end;
writeln('The number of ways to make change for a dollar is: ', count); // 242 ways to make change for a dollar
end.
</syntaxhighlight>
Output:
<pre>
0 pennies 0 nickels 0 dimes 4 quarters
0 pennies 0 nickels 5 dimes 2 quarters
0 pennies 0 nickels 10 dimes 0 quarters
0 pennies 1 nickels 2 dimes 3 quarters
......
85 pennies 1 nickels 1 dimes 0 quarters
85 pennies 3 nickels 0 dimes 0 quarters
90 pennies 0 nickels 1 dimes 0 quarters
90 pennies 2 nickels 0 dimes 0 quarters
95 pennies 1 nickels 0 dimes 0 quarters
100 pennies 0 nickels 0 dimes 0 quarters
The number of ways to make change for a dollar is: 242
</pre>
=={{header|Perl}}==
<
use Memoize;
Line 2,380 ⟶ 2,787:
say 'Ways to change $ 1000 with addition of less common coins: ',
cc_optimized( 1000 * 100, 1, 5, 10, 25, 50, 100 );
</syntaxhighlight>
{{out}}
Ways to change $ 1 with common coins: 242
Line 2,387 ⟶ 2,794:
=={{header|Phix}}==
Very fast, from http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change
<!--<syntaxhighlight lang="phix">-->
<span style="color: #008080;">function</span> <span style="color: #000000;">coin_count</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">amount</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">to</span> <span style="color: #000000;">amount</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<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: #008080;">return</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</syntaxhighlight>-->
An attempt to explain this algorithm further seems worthwhile:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">coin_count</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">amount</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- start with 1 known way to achieve 0 (being no coins)
-- (nb: s[1] holds the solution for 0, s[n+1] for n)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000080;font-style:italic;">-- then for every coin that we can use, increase number of
-- solutions by that previously found for the remainder.</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- this inner loop is essentially behaving as if we had
--
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">to</span> <span style="color: #000000;">amount</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<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: #008080;">return</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">-- The key to understanding the above is to try a dry run of this:</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;">"%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- (prints 1)
-- You'll need 4 2p coins, 3 3p coins, and 5 spaces marked 1..5.
--
--
--
-- Add previously found solns: +0 +0 +1 +0 +1 [2]
-- [1]
--
--
-- fact is central to understanding why this works. [3]
-- [2]
--
--
--
-- albeit by adding that as just added to the precessor.
-- [3] since we add
-- not count 2p+3p and 3p+2p as two solutions.
--For N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.</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;">"%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span><span style="color: #000000;">4</span><span style="color: #0000FF;">))</span>
<span style="color: #000080;font-style:italic;">--For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.</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;">"%d\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span><span style="color: #000000;">10</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;">"%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">1_00</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;">"%,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">1000_00</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,457 ⟶ 2,868:
9,007,199,254,740,992 -- max precision (53 bits) of a 64-bit float
</pre>
=={{header|Picat}}==
Using dynamic programming with tabling.
<syntaxhighlight lang="picat">go =>
Problems = [[ 1*100, [25,10,5,1]], % 1 dollar
[ 100*100, [100,50,25,10,5,1]], % 100 dollars
[ 1_000*100, [100,50,25,10,5,1]], % 1000 dollars
[ 10_000*100, [100,50,25,10,5,1]], % 10000 dollars
[100_000*100, [100,50,25,10,5,1]] % 100000 dollars
],
foreach([N,L] in Problems)
initialize_table, % clear the tabling from previous run
println([n=N,l=L]),
time(println(num_sols=coins(L,N,1)))
end.
table
coins(Coins, Money, M) = Sum =>
Sum1 = 0,
Len = Coins.length,
if M == Len then
Sum1 := 1,
else
foreach(I in M..Len)
if Money - Coins[I] == 0 then
Sum1 := Sum1 + 1
end,
if Money - Coins[I] > 0 then
Sum1 := Sum1 + coins(Coins, Money-Coins[I], I)
end,
end
end,
Sum = Sum1.</syntaxhighlight>
{{Output}}
<pre>[n = 100,l = [25,10,5,1]]
num_sols = 242
CPU time 0.0 seconds.
[n = 10000,l = [100,50,25,10,5,1]]
num_sols = 139946140451
CPU time 0.005 seconds.
[n = 100000,l = [100,50,25,10,5,1]]
num_sols = 13398445413854501
CPU time 0.046 seconds.
[n = 1000000,l = [100,50,25,10,5,1]]
num_sols = 1333983445341383545001
CPU time 0.496 seconds.
[n = 10000000,l = [100,50,25,10,5,1]]
num_sols = 133339833445334138335450001
CPU time 5.402 seconds.</pre>
=={{header|PicoLisp}}==
{{trans|C}}
<
(let (Buf (mapcar '((N) (cons 1 (need (dec N) 0))) Coins) Prev)
(do Sum
Line 2,467 ⟶ 2,938:
(inc (rot L) Prev)
(setq Prev (car L)) ) )
Prev ) )</
Test:
<
(println (coins 100 (cddr Coins)))
(println (coins (* 1000 100) Coins))
(println (coins (* 10000 100) Coins))
(println (coins (* 100000 100) Coins))
(prinl) )</
Output:
<pre>242
Line 2,489 ⟶ 2,960:
Basic version using brute force and constraint programming, the bonus version will work but takes a long time so skipped it.
<
% Basic, Q = Quarter, D = Dime, N = Nickel, P = Penny
Line 2,498 ⟶ 2,969:
coins_for(T) :-
coins(Q,D,N,P,T),
maplist(indomain, [Q,D,N,P]).</
{{out}}
<pre>
Line 2,508 ⟶ 2,979:
===Simple version===
{{trans|Go}}
<
ways = [0] * (amount + 1)
ways[0] = 1
Line 2,517 ⟶ 2,988:
print changes(100, [1, 5, 10, 25])
print changes(100000, [1, 5, 10, 25, 50, 100])</
Output:
<pre>242
Line 2,523 ⟶ 2,994:
===Fast version===
{{trans|C}}
<
import psyco
psyco.full()
Line 2,560 ⟶ 3,031:
print count_changes(10000000, coins), "\n"
main()</
Output:
<pre>242
Line 2,571 ⟶ 3,042:
99341140660285639188927260001
992198221207406412424859964272600001</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ stack ] is lim ( --> s )
[ swap dup 1+ lim put
1 0 rot of join
swap witheach
[ 0 over of
swap negate temp put
lim share times
[ over i^ peek
over temp share peek
+ join ]
temp take negate split
nip nip ]
-1 peek
lim release ] is makechange ( n [ --> n )
say "With US coins." cr
100 ' [ 1 5 10 25 ] makechange echo cr
100000 ' [ 1 5 10 25 50 100 ] makechange echo cr
cr
say "With EU coins." cr
100 ' [ 1 2 5 10 20 50 100 200 ] makechange echo cr
100000 ' [ 1 2 5 10 20 50 100 200 ] makechange echo cr</syntaxhighlight>
{{out}}
<pre>With US coins.
242
13398445413854501
With EU coins.
4563
10056050940818192726001
</pre>
=={{header|Racket}}==
This is the basic recursive way:
<
(define (ways-to-make-change cents coins)
(cond ((null? coins) 0)
Line 2,584 ⟶ 3,092:
(ways-to-make-change 100 '(25 10 5 1)) ; -> 242
</syntaxhighlight>
This works for the small numbers, but the optional task is just too slow with this solution, so with little change to the code we can use memoization:
<
(define memos (make-hash))
Line 2,610 ⟶ 3,118:
cpu time: 20223 real time: 20673 gc time: 10233
99341140660285639188927260001 |#</
=={{header|Raku}}==
Line 2,617 ⟶ 3,125:
{{trans|Ruby}}
<syntaxhighlight lang="raku"
sub change-r($amount, @coins) {
my @cache = [1 xx @coins], |([] xx $amount);
Line 2,650 ⟶ 3,158:
say "\nRecursive:";
say change-r 1_00, [1,5,10,25];
say change-r 1000_00, [1,5,10,25,50,100];</
{{out}}
<pre>Iterative:
Line 2,671 ⟶ 3,179:
The amount can be specified in cents (as a number), or in dollars (as for instance, $1000).
<
numeric digits 20 /*be able to handle large amounts of $.*/
parse arg N $ /*obtain optional arguments from the CL*/
Line 2,702 ⟶ 3,210:
if a==$.k then return f+1 /*handle this special case of A=a coin.*/
if a <$.k then return f /* " " " " " A<a coin.*/
return f+MKchg(a-$.k,k) /*use diminished amount ($) for change.*/</
{{out|output|text= when using the default input:}}
<pre>
Line 2,717 ⟶ 3,225:
===with memoization===
This REXX version is more than a couple of orders of magnitude faster than the 1<sup>st</sup> version when using larger amounts.
<
numeric digits 20 /*be able to handle large amounts of $.*/
parse arg N $ /*obtain optional arguments from the CL*/
Line 2,749 ⟶ 3,257:
if a==$.k then do; !.a.k= f+1; return !.a.k; end /*handle this special case.*/
if a <$.k then do; !.a.k= f ; return f ; end /* " " " " */
!.a.k= f + MKchg(a-$.k, k); return !.a.k /*compute, define, return. */</
{{out|output|text= when using the following input for the optional test case: <tt> $1000 1 5 10 25 50 100 </tt>}}
<pre>
Line 2,758 ⟶ 3,266:
===with error checking===
This REXX version is identical to the previous REXX version, but has error checking for the amount and the coins specified.
<
numeric digits 20 /*be able to handle large amounts of $.*/
parse arg N $ /*obtain optional arguments from the CL*/
Line 2,811 ⟶ 3,319:
if a==$.k then do; !.a.k= f+1; return !.a.k; end /*handle this special case.*/
if a <$.k then do; !.a.k= f ; return f ; end /* " " " " */
!.a.k= f + MKchg(a-$.k, k); return !.a.k /*compute, define, return. */</
{{out|output|text= is the same as the previous REXX version.}}<br><br>
=={{header|Ring}}==
<
penny = 1
nickel = 1
Line 2,835 ⟶ 3,343:
next
see count + " ways to make a dollar" + nl
</syntaxhighlight>
Output:
<pre>
Line 2,849 ⟶ 3,357:
242 ways to make a dollar
</pre>
=={{header|RPL}}==
'''Dynamic programming (space optimized)'''
Source: [https://www.geeksforgeeks.org/coin-change-dp-7/ GeeksforGeeks website]
« → coins sum
« sum 1 + 1 →LIST 0 CON <span style="color:grey">@ dp[ii] will be storing the # of solutions for ii-1</span>
1 1 PUT <span style="color:grey">@ base case</span>
1 coins SIZE '''FOR''' ii
coins ii GET SWAP
'''IF''' OVER sum ≤ '''THEN'''
<span style="color:grey">@ Pick all coins one by one and update dp[] values </span>
<span style="color:grey">@ after the index greater than or equal to the value of the picked coin </span>
OVER 1 + sum 1 + '''FOR''' j
DUP j GET
OVER j 5 PICK - GET +
j SWAP PUT
'''NEXT'''
'''END''' SWAP DROP
'''NEXT'''
DUP SIZE GET
» » '<span style="color:blue">COUNT</span>' STO
{ 1 5 10 25 } 100 <span style="color:blue">COUNT</span>
{{out}}
<pre>
1: 242
</pre>
Line 2,856 ⟶ 3,392:
'''Recursive, with caching'''
<
@cache = Array.new(amount+1){|i| Array.new(coins.size, i.zero? ? 1 : nil)}
@coins = coins
Line 2,873 ⟶ 3,409:
p make_change( 1_00, [1,5,10,25])
p make_change(1000_00, [1,5,10,25,50,100])</
outputs
Line 2,881 ⟶ 3,417:
'''Iterative'''
<
n, m = amount, coins.size
table = Array.new(n+1){|i| Array.new(m, i.zero? ? 1 : nil)}
Line 2,894 ⟶ 3,430:
p make_change2( 1_00, [1,5,10,25])
p make_change2(1000_00, [1,5,10,25,50,100])</
outputs
<pre>242
Line 2,900 ⟶ 3,436:
=={{header|Run BASIC}}==
<
for nickel = 0 to 20
for dime = 0 to 10
Line 2,912 ⟶ 3,448:
next nickel
next penny
print count;" ways to make a buck"</
<pre>0 pennies 0 nickels 0 dimes 4 quarters
0 pennies 0 nickels 5 dimes 2 quarters
Line 2,926 ⟶ 3,462:
=={{header|Rust}}==
<
let size = cents + 1;
let mut ways = vec![0; size];
Line 2,941 ⟶ 3,477:
println!("{}", make_change(&[1,5,10,25], 100));
println!("{}", make_change(&[1,5,10,25,50,100], 100_000));
}</
{{output}}
<pre>242
Line 2,948 ⟶ 3,484:
=={{header|SAS}}==
Generate the solutions using CLP solver in SAS/OR:
<
proc optmodel;
/* declare set and names of coins */
Line 2,968 ⟶ 3,504:
/* print all solutions */
proc print data=sols;
run;</
Output:
Line 2,987 ⟶ 3,523:
=={{header|Scala}}==
<
val ways = Array.fill(amount + 1)(0)
ways(0) = 1
Line 2,998 ⟶ 3,534:
countChange (15, List(1, 5, 10, 25))
</syntaxhighlight>
Output:
<pre>res0: Int = 6
Line 3,004 ⟶ 3,540:
Recursive implementation:
<
if (target == 0) 1
else if (coins.isEmpty || target < 0) 0
Line 3,012 ⟶ 3,548:
count(100, List(25, 10, 5, 1))
</syntaxhighlight>
=={{header|Scheme}}==
A simple recursive implementation:
<
(lambda (x coins)
(cond
Line 3,024 ⟶ 3,560:
[else (+ (ways-to-make-change x (cdr coins)) (ways-to-make-change (- x (car coins)) coins))])))
(ways-to-make-change 100)</
Output:
<pre>242</pre>
Line 3,032 ⟶ 3,568:
===Straightforward solution===
Fairly simple solution for the task. Expanding it to the optional task is not recommend, for Scilab will spend a lot of time processing the nested <code>for</code> loops.
<syntaxhighlight lang="text">amount=100;
coins=[25 10 5 1];
n_coins=zeros(coins);
Line 3,053 ⟶ 3,589:
end
disp(ways);</
{{out}}
Line 3,062 ⟶ 3,598:
{{trans|Python}}
<syntaxhighlight lang="text">function varargout=changes(amount, coins)
ways = zeros(1,amount + 2);
ways(1) = 1;
Line 3,076 ⟶ 3,612:
a=changes(100, [1, 5, 10, 25]);
b=changes(100000, [1, 5, 10, 25, 50, 100]);
mprintf("%.0f, %.0f", a, b);</
{{out}}
Line 3,083 ⟶ 3,619:
=={{header|Seed7}}==
<
include "bigint.s7i";
Line 3,123 ⟶ 3,659:
writeln(changeCount( 100000, euCoins));
writeln(changeCount(1000000, euCoins));
end func;</
Output:
Line 3,133 ⟶ 3,669:
99341140660285639188927260001
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program count_the_coins;
print(count([1, 5, 10, 25], 100));
print(count([1, 5, 10, 25, 50, 100], 1000 * 100));
proc count(coins, n);
tab := {[0, 1]};
loop for coin in coins do
loop for i in [coin..n] do
tab(i) +:= tab(i - coin) ? 0;
end loop;
end loop;
return tab(n);
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>242
13398445413854501</pre>
=={{header|Sidef}}==
{{trans|Perl}}
<
func cc({ .is_neg }, *_) { 0 }
func cc({ .is_zero }, *_) { 1 }
Line 3,152 ⟶ 3,707:
var y = cc_optimized(1000 * 100, 1, 5, 10, 25, 50, 100);
say "Ways to change $1000 with addition of less common coins: #{y}";</
{{out}}
<pre>
Line 3,162 ⟶ 3,717:
{{trans|Python}}
{{libheader|Attaswift BigInt}}
<
func countCoins(amountCents cents: Int, coins: [Int]) -> BigInt {
Line 3,205 ⟶ 3,760:
print(countCoins(amountCents: 10000000, coins: set))
print()
}</
{{out}}
Line 3,220 ⟶ 3,775:
=={{header|Tailspin}}==
{{trans|Rust}}
<
templates makeChange&{coins:}
def paid: $;
Line 3,235 ⟶ 3,790:
100000 -> makeChange&{coins: [1,5,10,25,50,100]} -> '$; ways to change 1000 dollars with all coins
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 3,244 ⟶ 3,799:
=={{header|Tcl}}==
{{trans|Ruby}}
<
proc makeChange {amount coins} {
Line 3,265 ⟶ 3,820:
# Making change with the EU coin set:
puts [makeChange 100 {1 2 5 10 20 50 100 200}]
puts [makeChange 100000 {1 2 5 10 20 50 100 200}]</
Output:
<pre>
Line 3,276 ⟶ 3,831:
=={{header|uBasic/4tH}}==
{{trans|Run BASIC}}
<syntaxhighlight lang="text">c = 0
for p = 0 to 100
for n = 0 to 20
Line 3,289 ⟶ 3,844:
next n
next p
print c;" ways to make a buck"</
{{out}}
<pre>0 pennies 0 nickels 0 dimes 4 quarters
Line 3,306 ⟶ 3,861:
{{trans|Common Lisp}}
{{works with|bash}}
<
local -i amount=$1 coin j
local ways=(1)
Line 3,318 ⟶ 3,873:
}
count_change 100 25 10 5 1
count_change 100000 100 50 25 10 5 1</
{{works with|ksh|93}}
<
typeset -i amount=$1 coin j
typeset ways
Line 3,334 ⟶ 3,889:
}
count_change 100 25 10 5 1
count_change 100000 100 50 25 10 5 1</
{{works with|ksh|88}}
<
typeset -i amount=$1 coin j
typeset ways
Line 3,352 ⟶ 3,907:
}
count_change 100 25 10 5 1
# (optional task exceeds a subscript limit in ksh88)</
And just for fun, here's one that works even with the original V7 shell:
{{works with|sh|v7}}
<
set ${1-100} 25 10 5 1
fi
Line 3,371 ⟶ 3,926:
done
done
eval "echo \$ways_$amount"</
{{Out}}
Line 3,378 ⟶ 3,933:
=={{header|VBA}}==
{{trans|Phix}}<
'sequence s = Repeat(0, amount + 1)
Dim s As Variant
Line 3,399 ⟶ 3,954:
us_coins = [{100,50,25, 10, 5, 1}]
Debug.Print coin_count(us_coins, 100000)
End Sub</
<pre> 242
13398445413854501 </pre>
Line 3,405 ⟶ 3,960:
=={{header|VBScript}}==
{{trans|C#}}
<syntaxhighlight lang="vb">
Function count(coins,m,n)
ReDim table(n+1)
Line 3,426 ⟶ 3,981:
n = 100
WScript.StdOut.WriteLine count(arr,m,n)
</syntaxhighlight>
{{Out}}
Line 3,436 ⟶ 3,991:
{{trans|VBA}}
{{works with|Visual Basic|6}}
<
'----------------------------------------------------------------------
Private Function coin_count(coins As Variant, amount As Long) As Variant
Line 3,464 ⟶ 4,019:
Debug.Print coin_count(us_coins, 100000)
End Sub</
{{out}}
<pre> 242
13398445413854501</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="go">
fn main() {
amount := 100
println("amount: $amount; ways to make change: ${count_change(amount)}")
}
fn count_change(amount int) i64 {
if amount.str().count('0') > 4 {exit(-1)} // can be too slow
return cc(amount, 4)
}
fn cc(amount int, kinds_of_coins int) i64 {
if amount == 0 {return 1}
else if amount < 0 || kinds_of_coins == 0 {return 0}
return cc(amount, kinds_of_coins-1) +
cc(amount - first_denomination(kinds_of_coins), kinds_of_coins)
}
fn first_denomination(kinds_of_coins int) int {
match kinds_of_coins {
1 {return 1}
2 {return 5}
3 {return 10}
4 {return 25}
else {exit(-2)}
}
return kinds_of_coins
}
</syntaxhighlight>
Output:
<pre>
amount, ways to make change: 100 242
</pre>
Alternate:
<syntaxhighlight lang="go">
fn main() {
amount := 100
coins := [25, 10, 5, 1]
println("amount: $amount; ways to make change: ${count(coins, amount)}")
}
fn count(coins []int, amount int) int {
mut ways := []int{len: amount + 1}
ways[0] = 1
for coin in coins {
for idx := coin; idx <= amount; idx++ {
ways[idx] += ways[idx - coin]
}
}
return ways[amount]
}
</syntaxhighlight>
Output:
<pre>
amount: 100; ways to make change: 242
</pre>
=={{header|Wren}}==
Line 3,473 ⟶ 4,087:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var countCoins = Fn.new { |c, m, n|
Line 3,488 ⟶ 4,102:
var c = [1, 5, 10, 25, 50, 100]
Fmt.print("Ways to make change for $$1 using 4 coins = $,i", countCoins.call(c, 4, 100))
Fmt.print("Ways to make change for $$1,000 using 6 coins = $,i", countCoins.call(c, 6, 1000 * 100))</
{{out}}
Line 3,498 ⟶ 4,112:
=={{header|zkl}}==
{{trans|Scheme}}
<
if(not coins) return(0);
if(x<0) return(0);
Line 3,504 ⟶ 4,118:
ways_to_make_change(x, coins[1,*]) + ways_to_make_change(x - coins[0], coins)
}
ways_to_make_change(100).println();</
{{out}}
<pre>242</pre>
Line 3,510 ⟶ 4,124:
{{trans|Ruby}}
<
n, m := amount, coins.len();
table := (0).pump(n+1,List, (0).pump(m,List().write,1).copy);
Line 3,521 ⟶ 4,135:
println(make_change2( 100, T(1,5,10,25)));
make_change2(0d1000_00, T(1,5,10,25,50,100)) : "%,d".fmt(_).println();</
{{out}}
<pre>
Line 3,531 ⟶ 4,145:
{{trans|AWK}}
Test with emulator at full speed for reasonable performance.
<
20 GO SUB 1000
30 STOP
Line 3,550 ⟶ 4,164:
1140 NEXT p
1150 PRINT count
1160 RETURN </
|