Count the coins/0-1: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 35: | Line 35: | ||
countcoins( 6, [1, 2, 3, 4, 5] ); |
countcoins( 6, [1, 2, 3, 4, 5] ); |
||
countcoins( 6, [1, 1, 2, 3, 3, 4, 5] ); |
countcoins( 6, [1, 1, 2, 3, 3, 4, 5] ); |
||
countcoins( 40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] ); |
|||
my $count; |
|||
sub countcoins |
sub countcoins |
||
Line 41: | Line 43: | ||
my ($want, $coins) = @_; |
my ($want, $coins) = @_; |
||
print "\nsum $want coins @$coins\n"; |
print "\nsum $want coins @$coins\n"; |
||
$count = 0; |
|||
count($want, [], 0, $coins); |
count($want, [], 0, $coins); |
||
print "Number of ways: $count\n"; |
|||
} |
} |
||
Line 47: | Line 51: | ||
{ |
{ |
||
my ($want, $used, $sum, $have) = @_; |
my ($want, $used, $sum, $have) = @_; |
||
if( $sum == $want ) { |
if( $sum == $want ) { $count++ } |
||
elsif( $sum > $want or @$have == 0 ) {} |
elsif( $sum > $want or @$have == 0 ) {} |
||
else |
else |
||
Line 56: | Line 60: | ||
} |
} |
||
}</lang> |
}</lang> |
||
Third case not shown because it's too large. |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
sum 6 coins 1 2 3 4 5 |
sum 6 coins 1 2 3 4 5 |
||
Number of ways: 3 |
|||
used 1 5 |
|||
used 2 4 |
|||
sum 6 coins 1 1 2 3 3 4 5 |
sum 6 coins 1 1 2 3 3 4 5 |
||
Number of ways: 9 |
|||
used 1 1 4 |
|||
used 1 2 3 |
|||
sum 40 coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 |
|||
used 1 2 3 |
|||
Number of ways: 464 |
|||
used 1 5 |
|||
used 1 2 3 |
|||
used 1 2 3 |
|||
used 1 5 |
|||
used 2 4 |
|||
used 3 3 |
|||
</pre> |
</pre> |
Revision as of 17:42, 6 January 2021
Count the coins/0-1 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Let say you have some coins in your wallet and you want to have a given sum.
You can use each coin zero or one time.
How many ways can you do it ?
The result should be a number.
For instance the answer is 10 when coins = [1, 2, 3, 4, 5] and sum = 6.
- Task
Show the result the for the following examples:
- coins = [1, 2, 3, 4, 5] and sum = 6
- coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6
- coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40
- Extra
- Show the result of the same examples when the order you take the coins doesn't matter. For instance the answer is 3 when coins = [1, 2, 3, 4, 5] and sum = 6.
- Show an example of coins you used to reach the given sum and their indices. See Perl for this case.
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1 use warnings;
countcoins( 6, [1, 2, 3, 4, 5] ); countcoins( 6, [1, 1, 2, 3, 3, 4, 5] ); countcoins( 40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] );
my $count;
sub countcoins
{ my ($want, $coins) = @_; print "\nsum $want coins @$coins\n"; $count = 0; count($want, [], 0, $coins); print "Number of ways: $count\n"; }
sub count
{ my ($want, $used, $sum, $have) = @_; if( $sum == $want ) { $count++ } elsif( $sum > $want or @$have == 0 ) {} else { my ($thiscoin, @rest) = @$have; count( $want, [@$used, $thiscoin], $sum + $thiscoin, \@rest); count( $want, $used, $sum, \@rest); } }</lang>
- Output:
sum 6 coins 1 2 3 4 5 Number of ways: 3 sum 6 coins 1 1 2 3 3 4 5 Number of ways: 9 sum 40 coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 Number of ways: 464