Count the coins: Difference between revisions

m
syntax highlighting fixup automation
(Applesoft BASIC)
m (syntax highlighting fixup automation)
Line 34:
=={{header|11l}}==
{{trans|Python}}
<langsyntaxhighlight lang="11l">F changes(amount, coins)
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]))</langsyntaxhighlight>
 
Output:
Line 53:
=={{header|360 Assembly}}==
{{trans|AWK}}
<langsyntaxhighlight lang="360asm">* count the coins 04/09/2015
COINS CSECT
USING COINS,R12
Line 111:
PG DS CL12
YREGS
END COINS</langsyntaxhighlight>
{{out}}
<pre>
Line 121:
{{Works with|gnat/gcc}}
 
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO;
 
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;</langsyntaxhighlight>
 
Output:<pre> 242
Line 160:
{{works with|ALGOL 68G|Any - tested with release 2.4.1}}
{{trans|Haskell}}
<syntaxhighlight lang="algol68">
<lang Algol68>
#
Rosetta Code "Count the coins"
Line 192:
print((ways to make change(denoms, 100), newline))
END
</syntaxhighlight>
</lang>
Output:<pre>
+242
Line 198:
{{works with|ALGOL 68G|Any - tested with release 2.8.4}}
{{trans|Haskell}}
<syntaxhighlight lang="algol68">
<lang Algol68>
#
Rosetta Code "Count the coins"
Line 231:
print((ways to make change((1, 5, 10, 25, 50, 100), 100000), newline))
END
</syntaxhighlight>
</lang>
Output:<pre>
+242
Line 242:
{{trans|Phix}}
 
<langsyntaxhighlight lang="applescript">-- All input values must be integers and multiples of the same monetary unit.
on countCoins(amount, denominations)
-- Potentially long list of counters, initialised with 1 (result for amount 0) and 'amount' zeros.
Line 271:
set c1 to countCoins(100, {25, 10, 5, 1})
set c2 to countCoins(1000 * 100, {100, 50, 25, 10, 5, 1})
return {c1, c2}</langsyntaxhighlight>
 
{{output}}
<syntaxhighlight lang ="applescript">{242, 13398445413854501}</langsyntaxhighlight>
 
=={{header|Applesoft BASIC}}==
{{trans|Commodore BASIC}}
<langsyntaxhighlight 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;</langsyntaxhighlight>
=={{header|Arturo}}==
<langsyntaxhighlight lang="rebol">changes: function [amount coins][
ways: map 0..amount+1 [x]-> 0
ways\0: 1
Line 293:
print changes 100 [1 5 10 25]
print changes 100000 [1 5 10 25 50 100]</langsyntaxhighlight>
 
=={{header|AutoHotkey}}==
{{trans|Go}}
{{Works with|AutoHotkey_L}}
<langsyntaxhighlight AHKlang="ahk">countChange(amount){
return cc(amount, 4)
}
Line 314:
return [1, 5, 10, 25][kindsOfCoins]
}
MsgBox % countChange(100)</langsyntaxhighlight>
 
=={{header|AWK}}==
Line 320:
Iterative implementation, derived from Run BASIC:
 
<langsyntaxhighlight lang="awk">#!/usr/bin/awk -f
 
BEGIN {
Line 346:
return count;
}
</syntaxhighlight>
</lang>
 
Run time:
Line 358:
Recursive implementation (derived from Scheme example):
 
<langsyntaxhighlight lang="awk">#!/usr/bin/awk -f
 
BEGIN {
Line 385:
return koins[1]
}
</syntaxhighlight>
</lang>
 
Run time:
Line 399:
=={{header|BBC BASIC}}==
Non-recursive solution:
<langsyntaxhighlight lang="bbcbasic"> DIM uscoins%(3)
uscoins%() = 1, 5, 10, 25
PRINT FNchange(100, uscoins%()) " ways of making $1"
Line 435:
NEXT
= table(P%-1)
</syntaxhighlight>
</lang>
Output (BBC BASIC does not have large enough integers for the optional task):
<pre> 242 ways of making $1
Line 444:
=={{header|C}}==
Using some crude 128-bit integer type.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
Line 543:
 
return 0;
}</langsyntaxhighlight>output (only the first two lines are required by task):<syntaxhighlight lang="text">242
13398445413854501
1333983445341383545001
Line 551:
10056050940818192726001
99341140660285639188927260001
992198221207406412424859964272600001</langsyntaxhighlight>
 
=={{header|C sharp|C#}}==
<langsyntaxhighlight lang="csharp">
// Adapted from http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
class Program
Line 576:
}
}
</syntaxhighlight>
</lang>
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">
#include <iostream>
#include <stack>
Line 613:
std::cout << ways << std::endl;
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 619:
 
=={{header|Clojure}}==
<langsyntaxhighlight lang="lisp">(def denomination-kind [1 5 10 25])
 
(defn- cc [amount denominations]
Line 632:
(cc amount denominations))
 
(count-change 15 denomination-kind) ; = 6 </langsyntaxhighlight>
 
