How to resolve the algorithm Average loop length step by step in the Oberon-2 programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Average loop length step by step in the Oberon-2 programming language
Table of Contents
Problem Statement
Let f be a uniformly-randomly chosen mapping from the numbers 1..N to the numbers 1..N (note: not necessarily a permutation of 1..N; the mapping could produce a number in more than one way or not at all). At some point, the sequence 1, f(1), f(f(1))... will contain a repetition, a number that occurring for the second time in the sequence.
Write a program or a script that estimates, for each N, the average length until the first such repetition. Also calculate this expected length using an analytical formula, and optionally compare the simulated result with the theoretical one.
This problem comes from the end of Donald Knuth's Christmas tree lecture 2011. Example of expected output:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Average loop length step by step in the Oberon-2 programming language
Source code in the oberon-2 programming language
MODULE AvgLoopLen;
(* Oxford Oberon-2 *)
IMPORT Random, Out;
PROCEDURE Fac(n: INTEGER; f: REAL): REAL;
BEGIN
IF n = 0 THEN
RETURN f
ELSE
RETURN Fac(n - 1,n*f)
END
END Fac;
PROCEDURE Power(n,i: INTEGER): REAL;
VAR
p: REAL;
BEGIN
p := 1.0;
WHILE i > 0 DO p := p * n; DEC(i) END;
RETURN p
END Power;
PROCEDURE Abs(x: REAL): REAL;
BEGIN
IF x < 0 THEN RETURN -x ELSE RETURN x END
END Abs;
PROCEDURE Analytical(n: INTEGER): REAL;
VAR
i: INTEGER;
res: REAL;
BEGIN
res := 0.0;
FOR i := 1 TO n DO
res := res + (Fac(n,1.0) / Power(n,i) / Fac(n - i,1.0));
END;
RETURN res
END Analytical;
PROCEDURE Averages(n: INTEGER): REAL;
CONST
times = 100000;
VAR
rnds: SET;
r,count,i: INTEGER;
BEGIN
count := 0; i := 0;
WHILE i < times DO
rnds := {};
LOOP
r := Random.Roll(n);
IF r IN rnds THEN EXIT ELSE INCL(rnds,r); INC(count) END
END;
INC(i)
END;
RETURN count / times
END Averages;
VAR
i: INTEGER;
av,an,df: REAL;
BEGIN
Random.Randomize;
Out.String(" Averages Analytical Diff% ");Out.Ln;
FOR i := 1 TO 20 DO
Out.Int(i,3); Out.String(": ");
av := Averages(i);an := Analytical(i);df := Abs(av - an) / an * 100.0;
Out.Fixed(av,10,4);Out.Fixed(an,11,4);Out.Fixed(df,10,4);Out.Ln
END
END AvgLoopLen.
You may also check:How to resolve the algorithm Sort stability step by step in the Liberty BASIC programming language
You may also check:How to resolve the algorithm String length step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Pi step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm Call a foreign-language function step by step in the Tcl programming language
You may also check:How to resolve the algorithm Matrix chain multiplication step by step in the Kotlin programming language