Rosetta Code

Count the coins: Difference between revisions

Page Discussion

Count the coins (view source)

Revision as of 10:21, 16 March 2024

3,762 bytes added ,  2 months ago
→‎{{header|RPL}}: typo
(17 intermediate revisions by 7 users not shown)
Line 1,001:
Simple recursive version plus cached version using a map.
 
'''=== Dart 1 version''': ===
<syntaxhighlight lang="dart">
var cache = new Map();
Line 1,066:
</pre>
 
'''=== Dart 2 version''': ===
<syntaxhighlight lang="dart">
 
Line 1,175:
end.
</syntaxhighlight>
=={{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}}==
 
Line 1,196 ⟶ 1,216:
 
<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}}==
Line 1,618 ⟶ 1,667:
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}}==
Line 2,364 ⟶ 2,423:
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 3,191 ⟶ 3,268:
 
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 3,475 ⟶ 3,580:
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}}==
Line 3,811 ⟶ 3,935:
13398445413854501</pre>
 
=={{header|V (Vlang)}}==
{{trans|goGo}}
<syntaxhighlight lang="go">fn main() {
fn main() {
amount := 100
println("amount,: $amount; ways to make change: $amount ${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 10}
} 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)
Line 3,834 ⟶ 3,957:
fn first_denomination(kinds_of_coins int) int {
match kinds_of_coins {
1 {return 1}
2 {return 15}
3 {return 10}
}
24 {return 25}
else {exit(-2)}
return 5
}
3 {
return 10
}
4 {
return 25
}
}
return kinds_of_coins
}</syntaxhighlight>
}
</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>
 
Line 3,857 ⟶ 3,998:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./big" for BigInt
import "./fmt" for Fmt
 
var countCoins = Fn.new { |c, m, n|
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/329968...362013"