=={{header|COBOL}}==
{{trans|C#}}
<langsyntaxhighlight lang="cobol">
identification division.
program-id. CountCoins.
Line 668:
end-perform
.
</syntaxhighlight>
</lang>
{{out}}
<pre>242</pre>
Line 676:
{{trans|Python}}
 
<langsyntaxhighlight lang="coco">changes = (amount, coins) ->
ways = [1].concat [0] * amount
for coin of coins
Line 683:
ways[amount]
console.log changes 100, [1 5 10 25]</langsyntaxhighlight>
 
=={{header|Commodore BASIC}}==
Line 698:
 
 
<langsyntaxhighlight lang="gwbasic">5 m=100:rem money = $1.00 or 100 pennies.
10 print chr$(147);chr$(14);"This program will calculate the number"
11 print "of combinations of 'change' that can be"
Line 724:
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</langsyntaxhighlight>
 
'''Example 2:''' Commodore 64 with Screen Blanking
Line 732:
Enabling screen blanking (and therefore not printing each result) results in a total time of 1:44.
 
<langsyntaxhighlight lang="gwbasic">145 if not yn then poke 53265,peek(53265) and 239
245 en$=ti$:if not yn then poke 53265,peek(53265) or 16</langsyntaxhighlight>
 
'''Example 3:''' Commodore 128 with VIC-II blanking, 2MHz fast mode.
Line 739:
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:
 
<langsyntaxhighlight lang="gwbasic">145 if not yn then fast
245 en$=ti$:if not yn then slow</langsyntaxhighlight>
 
=={{header|Common Lisp}}==
===Recursive Version With Cache===
<langsyntaxhighlight lang="lisp">(defun count-change (amount coins
&optional
(length (1- (length coins)))
Line 761:
(print (count-change 100 '(25 10 5 1))) ; = 242
(print (count-change 100000 '(100 50 25 10 5 1))) ; = 13398445413854501
(terpri)</langsyntaxhighlight>
 
===Iterative Version===
<langsyntaxhighlight lang="lisp">(defun count-change (amount coins &aux (ways (make-array (1+ amount) :initial-element 0)))
(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))</langsyntaxhighlight>
 
=={{header|D}}==
===Basic Version===
{{trans|Go}}
<langsyntaxhighlight lang="d">import std.stdio, std.bigint;
 
auto changes(int amount, int[] coins) {
Line 788:
changes( 1_00, [25, 10, 5, 1]).writeln;
changes(1000_00, [100, 50, 25, 10, 5, 1]).writeln;
}</langsyntaxhighlight>
{{out}}
<pre>242
Line 795:
===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.
<langsyntaxhighlight lang="d">import std.stdio, core.checkedint;
 
auto changes(int amount, int[] coins, ref bool overflow) {
Line 815:
if (overflow)
"Overflow".puts;
}</langsyntaxhighlight>
The output is the same.
 
===Faster Version===
{{trans|C}}
<langsyntaxhighlight lang="d">import std.stdio, std.bigint;
 
BigInt countChanges(in int amount, in int[] coins) pure /*nothrow*/ {
Line 861:
writeln;
}
}</langsyntaxhighlight>
{{out}}
<pre>242
Line 876:
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}}
<langsyntaxhighlight lang="d">import std.stdio, std.bigint, std.algorithm, std.conv, std.functional;
 
struct Ucent { /// Simplified 128-bit integer (like ucent).
Line 935:
writeln;
}
}</langsyntaxhighlight>
 
===Printing Version===
This version prints all the solutions (so it can be used on the smaller input):
<langsyntaxhighlight lang="d">import std.stdio, std.conv, std.string, std.algorithm, std.range;
 
void printChange(in uint tot, in uint[] coins)
Line 970:
void main() {
printChange(1_00, [1, 5, 10, 25]);
}</langsyntaxhighlight>
{{out}}
<pre>1:5 5:1 10:4 25:2
Line 1,000:
=={{header|Dart}}==
Simple recursive version plus cached version using a map.
<syntaxhighlight lang="dart">
<lang Dart>
var cache = new Map();
 
Line 1,056:
return(count);
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,065:
=={{header|Delphi}}==
{{Trans|C#}}
<syntaxhighlight lang="delphi">
<lang Delphi>
program Count_the_coins;
 
Line 1,095:
Readln;
end.
</syntaxhighlight>
</lang>
=={{header|Dyalect}}==
 
<langsyntaxhighlight lang="dyalect">func countCoins(coins, n) {
var xs = Array.Empty(n + 1, 0)
xs[0] = 1
Line 1,112:
 
var coins = [1, 5, 10, 25]
print(countCoins(coins, 100))</langsyntaxhighlight>
 
{{out}}
Line 1,120:
=={{header|EchoLisp}}==
Recursive solution using memoization, adapted from CommonLisp and Racket.
<langsyntaxhighlight lang="scheme">
(lib 'compile) ;; for (compile)
(lib 'bigint) ;; integer results > 32 bits
Line 1,141:
 
(compile 'ways) ;; speed-up things
</syntaxhighlight>
</lang>
{{out}}
<langsyntaxhighlight lang="scheme">
(define change '(25 10 5 1))
(define c-1 (list-tail change -1)) ;; pointer to (1)
Line 1,176:
→ 13398445413854501
 
</syntaxhighlight>
</lang>
 
=={{header|EDSAC order code}}==
Line 1,182:
 
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.
<langsyntaxhighlight lang="edsac">
["Count the coins" problem for Rosetta Code.]
[EDSAC program, Initial Orders 2.]
Line 1,337:
E21Z [define entry point]
PF [enter with acc = 0]
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,347:
=={{header|Elixir}}==
Recursive Dynamic Programming solution in Elixir
<langsyntaxhighlight Elixirlang="elixir">defmodule Coins do
def find(coins,lim) do
vals = Map.new(0..lim,&{&1,0}) |> Map.put(0,1)
Line 1,370:
 
Coins.find([1,5,10,25],100)
Coins.find([1,5,10,25,50,100],100_000)</langsyntaxhighlight>
 
{{out}}
Line 1,379:
 
=={{header|Erlang}}==
<langsyntaxhighlight lang="erlang">
-module(coins).
-compile(export_all).
Line 1,411:
A2 = 100000, C2 = [100, 50, 25, 10, 5, 1],
print(A2,C2).
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,422:
{{trans|OCaml}}
<p>Forward iteration, which can also be seen in Scala.</p>
<langsyntaxhighlight lang="fsharp">let changes amount coins =
let ways = Array.zeroCreate (amount + 1)
ways.[0] <- 1L
Line 1,434:
printfn "%d" (changes 100 [25; 10; 5; 1]);
printfn "%d" (changes 100000 [100; 50; 25; 10; 5; 1]);
0</langsyntaxhighlight>
{{out}}
<pre>242
Line 1,440:
 
=={{header|Factor}}==
<langsyntaxhighlight lang="factor">USING: combinators kernel locals math math.ranges sequences sets sorting ;
IN: rosetta.coins
 
Line 1,475:
: make-change ( cents coins -- ways )
members [ ] inv-sort-with ! Sort coins in descending order.
recursive-count ;</langsyntaxhighlight>
 
From the listener:
Line 1,488:
 
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>
</lang>
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,515:
: make-change ( cents coins -- ways )
members [ ] inv-sort-with (make-change) ;
</syntaxhighlight>
</lang>
Or one could implement the algorithm like described in http://www.cdn.geeksforgeeks.org/dynamic-programming-set-7-coin-change.
<langsyntaxhighlight lang="factor">
USE: math.ranges
 
Line 1,538:
13398445413854501
Running time: 0.029163549 seconds
</syntaxhighlight>
</lang>
 
=={{header|Forth}}==
<langsyntaxhighlight lang="forth">\ counting change (SICP section 1.2.2)
 
: table create does> swap cells + @ ;
Line 1,556:
then then ;
 
100 5 count-change .</langsyntaxhighlight>
 
=={{header|FreeBASIC}}==
Translation from "Dynamic Programming Solution: Python version" on this webside [http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/]
<langsyntaxhighlight lang="freebasic">' version 09-10-2016
' compile with: fbc -s console
 
Line 1,625:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre>
Line 1,635:
 
=={{header|FutureBasic}}==
<langsyntaxhighlight lang="futurebasic">include "NSLog.incl"
 
void local fn Doit
Line 1,660:
fn DoIt
 
HandleEvents</langsyntaxhighlight>
 
Output:
Line 1,677:
=={{header|Go}}==
{{trans|lisp}}
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 1,713:
}
panic(kindsOfCoins)
}</langsyntaxhighlight>
Output:
<pre>
Line 1,719:
</pre>
Alternative algorithm, practical for the optional task.
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 1,737:
}
return ways[amount]
}</langsyntaxhighlight>
Output:
<pre>
Line 1,746:
{{trans|Go}}
Intuitive Recursive Solution:
<langsyntaxhighlight lang="groovy">def ccR
ccR = { BigInteger tot, List<BigInteger> coins ->
BigInteger n = coins.size()
Line 1,758:
ccR(tot - coins[0], coins)
}
}</langsyntaxhighlight>
 
Fast Iterative Solution:
<langsyntaxhighlight lang="groovy">def ccI = { BigInteger tot, List<BigInteger> coins ->
List<BigInteger> ways = [0g] * (tot+1)
ways[0] = 1g
Line 1,770:
}
ways[tot]
}</langsyntaxhighlight>
 
Test:
<langsyntaxhighlight lang="groovy">println '\nBase:'
[iterative: ccI, recursive: ccR].each { label, cc ->
print "${label} "
Line 1,786:
def ways = ccI(1000g * 100, [100g, 50g, 25g, 10g, 5g, 1g])
def elapsed = System.currentTimeMillis() - start
println ("answer: ${ways} elapsed: ${elapsed}ms")</langsyntaxhighlight>
 
Output:
Line 1,798:
=={{header|Haskell}}==
Naive implementation:
<langsyntaxhighlight lang="haskell">count :: (Integral t, Integral a) => t -> [t] -> a
count 0 _ = 1
count _ [] = 0
Line 1,807:
 
main :: IO ()
main = print (count 100 [1, 5, 10, 25])</langsyntaxhighlight>
 
Much faster, probably harder to read, is to update results from bottom up:
<langsyntaxhighlight lang="haskell">count :: Integral a => [Int] -> [a]
count = foldr addCoin (1 : repeat 0)
where
Line 1,820:
main = do
print (count [25, 10, 5, 1] !! 100)
print (count [100, 50, 25, 10, 5, 1] !! 10000)</langsyntaxhighlight>
 
Or equivalently, (reformulating slightly, and adding a further test):
 
<langsyntaxhighlight lang="haskell">import Data.Function (fix)
 
count
Line 1,845:
, ([100, 50, 25, 10, 5, 1], 1000000)
]
</syntaxhighlight>
</lang>
{{Out}}
<pre>242
Line 1,852:
 
=={{header|Icon}} and {{header|Unicon}}==
<langsyntaxhighlight Iconlang="icon">procedure main()
 
US_coins := [1, 5, 10, 25]
Line 1,870:
every (s := "[ ") ||:= !L || " "
return s || "]"
end</langsyntaxhighlight>
 
This is a naive implementation and very slow.
{{improve|Icon|Needs a better algorithm.}}
<langsyntaxhighlight Iconlang="icon">procedure CountCoins(amt,coins) # very slow, recurse by coin value
local count
static S
Line 1,892:
return (amt ~= 0) | 1
}
end</langsyntaxhighlight>
 
{{libheader|Icon Programming Library}}
Line 1,902:
 
Another one:
<syntaxhighlight lang="icon">
<lang Icon>
# coin.icn
# usage: coin value
Line 1,921:
write(" coins in ", count(coins, money), " different ways.")
end
</syntaxhighlight>
</lang>
Output:
<pre>
Line 1,929:
 
=={{header|IS-BASIC}}==
<langsyntaxhighlight ISlang="is-BASICbasic">100 PROGRAM "Coins.bas"
110 LET MONEY=100
120 LET COUNT=0
Line 1,946:
270 NEXT
280 NEXT
290 PRINT COUNT;"different combinations found."</langsyntaxhighlight>
 
=={{header|J}}==
Line 1,952:
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).
 
<langsyntaxhighlight lang="j">merge=: ({:"1 (+/@:({."1),{:@{:)/. ])@;
count=: {.@] <@,. {:@] - [ * [ i.@>:@<.@%~ {:@]
init=: (1 ,. ,.)^:(0=#@$)
nsplits=: 0 { [: +/ [: (merge@:(count"1) init)/ }.@/:~@~.@,</langsyntaxhighlight>
 
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,961:
Thus:
 
<langsyntaxhighlight lang="j"> 100 nsplits 1 5 10 25
242</langsyntaxhighlight>
 
And, on a 64 bit machine with sufficient memory:
 
<langsyntaxhighlight lang="j"> 100000 nsplits 1 5 10 25 50 100
13398445413854501</langsyntaxhighlight>
 
Warning: the above version can miss one when the largest coin is equal to the total value.
Line 1,973:
For British viewers change from £10 using £10 £5 £2 £1 50p 20p 10p 5p 2p and 1p
 
<langsyntaxhighlight lang="j"> init =: 4 : '(1+x)$1'
length1 =: 4 : '1=#y'
f =: 4 : ',/ +/\ (-x) ]\ y'
Line 1,981:
 
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)</langsyntaxhighlight>
 
=={{header|Java}}==
{{trans|D}}
{{works with|Java|1.5+}}
<langsyntaxhighlight lang="java5">import java.util.Arrays;
import java.math.BigInteger;
 
Line 2,031:
}
}
}</langsyntaxhighlight>
Output:
<pre>242
Line 2,049:
Efficient iterative algorithm (cleverly calculates number of combinations without permuting them)
 
<langsyntaxhighlight Javascriptlang="javascript">function countcoins(t, o) {
'use strict';
var targetsLength = t + 1;
Line 2,067:
 
return t[targetsLength - 1];
}</langsyntaxhighlight>
 
{{out}}
JavaScript hits integer limit for optional task
<langsyntaxhighlight JavaScriptlang="javascript">countcoins(100, [1,5,10,25]);
242</langsyntaxhighlight>
 
===Recursive===
Line 2,078:
Inefficient recursive algorithm (naively calculates number of combinations by actually permuting them)
 
<langsyntaxhighlight Javascriptlang="javascript">function countcoins(t, o) {
'use strict';
var operandsLength = o.length;
Line 2,102:
permutate(0, 0);
return solutions;
}</langsyntaxhighlight>
{{Out}}
Too slow for optional task
 
<langsyntaxhighlight JavaScriptlang="javascript">countcoins(100, [1,5,10,25]);
242</langsyntaxhighlight>
 
===Iterative again===
 
{{Trans|C#}}
<langsyntaxhighlight lang="javascript">var amount = 100,
coin = [1, 5, 10, 25]
var t = [1];
Line 2,119:
for (var ci = coin[i], a = ci; a <= amount; a++)
t[a] += t[a - ci]
document.write(t[amount])</langsyntaxhighlight>
{{Out}}
<pre>242</pre>
Line 2,125:
=={{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.
<langsyntaxhighlight lang="jq"># How many ways are there to make "target" cents, given a list of coin
# denominations as input.
# The strategy is to record at total[n] the number of ways to make n cents.
Line 2,140:
end
end ) )
| .[target] ;</langsyntaxhighlight>
'''Example''':
[1,5,10,25] | countcoins(100)
Line 2,148:
=={{header|Julia}}==
{{trans|Python}}
<langsyntaxhighlight lang="julia">function changes(amount::Int, coins::Array{Int})::Int128
ways = zeros(Int128, amount + 1)
ways[1] = 1
Line 2,158:
 
@show changes(100, [1, 5, 10, 25])
@show changes(100000, [1, 5, 10, 25, 50, 100])</langsyntaxhighlight>
 
{{out}}
Line 2,166:
=={{header|Kotlin}}==
{{trans|C#}}
<langsyntaxhighlight lang="scala">// version 1.0.6
 
fun countCoins(c: IntArray, m: Int, n: Int): Long {
Line 2,180:
println(countCoins(c, 4, 100))
println(countCoins(c, 6, 1000 * 100))
}</langsyntaxhighlight>
 
{{out}}
Line 2,190:
=={{header|Lasso}}==
Inspired by the javascript iterative example for the same task
<langsyntaxhighlight Lassolang="lasso">define cointcoins(
target::integer,
operands::array
Line 2,219:
cointcoins(100, array(1,5,10,25,))
'<br />'
cointcoins(100000, array(1, 5, 10, 25, 50, 100))</langsyntaxhighlight>
Output:
<pre>242
Line 2,226:
=={{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"...
<langsyntaxhighlight Lualang="lua">function countSums (amount, values)
local t = {}
for i = 1, amount do t[i] = 0 end
Line 2,237:
 
print(countSums(100, {1, 5, 10, 25}))
print(countSums(100000, {1, 5, 10, 25, 50, 100}))</langsyntaxhighlight>
{{out}}
<pre>242
Line 2,245:
===Fast O(n*m)===
Works with decimals in table()
<syntaxhighlight lang="m2000 interpreter">
<lang M2000 Interpreter>
Module FindCoins {
Function count(c(), n) {
Line 2,260:
}
FindCoins
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,269:
Using an inventory (a kind of vector) to save first search (but is slower than previous one)
 
<syntaxhighlight lang="m2000 interpreter">
<lang M2000 Interpreter>
Module CheckThisToo {
inventory c=" 0 0":=1@
Line 2,284:
}
CheckThisToo
</syntaxhighlight>
</lang>
 
=={{header|Maple}}==
Line 2,290:
Straightforward implementation with power series. Not very efficient for large amounts. Note that in the following, all amounts are in '''cents'''.
 
<langsyntaxhighlight lang="maple">assume(p::posint,abs(x)<1):
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,304:
 
ways(100000,[1,5,10,25,50,100]);
# 13398445413854501</langsyntaxhighlight>
 
A faster implementation.
 
<langsyntaxhighlight lang="maple">ways2:=proc(amount,purse)
local a,n,k;
a:=Array(1..amount);
Line 2,345:
 
ways2(100000000,[1,5,10,25,50,100]);
# 13333398333445333413833354500001</langsyntaxhighlight>
 
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:
 
<langsyntaxhighlight lang="maple">P:=n->4/(3*10^9)*n^5+65/10^8*n^4+112/10^6*n^3+805/10^5*n^2+635/3000*n+1:
 
for k from 2 to 8 do lprint(P(10^k)) od:
Line 2,358:
1333983445341383545001
133339833445334138335450001
13333398333445333413833354500001</langsyntaxhighlight>
 
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
 
<langsyntaxhighlight lang="maple">Q:=n->40/3*n^5+65*n^4+112*n^3+161/2*n^2+127/6*n+1:</langsyntaxhighlight>
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
{{trans|Go}}
<langsyntaxhighlight Mathematicalang="mathematica">CountCoins[amount_, coinlist_] := ( ways = ConstantArray[1, amount];
Do[For[j = coin, j <= amount, j++,
If[ j - coin == 0,
Line 2,373:
]]
, {coin, coinlist}];
ways[[amount]])</langsyntaxhighlight>
Example usage:
<pre>CountCoins[100, {25, 10, 5}]
Line 2,382:
 
=={{header|MATLAB}} / {{header|Octave}}==
<syntaxhighlight lang="matlab">
<lang Matlab>
%% Count_The_Coins
clear;close all;clc;
Line 2,413:
end % End for
toc
</syntaxhighlight>
</lang>
Example Output:
<pre>Main Challenge: 242
Line 2,420:
 
=={{header|Mercury}}==
<langsyntaxhighlight Mercurylang="mercury">:- module coins.
:- interface.
:- import_module int, io.
Line 2,467:
show([P|T], !IO) :-
io.write(P, !IO), io.nl(!IO),
show(T, !IO).</langsyntaxhighlight>
 
=={{header|Nim}}==
{{trans|Python}}
<langsyntaxhighlight lang="nim">proc changes(amount: int, coins: openArray[int]): int =
var ways = @[1]
ways.setLen(amount+1)
Line 2,480:
 
echo changes(100, [1, 5, 10, 25])
echo changes(100000, [1, 5, 10, 25, 50, 100])</langsyntaxhighlight>
Output:
<pre>242
Line 2,489:
Translation of the D minimal version:
 
<langsyntaxhighlight lang="ocaml">let changes amount coins =
let ways = Array.make (amount + 1) 0L in
ways.(0) <- 1L;
Line 2,502:
Printf.printf "%Ld\n" (changes 1_00 [25; 10; 5; 1]);
Printf.printf "%Ld\n" (changes 1000_00 [100; 50; 25; 10; 5; 1]);
;;</langsyntaxhighlight>
 
Output:
Line 2,511:
 
=={{header|PARI/GP}}==
<langsyntaxhighlight lang="parigp">coins(v)=prod(i=1,#v,1/(1-'x^v[i]));
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)</langsyntaxhighlight>
Output:
<pre>%1 = 242
Line 2,520:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use 5.01;
use Memoize;
 
Line 2,542:
say 'Ways to change $ 1000 with addition of less common coins: ',
cc_optimized( 1000 * 100, 1, 5, 10, 25, 50, 100 );
</syntaxhighlight>
</lang>
{{out}}
Ways to change $ 1 with common coins: 242
Line 2,549:
=={{header|Phix}}==
Very fast, from http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change
<!--<langsyntaxhighlight Phixlang="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>
Line 2,560:
<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>
<!--</langsyntaxhighlight>-->
An attempt to explain this algorithm further seems worthwhile:
<!--<langsyntaxhighlight Phixlang="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)
Line 2,607:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 2,627:
Using dynamic programming with tabling.
 
<langsyntaxhighlight Picatlang="picat">go =>
Problems = [[ 1*100, [25,10,5,1]], % 1 dollar
[ 100*100, [100,50,25,10,5,1]], % 100 dollars
Line 2,656:
end
end,
Sum = Sum1.</langsyntaxhighlight>
 
{{Output}}
Line 2,686:
=={{header|PicoLisp}}==
{{trans|C}}
<langsyntaxhighlight PicoLisplang="picolisp">(de coins (Sum Coins)
(let (Buf (mapcar '((N) (cons 1 (need (dec N) 0))) Coins) Prev)
(do Sum
Line 2,693:
(inc (rot L) Prev)
(setq Prev (car L)) ) )
Prev ) )</langsyntaxhighlight>
Test:
<langsyntaxhighlight PicoLisplang="picolisp">(for Coins '((100 50 25 10 5 1) (200 100 50 20 10 5 2 1))
(println (coins 100 (cddr Coins)))
(println (coins (* 1000 100) Coins))
(println (coins (* 10000 100) Coins))
(println (coins (* 100000 100) Coins))
(prinl) )</langsyntaxhighlight>
Output:
<pre>242
Line 2,715:
Basic version using brute force and constraint programming, the bonus version will work but takes a long time so skipped it.
 
<langsyntaxhighlight Prologlang="prolog">:- use_module(library(clpfd)).
 
% Basic, Q = Quarter, D = Dime, N = Nickel, P = Penny
Line 2,724:
coins_for(T) :-
coins(Q,D,N,P,T),
maplist(indomain, [Q,D,N,P]).</langsyntaxhighlight>
{{out}}
<pre>
Line 2,734:
===Simple version===
{{trans|Go}}
<langsyntaxhighlight lang="python">def changes(amount, coins):
ways = [0] * (amount + 1)
ways[0] = 1
Line 2,743:
 
print changes(100, [1, 5, 10, 25])
print changes(100000, [1, 5, 10, 25, 50, 100])</langsyntaxhighlight>
Output:
<pre>242
Line 2,749:
===Fast version===
{{trans|C}}
<langsyntaxhighlight lang="python">try:
import psyco
psyco.full()
Line 2,786:
print count_changes(10000000, coins), "\n"
 
main()</langsyntaxhighlight>
Output:
<pre>242
Line 2,800:
=={{header|Quackery}}==
 
<langsyntaxhighlight Quackerylang="quackery"> [ stack ] is lim ( --> s )
 
[ swap dup 1+ lim put
Line 2,822:
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</langsyntaxhighlight>
 
{{out}}
Line 2,837:
=={{header|Racket}}==
This is the basic recursive way:
<langsyntaxhighlight Racketlang="racket">#lang racket
(define (ways-to-make-change cents coins)
(cond ((null? coins) 0)
Line 2,847:
 
(ways-to-make-change 100 '(25 10 5 1)) ; -> 242
</syntaxhighlight>
</lang>
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:
<langsyntaxhighlight Racketlang="racket">#lang racket
(define memos (make-hash))
Line 2,873:
 
cpu time: 20223 real time: 20673 gc time: 10233
99341140660285639188927260001 |#</langsyntaxhighlight>
 
=={{header|Raku}}==
Line 2,880:
{{trans|Ruby}}
 
<syntaxhighlight lang="raku" perl6line># Recursive (cached)
sub change-r($amount, @coins) {
my @cache = [1 xx @coins], |([] xx $amount);
Line 2,913:
say "\nRecursive:";
say change-r 1_00, [1,5,10,25];
say change-r 1000_00, [1,5,10,25,50,100];</langsyntaxhighlight>
{{out}}
<pre>Iterative:
Line 2,934:
 
The amount can be specified in cents (as a number), or in dollars (as for instance, &nbsp; $1000).
<langsyntaxhighlight lang="rexx">/*REXX program counts the number of ways to make change with coins from an given amount.*/
numeric digits 20 /*be able to handle large amounts of $.*/
parse arg N $ /*obtain optional arguments from the CL*/
Line 2,965:
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.*/</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 2,980:
===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.
<langsyntaxhighlight lang="rexx">/*REXX program counts the number of ways to make change with coins from an given amount.*/
numeric digits 20 /*be able to handle large amounts of $.*/
parse arg N $ /*obtain optional arguments from the CL*/
Line 3,012:
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. */</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the following input for the optional test case: &nbsp; &nbsp; <tt> $1000 &nbsp; 1 &nbsp; 5 &nbsp; 10 &nbsp; 25 &nbsp; 50 &nbsp; 100 </tt>}}
<pre>
Line 3,021:
===with error checking===
This REXX version is identical to the previous REXX version, but has error checking for the amount and the coins specified.
<langsyntaxhighlight lang="rexx">/*REXX program counts the number of ways to make change with coins from an given amount.*/
numeric digits 20 /*be able to handle large amounts of $.*/
parse arg N $ /*obtain optional arguments from the CL*/
Line 3,074:
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. */</langsyntaxhighlight>
{{out|output|text=&nbsp; is the same as the previous REXX version.}}<br><br>
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
penny = 1
nickel = 1
Line 3,098:
next
see count + " ways to make a dollar" + nl
</syntaxhighlight>
</lang>
Output:
<pre>
Line 3,119:
'''Recursive, with caching'''
 
<langsyntaxhighlight lang="ruby">def make_change(amount, coins)
@cache = Array.new(amount+1){|i| Array.new(coins.size, i.zero? ? 1 : nil)}
@coins = coins
Line 3,136:
 
p make_change( 1_00, [1,5,10,25])
p make_change(1000_00, [1,5,10,25,50,100])</langsyntaxhighlight>
 
outputs
Line 3,144:
'''Iterative'''
 
<langsyntaxhighlight lang="ruby">def make_change2(amount, coins)
n, m = amount, coins.size
table = Array.new(n+1){|i| Array.new(m, i.zero? ? 1 : nil)}
Line 3,157:
 
p make_change2( 1_00, [1,5,10,25])
p make_change2(1000_00, [1,5,10,25,50,100])</langsyntaxhighlight>
outputs
<pre>242
Line 3,163:
 
=={{header|Run BASIC}}==
<langsyntaxhighlight lang="runbasic">for penny = 0 to 100
for nickel = 0 to 20
for dime = 0 to 10
Line 3,175:
next nickel
next penny
print count;" ways to make a buck"</langsyntaxhighlight>Output:
<pre>0 pennies 0 nickels 0 dimes 4 quarters
0 pennies 0 nickels 5 dimes 2 quarters
Line 3,189:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">fn make_change(coins: &[usize], cents: usize) -> usize {
let size = cents + 1;
let mut ways = vec![0; size];
Line 3,204:
println!("{}", make_change(&[1,5,10,25], 100));
println!("{}", make_change(&[1,5,10,25,50,100], 100_000));
}</langsyntaxhighlight>
{{output}}
<pre>242
Line 3,211:
=={{header|SAS}}==
Generate the solutions using CLP solver in SAS/OR:
<langsyntaxhighlight lang="sas">/* call OPTMODEL procedure in SAS/OR */
proc optmodel;
/* declare set and names of coins */
Line 3,231:
/* print all solutions */
proc print data=sols;
run;</langsyntaxhighlight>
 
Output:
Line 3,250:
 
=={{header|Scala}}==
<langsyntaxhighlight lang="scala">def countChange(amount: Int, coins:List[Int]) = {
val ways = Array.fill(amount + 1)(0)
ways(0) = 1
Line 3,261:
 
countChange (15, List(1, 5, 10, 25))
</syntaxhighlight>
</lang>
Output:
<pre>res0: Int = 6
Line 3,267:
 
Recursive implementation:
<langsyntaxhighlight lang="scala">def count(target: Int, coins: List[Int]): Int = {
if (target == 0) 1
else if (coins.isEmpty || target < 0) 0
Line 3,275:
 
count(100, List(25, 10, 5, 1))
</syntaxhighlight>
</lang>
 
=={{header|Scheme}}==
A simple recursive implementation:
<langsyntaxhighlight lang="scheme">(define ways-to-make-change
(lambda (x coins)
(cond
Line 3,287:
[else (+ (ways-to-make-change x (cdr coins)) (ways-to-make-change (- x (car coins)) coins))])))
 
(ways-to-make-change 100)</langsyntaxhighlight>
Output:
<pre>242</pre>
Line 3,295:
===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,316:
end
 
disp(ways);</langsyntaxhighlight>
 
{{out}}
Line 3,325:
{{trans|Python}}
 
<syntaxhighlight lang="text">function varargout=changes(amount, coins)
ways = zeros(1,amount + 2);
ways(1) = 1;
Line 3,339:
a=changes(100, [1, 5, 10, 25]);
b=changes(100000, [1, 5, 10, 25, 50, 100]);
mprintf("%.0f, %.0f", a, b);</langsyntaxhighlight>
 
{{out}}
Line 3,346:
 
=={{header|Seed7}}==
<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
Line 3,386:
writeln(changeCount( 100000, euCoins));
writeln(changeCount(1000000, euCoins));
end func;</langsyntaxhighlight>
 
Output:
Line 3,399:
=={{header|Sidef}}==
{{trans|Perl}}
<langsyntaxhighlight lang="ruby">func cc(_) { 0 }
func cc({ .is_neg }, *_) { 0 }
func cc({ .is_zero }, *_) { 1 }
Line 3,415:
 
var y = cc_optimized(1000 * 100, 1, 5, 10, 25, 50, 100);
say "Ways to change $1000 with addition of less common coins: #{y}";</langsyntaxhighlight>
{{out}}
<pre>
Line 3,425:
{{trans|Python}}
{{libheader|Attaswift BigInt}}
<langsyntaxhighlight lang="swift">import BigInt
 
func countCoins(amountCents cents: Int, coins: [Int]) -> BigInt {
Line 3,468:
print(countCoins(amountCents: 10000000, coins: set))
print()
}</langsyntaxhighlight>
 
{{out}}
Line 3,483:
=={{header|Tailspin}}==
{{trans|Rust}}
<langsyntaxhighlight lang="tailspin">
templates makeChange&{coins:}
def paid: $;
Line 3,498:
100000 -> makeChange&{coins: [1,5,10,25,50,100]} -> '$; ways to change 1000 dollars with all coins
' -> !OUT::write
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,507:
=={{header|Tcl}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
 
proc makeChange {amount coins} {
Line 3,528:
# 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}]</langsyntaxhighlight>
Output:
<pre>
Line 3,539:
=={{header|uBasic/4tH}}==
{{trans|Run BASIC}}
<syntaxhighlight lang="text">c = 0
for p = 0 to 100
for n = 0 to 20
Line 3,552:
next n
next p
print c;" ways to make a buck"</langsyntaxhighlight>
{{out}}
<pre>0 pennies 0 nickels 0 dimes 4 quarters
Line 3,569:
{{trans|Common Lisp}}
{{works with|bash}}
<langsyntaxhighlight lang="bash">function count_change {
local -i amount=$1 coin j
local ways=(1)
Line 3,581:
}
count_change 100 25 10 5 1
count_change 100000 100 50 25 10 5 1</langsyntaxhighlight>
 
{{works with|ksh|93}}
<langsyntaxhighlight lang="bash">function count_change {
typeset -i amount=$1 coin j
typeset ways
Line 3,597:
}
count_change 100 25 10 5 1
count_change 100000 100 50 25 10 5 1</langsyntaxhighlight>
 
{{works with|ksh|88}}
<langsyntaxhighlight lang="bash">function count_change {
typeset -i amount=$1 coin j
typeset ways
Line 3,615:
}
count_change 100 25 10 5 1
# (optional task exceeds a subscript limit in ksh88)</langsyntaxhighlight>
 
And just for fun, here's one that works even with the original V7 shell:
 
{{works with|sh|v7}}
<langsyntaxhighlight lang="bash">if [ $# -lt 2 ]; then
set ${1-100} 25 10 5 1
fi
Line 3,634:
done
done
eval "echo \$ways_$amount"</langsyntaxhighlight>
 
{{Out}}
Line 3,641:
 
=={{header|VBA}}==
{{trans|Phix}}<langsyntaxhighlight lang="vb">Private Function coin_count(coins As Variant, amount As Long) As Variant 'return type will be Decimal
'sequence s = Repeat(0, amount + 1)
Dim s As Variant
Line 3,662:
us_coins = [{100,50,25, 10, 5, 1}]
Debug.Print coin_count(us_coins, 100000)
End Sub</langsyntaxhighlight>{{out}}
<pre> 242
13398445413854501 </pre>
Line 3,668:
=={{header|VBScript}}==
{{trans|C#}}
<syntaxhighlight lang="vb">
<lang vb>
Function count(coins,m,n)
ReDim table(n+1)
Line 3,689:
n = 100
WScript.StdOut.WriteLine count(arr,m,n)
</syntaxhighlight>
</lang>
 
{{Out}}
Line 3,699:
{{trans|VBA}}
{{works with|Visual Basic|6}}
<langsyntaxhighlight lang="vb">Option Explicit
'----------------------------------------------------------------------
Private Function coin_count(coins As Variant, amount As Long) As Variant
Line 3,727:
Debug.Print coin_count(us_coins, 100000)
End Sub</langsyntaxhighlight>
{{out}}
<pre> 242
Line 3,734:
=={{header|Vlang}}==
{{trans|go}}
<langsyntaxhighlight lang="go">fn main() {
amount := 100
println("amount, ways to make change: $amount ${count_change(amount)}"))
Line 3,768:
}
}
}</langsyntaxhighlight>
Output:
<pre>
Line 3,778:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight lang="ecmascript">import "/big" for BigInt
import "/fmt" for Fmt
 
Line 3,793:
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))</langsyntaxhighlight>
 
{{out}}
Line 3,803:
=={{header|zkl}}==
{{trans|Scheme}}
<langsyntaxhighlight lang="zkl">fcn ways_to_make_change(x, coins=T(25,10,5,1)){
if(not coins) return(0);
if(x<0) return(0);
Line 3,809:
ways_to_make_change(x, coins[1,*]) + ways_to_make_change(x - coins[0], coins)
}
ways_to_make_change(100).println();</langsyntaxhighlight>
{{out}}
<pre>242</pre>
Line 3,815:
 
{{trans|Ruby}}
<langsyntaxhighlight lang="zkl">fcn make_change2(amount, coins){
n, m := amount, coins.len();
table := (0).pump(n+1,List, (0).pump(m,List().write,1).copy);
Line 3,826:
 
println(make_change2( 100, T(1,5,10,25)));
make_change2(0d1000_00, T(1,5,10,25,50,100)) : "%,d".fmt(_).println();</langsyntaxhighlight>
{{out}}
<pre>
Line 3,836:
{{trans|AWK}}
Test with emulator at full speed for reasonable performance.
<langsyntaxhighlight lang="zxbasic">10 LET amount=100
20 GO SUB 1000
30 STOP
Line 3,855:
1140 NEXT p
1150 PRINT count
1160 RETURN </langsyntaxhighlight>
10,327

edits