Count the coins/0-1: Difference between revisions

Content added Content deleted
m (→‎{{header|Perl}}: prepend pascal)
m (→‎{{header|Pascal}}: added checking all weights not taking order into account)
Line 159: Line 159:
</pre>
</pre>
=={{header|Pascal}}==
=={{header|Pascal}}==
first count all combinations by brute force.Modified nQueens.
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;
<lang pascal>program Coins0_1;
{$IFDEF FPC}
{$IFDEF FPC}
Line 177: Line 177:
type
type
{$IFNDEF FPC}
{$IFNDEF FPC}
NativeInt = longInt;
NativeInt = Int32;
{$ENDIF}
{$ENDIF}
tFreeCol = array[0..nmax] of Int32;
tFreeCol = array[0..nmax] of Int32;
var
var
⚫
n,gblCount : nativeUInt;
FreeIdx,
FreeIdx,
IdxWeight : tFreeCol;
IdxWeight : tFreeCol;
n,
⚫
gblCount : nativeUInt;


procedure AddNextWeight(Row,sum:nativeInt);
procedure AddNextWeight(Row,sum:nativeInt);
//order is important
var
var
i,Col,Weight : nativeInt;
i,Col,Weight : nativeInt;
Line 195: Line 197:
Col := FreeIdx[i];
Col := FreeIdx[i];
Weight:= IdxWeight[col];
Weight:= IdxWeight[col];
IF Sum+Weight > 0 then
IF Sum+Weight <= 0 then
⚫
CONTINUE;

Sum +=Weight;
⚫
If Sum = 0 then
Begin
Begin
Sum -=Weight;
Sum +=Weight;
inc(gblCount);
If Sum = 0 then
end
Begin
else
Sum -=Weight;
begin
inc(gblCount);
//swap FreeRow[Row<->i]
end
FreeIdx[i] := FreeIdx[Row];
else
FreeIdx[Row] := Col;
begin
FreeIdx[i] := FreeIdx[Row];
FreeIdx[Row] := Col;


AddNextWeight(Row+1,sum);
AddNextWeight(Row+1,sum);
//Undo
//Undo
Sum -=Weight;
Sum -=Weight;
FreeIdx[Row] := FreeIdx[i];
FreeIdx[Row] := FreeIdx[i];
FreeIdx[i] := Col;
FreeIdx[i] := Col;
⚫
end;
end;
end;
end;
end;
end;
end;

procedure CheckBinary(n,MaxIdx,Sum:NativeInt);
//order is not important
Begin
⚫
if sum = 0 then
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;
end;
end;
Line 225: Line 239:
gblCount := 0;
gblCount := 0;
AddNextWeight(0,-MaxSum);
AddNextWeight(0,-MaxSum);
WriteLn(MaxSum:6,gblCount:12);
Write(MaxSum:6,gblCount:12);
gblCount := 0;
CheckBinary(0,i,-MaxSum);
WriteLn(gblCount:12);
end;
end;


Line 232: Line 249:


begin
begin
writeln('sum':6,'very silly':12,'silly':12);
For i := 0 to High(coins1) do
For i := 0 to High(coins1) do
Begin
Begin
Line 252: Line 270:
end;
end;
CheckAll(High(coins3),40);
CheckAll(High(coins3),40);
end.

end.</lang>
</lang>
{{out}}
{{out}}
<pre> 6 10
<pre>
6 38
sum very silly silly
40 3782932
6 10 3
6 38 9
⚫
// real 0m0,079s ( fpc 3.2.0 -O3 -Xs AMD 2200G 3.7 Ghz )
40 3782932 464

⚫
// real 0m0,080s ( fpc 3.2.0 -O3 -Xs AMD 2200G 3.7 Ghz )
</pre>
</pre>

=={{header|Perl}}==
=={{header|Perl}}==
<lang perl>#!/usr/bin/perl
<lang perl>#!/usr/bin/perl
Retrieved from "https://rosettacode.org/wiki/Count_the_coins/0-1"