Solutions TOPIC M: Recursion.
Contents :
Recursion.
Exercises :
D1: Arrow.
MODULE D1;
<* NOOPTIMIZE + *>
FROM IO IMPORT
RdChar,
WrChar, WrStr, RdStr, WrLn, RdCard, WrCard, RdInt, WrInt, RdReal,
WrReal, RdBool,
WrBool;
FROM RealMath
IMPORT
sqrt, exp, sin, cos, tan, arcsin, arccos, arctan, power, round;
PROCEDURE Arrow(size: CARDINAL);
PROCEDURE
LineOfAsterisks(nbrOfAsterisks: CARDINAL);
BEGIN
WrChar('*');
IF
nbrOfAsterisks
>
1
THEN
LineOfAsterisks(nbrOfAsterisks
-
1);
ELSE
WrLn;
END;
END
LineOfAsterisks;
PROCEDURE
ArrowRecursion(ctr: CARDINAL);
BEGIN
LineOfAsterisks(ctr);
IF
ctr
<
size
THEN
ArrowRecursion(ctr
+
1);
LineOfAsterisks(ctr);
END;
END
ArrowRecursion;
BEGIN
ArrowRecursion(1);
END Arrow;
BEGIN
WrLn;
Arrow(5);
END D1.
S1
S2
S4: Backtracking
MODULE Backtracking;
<* WOFF + *> <* NOOPTIMIZE
+ *>
FROM IO IMPORT RdChar, WrChar,
WrStr, RdStr,
WrLn, RdLn, RdCard, WrCard, RdInt, WrInt, RdReal, WrReal, WrFixReal,
RdBool,
WrBool;
CONST AANTAL_NODES = 8;
TYPE Pad = RECORD
nodes:
ARRAY[1..AANTAL_NODES]
OF
CARDINAL;
aantalNodes,
lengte:
CARDINAL;
END;
VAR graph: ARRAY[1..AANTAL_NODES],[1..AANTAL_NODES] OF CARDINAL;
(* Nuttige pad procedures *)
PROCEDURE PrintPad(pad: Pad);
VAR i: CARDINAL;
BEGIN
WrCard(pad.nodes[1], 0);
FOR i := 2 TO
pad.aantalNodes DO
WrStr("
=> ");WrCard(pad.nodes[i], 0);
END;
WrStr(" (lengte
");WrCard(pad.lengte, 0);WrStr(")");
END PrintPad;
PROCEDURE
VoegNodeToeAanPad(node:
CARDINAL; VAR pad: Pad);
BEGIN
IF
pad.aantalNodes = 0 THEN
pad.lengte
:=
0;
ELSE
pad.lengte
:=
pad.lengte
+
graph[pad.nodes[pad.aantalNodes],
node];
END;
INC(pad.aantalNodes);
pad.nodes[pad.aantalNodes] := node;
END VoegNodeToeAanPad;
(* De
te maken procedure *)
PROCEDURE ZoekKortstePad(begin, einde: CARDINAL): Pad;
VAR
kortste_pad:
Pad;
(*
de
recursieve
procedure
*)
PROCEDURE
Backtracking(alGeweest:
ARRAY
OF
BOOLEAN;
nieuweNode: CARDINAL; pad:
Pad);
VAR
i:
CARDINAL;
BEGIN
(*
....
*)
END Backtracking;
VAR al_geweest: ARRAY[1..AANTAL_NODES] OF BOOLEAN; (* houdt bij of een
node al
bezocht is *)
i:
CARDINAL;
pad:
Pad;
BEGIN
FOR
i
:=
1
TO
AANTAL_NODES DO
al_geweest[i]
:=
FALSE;
END;
al_geweest[begin]
:=
TRUE;
pad.aantalNodes
:=
0;
pad.lengte:=0;
Backtracking(al_geweest, begin, pad);
RETURN kortste_pad;
END ZoekKortstePad;
BEGIN
(* definieren van de graph *)
graph[1,2] := 5;
graph[2,1] := 5;
graph[1,3] := 7;
graph[3,1] := 7;
graph[2,4] := 4;
graph[4,2] := 4;
graph[3,4] := 4;
graph[4,3] := 4;
graph[3,5] := 2;
graph[5,3] := 2;
graph[3,6] := 5;
graph[6,3] := 5;
graph[4,5] := 3;
graph[5,4] := 3;
graph[2,7] := 7;
graph[7,2] := 7;
graph[6,5] := 2;
graph[5,6] := 2;
graph[6,8] := 5;
graph[8,6] := 5;
graph[7,8] := 6;
graph[8,7] := 6;
graph[5,7] := 3;
graph[7,5] := 3;
WrStr("Kortste pad tussen 1 & 8: ");PrintPad(ZoekKortstePad(1,
8)); WrLn;
END Backtracking.
S5: Fractals.
MODULE S3;
<* WOFF + *> <* NOOPTIMIZE
+ *>
FROM IO IMPORT
RdChar,
WrChar, WrStr, RdStr, WrLn, RdLn, RdCard, WrCard, RdInt, WrInt,RdReal,
WrReal,
WrFixReal, RdBool, WrBool, RdKey, KeyPressed;
FROM RealMath
IMPORT
sqrt, exp, sin, cos, tan, arcsin, arccos, arctan, power, round;
FROM Lib IMPORT
Delay; (*
Wait n milliseconds *)
FROM Graph IMPORT
Init,
Line, Rectangle, Circle, Disc, Polygon, _clrBLACK, _clrBLUE, _clrGREEN,
_clrCYAN, _clrRED, _clrMAGENTA;
FROM Graph IMPORT
_clrBROWN, _clrWHITE, _clrGRAY, _clrLIGHTBLUE,
_clrLIGHTGREEN,_clrLIGHTCYAN,
_clrLIGHTRED, _clrLIGHTMAGENTA, _clrLIGHTYELLOW, _clrBRIGHTWHITE;
CONST SCREEN_SIZE = 600; (* constants *)
(*************************
USEFULL
PROCEDURES ************************************************************)
PROCEDURE DivideLineIn3(x1, y1, x2,
y2:
CARDINAL; VAR x3, y3, x4, y4: CARDINAL);
(* Divides the line x1,y1 - x2,y2 in
three
pieces defined by x3,y3 & x4,y4 *)
BEGIN
x3 := VAL(CARDINAL,
VAL(INTEGER, x1)
+ (VAL(INTEGER, x2) - VAL(INTEGER, x1)) / 3);
y3 := VAL(CARDINAL,
VAL(INTEGER, y1)
+ (VAL(INTEGER, y2) - VAL(INTEGER, y1)) / 3);
x4 := VAL(CARDINAL,
VAL(INTEGER, x1)
+ (VAL(INTEGER, x2) - VAL(INTEGER, x1)) * 2 / 3);
y4 := VAL(CARDINAL,
VAL(INTEGER, y1)
+ (VAL(INTEGER, y2) - VAL(INTEGER, y1)) * 2 / 3);
END DivideLineIn3;
PROCEDURE RotatePoint(x1, y1, x2,
y2:
CARDINAL; angle: INTEGER; VAR x3, y3: CARDINAL);
(* Rotate point x2,y2 around x1,y1,
resulting in x3,y3,
the angle is in degrees
(clockwise is positive) *)
CONST DEGREES_TO_RADIANS =
3.14 /
180.0;
VAR cosa, sina, x1_r, x2_r,
y1_r,
y2_r, x3_r, y3_r: REAL;
BEGIN
cosa := cos(VAL(REAL, angle)
*
DEGREES_TO_RADIANS);
sina := sin(VAL(REAL, angle)
*
DEGREES_TO_RADIANS);
x1_r := VAL(REAL, x1);
y1_r := VAL(REAL, y1);
x2_r := VAL(REAL, x2);
y2_r := VAL(REAL, y2);
x3_r := x1_r + (x2_r - x1_r)
* cosa -
(y2_r - y1_r) * sina;
y3_r := y1_r + (x2_r - x1_r)
* sina +
(y2_r - y1_r) * cosa;
IF x3_r > 0.0 THEN
x3 :=
VAL(CARDINAL,
x3_r);
ELSE
x3 := 0;
END;
IF y3_r > 0.0 THEN
y3 :=
VAL(CARDINAL,
y3_r);
ELSE
y3 := 0;
END;
END RotatePoint;
PROCEDURE Triangle (x1, y1, x2,
y2, x3,
y3, color: CARDINAL; filled: BOOLEAN);
(* Draws a triangle with the three
given
points *)
VAR arrx, arry: ARRAY[1..4]
OF
CARDINAL;
BEGIN
arrx[1] := x1; arry[1] := y1;
arrx[2] := x2; arry[2] := y2;
arrx[3] := x3; arry[3] := y3;
arrx[4] := x1; arry[4] := y1;
Polygon(4, arrx, arry, color,
filled);
END Triangle;
PROCEDURE EquilateralTriangle(x1,
y1, x2,
y2, color: CARDINAL; filled, clockwise: BOOLEAN; VAR x3, y3:
CARDINAL);
(* draws a equilateral triangle
(gelijkzijdige driehoek) with base line x1,y1 - x2,y2
the third point is
calculated
clockwise or counterclockwise from base line
the third point is
returned by
variable in x3, y3 *)
CONST ANGLE_60_DEGREES = 3.14
/ 3.0;
VAR cos60, sin60, x1_r, x2_r,
y1_r,
y2_r, x3_r, y3_r: REAL;
BEGIN
IF clockwise THEN
RotatePoint(x1,
y1, x2,
y2, 60, x3, y3);
ELSE
RotatePoint(x1,
y1, x2,
y2, -60, x3, y3);
END;
Triangle(x1, y1, x2, y2, x3,
y3,
color, filled);
END EquilateralTriangle;
PROCEDURE CentralPoint(x1, y1,
x2, y2:
CARDINAL; VAR x3, y3: CARDINAL);
(* calculates central point
('middelpunt')
of the 2 given points *)
BEGIN
x3 := VAL(CARDINAL,
VAL(INTEGER, x1)
+ (VAL(INTEGER, x2) - VAL(INTEGER, x1)) / 2);
y3 := VAL(CARDINAL,
VAL(INTEGER, y1)
+ (VAL(INTEGER, y2) - VAL(INTEGER, y1)) / 2);
END CentralPoint;
TYPE DirectionEn = (LEFT, RIGHT);
PROCEDURE DrawNextLine(x1, y1, x2,
y2,
color: CARDINAL; direction: DirectionEn; VAR x3, y3: CARDINAL);
(* draws another line to the left or
right
of line x1,y1 - x2,y2
the new endpoint is
returned in
x3,y3 *)
VAR cos60, sin60, x1_r, x2_r,
y1_r,
y2_r, x3_r, y3_r: REAL;
BEGIN
x1_r := VAL(REAL, x1);
y1_r := VAL(REAL, y1);
x2_r := VAL(REAL, x2);
y2_r := VAL(REAL, y2);
IF direction = RIGHT THEN
x3_r := x2_r -
(y2_r -
y1_r);
y3_r := y2_r +
(x2_r -
x1_r);
ELSE
x3_r := x2_r +
(y2_r -
y1_r);
y3_r := y2_r -
(x2_r -
x1_r);
END;
IF x3_r > 0.0 THEN
x3 :=
VAL(CARDINAL,
x3_r);
ELSE
x3 := 0;
END;
IF y3_r > 0.0 THEN
y3 :=
VAL(CARDINAL,
y3_r);
ELSE
y3 := 0;
END;
Line(x2, y2, x3, y3, color);
END DrawNextLine;
PROCEDURE Distance(x1, y1, x2,
y2:
INTEGER): CARDINAL;
BEGIN
RETURN VAL(CARDINAL,
sqrt((VAL(REAL,
x1) - VAL(REAL, x2))*(VAL(REAL, x1) - VAL(REAL, x2)) + (VAL(REAL, y1) -
VAL(REAL, y2))*(VAL(REAL, y1) - VAL(REAL, y2))));
END Distance;
(**********************************************************************************************)
VAR x:
CHAR;
(*
variable-declarations
*)
x3,
y3,
x4,
y4:
CARDINAL;
BEGIN
WrLn;
IF NOT Init(1, 1 ,
SCREEN_SIZE,
SCREEN_SIZE) THEN
WrStr("Sorry,
graphics doesn't work");WrLn;
RETURN;
END;
EquilateralTriangle(200, 200, 400, 200, _clrGREEN, TRUE, TRUE, x3, y3);
(* Show graphics until
user
presses a key *)
WrStr("Press any key to
finish
the program");
x := RdKey();
WrLn; RdLn;
END S3.
X1
H1
H2
T1
Exercise
geheugen nodig: 3 x 4 + 5 x (3 x 4 + 2 x 4) = 112
alGeweest[nieuweNode-1]
:= TRUE;
VoegNodeToeAanPad(nieuweNode,
pad);
WrCard(nieuweNode, 0);WrStr(" - ");
IF nieuweNode = einde THEN
WrLn;WrStr("Pad
gevonden:
");PrintPad(pad);
IF
pad.lengte
<
kortste_pad.lengte
THEN
WrStr("
is
korter
dan
vorige!!");
kortste_pad
:=
pad;
END;
WrLn;
ELSE
FOR i := 1 TO AANTAL_NODES DO
IF
(graph[nieuweNode,
i]
>
0)
AND NOT alGeweest[i-1] THEN
Backtracking(alGeweest,
i,
pad);
END;
END;
END;
