66 lines
1.1 KiB
ObjectPascal
66 lines
1.1 KiB
ObjectPascal
program Average_loop_length;
|
|
|
|
{$APPTYPE CONSOLE}
|
|
|
|
uses
|
|
System.SysUtils,
|
|
System.Math;
|
|
|
|
const
|
|
MAX_N = 20;
|
|
TIMES = 1000000;
|
|
|
|
function Factorial(const n: Double): Double;
|
|
begin
|
|
Result := 1;
|
|
if n > 1 then
|
|
Result := n * Factorial(n - 1);
|
|
end;
|
|
|
|
function Expected(const n: Integer): Double;
|
|
var
|
|
i: Integer;
|
|
begin
|
|
Result := 0;
|
|
for i := 1 to n do
|
|
Result := Result + (factorial(n) / Power(n, i) / factorial(n - i));
|
|
end;
|
|
|
|
function Test(const n, times: Integer): integer;
|
|
var
|
|
i, x, bits: Integer;
|
|
begin
|
|
Result := 0;
|
|
for i := 0 to times - 1 do
|
|
begin
|
|
x := 1;
|
|
bits := 0;
|
|
while ((bits and x) = 0) do
|
|
begin
|
|
inc(Result);
|
|
bits := bits or x;
|
|
x := 1 shl random(n);
|
|
end;
|
|
end;
|
|
end;
|
|
|
|
var
|
|
n, cnt: Integer;
|
|
avg, theory, diff: Double;
|
|
|
|
begin
|
|
Randomize;
|
|
Writeln(#10' tavg'^I'exp.'^I'diff'#10'-------------------------------');
|
|
|
|
for n := 1 to MAX_N do
|
|
begin
|
|
cnt := test(n, times);
|
|
avg := cnt / times;
|
|
theory := expected(n);
|
|
diff := (avg / theory - 1) * 100;
|
|
writeln(format('%2d %8.4f %8.4f %6.3f%%', [n, avg, theory, diff]));
|
|
end;
|
|
|
|
readln;
|
|
end.
|