Solutions TOPIC M: Recursion.

Contents :

   Recursion.

Exercises :


D1: Arrow.

Exercise

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

Exercise


S2

Exercise

 


S4: Backtracking

Exercise

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.

Exercise

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

Exercise


H1

Exercise


H2

Exercise


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;