Count the coins: Difference between revisions
m
→{{header|Delphi}}
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
|||
| (19 intermediate revisions by 6 users not shown) | |||
Line 156:
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}}==
Line 1,175 ⟶ 1,218:
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}}==
Line 1,196 ⟶ 1,262:
<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,713:
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,469:
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,598 ⟶ 2,721:
%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}}==
<syntaxhighlight lang="perl">use 5.01;
Line 3,191 ⟶ 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 3,475 ⟶ 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}}==
Line 3,812 ⟶ 4,025:
=={{header|V (Vlang)}}==
{{trans|
<syntaxhighlight lang="go">
fn main() {
amount := 100
println("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
return cc(amount, kinds_of_coins-1) +
cc(amount - first_denomination(kinds_of_coins), kinds_of_coins)
Line 3,834 ⟶ 4,046:
fn first_denomination(kinds_of_coins int) int {
match kinds_of_coins {
1 {return 1}
3 {return 10}
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>
Line 3,857 ⟶ 4,087:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var countCoins = Fn.new { |c, m, n|
| |||