Count the coins/0-1: Difference between revisions
Added Algol 68
Alextretyak (talk | contribs) m (→{{header|11l}}) |
(Added Algol 68) |
||
Line 107:
Number of ways - order important : 3782932 (all perms of above indices)
</pre>
=={{header|ALGOL 68}}==
{{Trans|Go}}which is{{Trans|Wren}}
<syntaxhighlight lang="algol68">
BEGIN # count the ways of summing coins to a particular number - translation of the Go sample #
INT countu := 0; # order unimportant #
INT counti := 0; # order important #
INT width := 0; # for printing purposes #
PROC factorial = (INT n )INT:
BEGIN
INT prod := 1;
FOR i FROM 2 TO n DO
prod *:= i
OD;
prod
END # factorial # ;
OP LEN = ( []INT a )INT: ( UPB a - LWB a ) + 1;
OP LEN = ( STRING a )INT: ( UPB a - LWB a ) + 1;
PROC append = ( []INT a, INT b )[]INT:
BEGIN
[ 1 : LEN a + 1 ]INT result;
result[ 1 : LEN a ] := a;
result[ LEN a + 1 ] := b;
result
END # append # ;
OP TOSTRING = ( []INT a )STRING:
BEGIN
STRING result := "[";
STRING separator := "";
FOR i FROM LWB a TO UPB a DO
result +:= separator + whole( a[ i ], 0 );
separator := " "
OD;
result +:= "]"
END # TOSTRING # ;
PROC pad = ( STRING a, INT width )STRING:
IF INT len a = LEN a; len a >= width THEN a ELSE a + ( " " * ( width - len a ) ) FI;
PROC count = ( INT want, []INT used, INT sum, []INT have, uindices, rindices )VOID:
IF sum = want THEN
countu +:= 1;
counti +:= factorial( LEN used );
IF countu < 11 THEN
STRING uindices str = TOSTRING uindices;
print( ( " indices ", pad( uindices str, width ), " => used ", TOSTRING used, newline ) )
FI
ELIF sum < want AND LEN have /= 0 THEN
INT this coin = have[ LWB have ];
INT index = rindices[ LWB rindices ];
[]INT rest = have[ LWB have + 1 : ];
count( want, append( used, this coin ), sum + this coin, rest,
append( uindices, index ), rindices[ LWB rindices + 1 : ] );
count( want, used, sum, rest, uindices, rindices[ LWB rindices + 1 : ] )
FI # count # ;
PROC count coins = ( INT want, []INT coins, INT rqd width )VOID:
BEGIN
print( ( "Sum ", whole( want, 0 ), " from coins ", TOSTRING coins, newline ) );
countu := 0;
counti := 0;
width := rqd width;
[ 0 : LEN coins - 1 ]INT rindices;
FOR i FROM LWB rindices TO UPB rindices DO
rindices[ i ] := i
OD;
count( want, []INT(), 0, coins, []INT(), rindices );
IF countu > 10 THEN
print( ( " .......", newline ) );
print( ( " (only the first 10 ways generated are shown)", newline ) )
FI;
print( ( "Number of ways - order unimportant : ", whole( countu, 0 )
, " (as above)", newline ) );
print( ( "Number of ways - order important : ", whole( counti, 0 )
, " (all perms of above indices)", newline, newline ) )
END # count coins # ;
BEGIN # task #
count coins( 6, ( 1, 2, 3, 4, 5 ), 7 );
count coins( 6, ( 1, 1, 2, 3, 3, 4, 5 ), 9 );
count coins( 40, ( 1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100 ), 20 )
END
END
</syntaxhighlight>
{{out}}
<pre>
Sum 6 from coins [1 2 3 4 5]
indices [0 1 2] => used [1 2 3]
indices [0 4] => used [1 5]
indices [1 3] => used [2 4]
Number of ways - order unimportant : 3 (as above)
Number of ways - order important : 10 (all perms of above indices)
Sum 6 from coins [1 1 2 3 3 4 5]
indices [0 1 5] => used [1 1 4]
indices [0 2 3] => used [1 2 3]
indices [0 2 4] => used [1 2 3]
indices [0 6] => used [1 5]
indices [1 2 3] => used [1 2 3]
indices [1 2 4] => used [1 2 3]
indices [1 6] => used [1 5]
indices [2 5] => used [2 4]
indices [3 4] => used [3 3]
Number of ways - order unimportant : 9 (as above)
Number of ways - order important : 38 (all perms of above indices)
Sum 40 from coins [1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100]
indices [0 1 2 3 4 5 6 7 10] => used [1 2 3 4 5 5 5 5 10]
indices [0 1 2 3 4 5 6 7 11] => used [1 2 3 4 5 5 5 5 10]
indices [0 1 2 3 4 5 6 7 12] => used [1 2 3 4 5 5 5 5 10]
indices [0 1 2 3 4 5 6 7 13] => used [1 2 3 4 5 5 5 5 10]
indices [0 1 2 3 4 5 6 8] => used [1 2 3 4 5 5 5 15]
indices [0 1 2 3 4 5 6 9] => used [1 2 3 4 5 5 5 15]
indices [0 1 2 3 4 5 7 8] => used [1 2 3 4 5 5 5 15]
indices [0 1 2 3 4 5 7 9] => used [1 2 3 4 5 5 5 15]
indices [0 1 2 3 4 5 10 11] => used [1 2 3 4 5 5 10 10]
indices [0 1 2 3 4 5 10 12] => used [1 2 3 4 5 5 10 10]
.......
(only the first 10 ways generated are shown)
Number of ways - order unimportant : 464 (as above)
Number of ways - order important : 3782932 (all perms of above indices)
</pre>
| |||