Anonymous user
Count the coins/0-1: Difference between revisions
m
→{{header|Pascal}}: added checking all weights not taking order into account
m (→{{header|Perl}}: prepend pascal) |
m (→{{header|Pascal}}: added checking all weights not taking order into account) |
||
Line 159:
</pre>
=={{header|Pascal}}==
first count all combinations by brute force.Order is important.Modified nQueens.<BR>Next adding weigths by index.<BR>Using Phix wording 'silly'.
<lang pascal>program Coins0_1;
{$IFDEF FPC}
Line 177:
type
{$IFNDEF FPC}
NativeInt =
{$ENDIF}
tFreeCol = array[0..nmax] of Int32;
var
n,gblCount : nativeUInt;▼
FreeIdx,
IdxWeight : tFreeCol;
n,
procedure AddNextWeight(Row,sum:nativeInt);
//order is important
var
i,Col,Weight : nativeInt;
Line 195 ⟶ 197:
Col := FreeIdx[i];
Weight:= IdxWeight[col];
IF Sum+Weight
CONTINUE;▼
If Sum = 0 then▼
Begin
Sum
FreeIdx[i] := FreeIdx[Row];
FreeIdx[Row] := Col;
AddNextWeight(Row+1,sum);
//Undo
Sum -=Weight;
FreeIdx[Row] := FreeIdx[i];
FreeIdx[i] := Col;
end;
end;
end;
end;
procedure CheckBinary(n,MaxIdx,Sum:NativeInt);
//order is not important
Begin
inc(gblcount);
If (sum < 0) AND (n <= MaxIdx) then
Begin
//test next sum
CheckBinary(n+1,MaxIdx,Sum);// add nothing
CheckBinary(n+1,MaxIdx,Sum+IdxWeight[n]);//or the actual index
end;
end;
Line 225 ⟶ 239:
gblCount := 0;
AddNextWeight(0,-MaxSum);
gblCount := 0;
CheckBinary(0,i,-MaxSum);
WriteLn(gblCount:12);
end;
Line 232 ⟶ 249:
begin
writeln('sum':6,'very silly':12,'silly':12);
For i := 0 to High(coins1) do
Begin
Line 252 ⟶ 270:
end;
CheckAll(High(coins3),40);
end.
{{out}}
<pre>
sum
6 38 9
// real 0m0,079s ( fpc 3.2.0 -O3 -Xs AMD 2200G 3.7 Ghz ) ▼
40 3782932 464
</pre>
=={{header|Perl}}==
<lang perl>#!/usr/bin/perl
| |||