Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

Förslag till lösningar – Övningar

Övning 1

Uppgift 1: (a) En identifierare börjar med en bokstav och följs sedan av den längsta möjliga sekvens bestående av bokstäver och siffror minus de reserverade orden (som finns på sid A2 i boken). Eftersom man i Modula skiljer på stora och små bokstäver och de reserverade orden alltid skrivs med stora bokstäver är följande teckensträngar korrekta Modula-2 identifierare:

       Module     module       mODULE     A12A
       A321       String       STRING     REAL
                  CARDINAL     f

(b) Det är olämpligt att använda identifierare som är fördefinierade, de som liknar reserverade ord och som finns i de biblioteksmoduler som är standard.

       Module       module     mODULe     String
       CARDINAL     STRING     REAL

Uppgift 2: Antingen är det en standardidentifierare eller så finns den deklarerad i programmet. Standardidentifierare för funktioner och procedurer finns på sidan A22 i boken. En identifierare kan deklareras i importlistan, deklararationslistan eller vara ett argument till en funktion eller procedur.

Uppgift 3: I biblioteksmodulen InOut finns följande procedurer definierade:

    Read(ch)       Write(ch)
    ReadString(s)  WriteString(s)
    ReadInt(i)     WriteInt(i,f)
    ReadCard(i)    WriteCard(c,f)

                   WriteOct(i,f)
                   WriteHex(i,f)
I RealIO finns:
    ReadReal(r, success)
    WriteReal(r, width:CARDINAL, decPlaces:INTEGER)
Uppgift 4: MODULE ovn1uppg4;
FROM InOut  IMPORT ReadCard,    WriteLn,    Write,
                 WriteString, WriteCard;
VAR distans, min, sek, totsek, medel : CARDINAL;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

BEGIN
WriteString("Ange distans(km): ");
ReadCard(distans);
WriteString("Tid(minuter): ");
ReadCard(min);
WriteString("Tid(sekunder): ");
ReadCard(sek);
totsek := min*60 + sek;
medel  := totsek DIV distans;
WriteString("Medelhastighet(min.sek/km): ");
WriteCard(medel DIV 60,3);
Write('.');
IF medel MOD 60 < 10
   THEN Write('0');
      WriteCard(medel MOD 60,1);
   ELSE WriteCard(medel MOD 60,2);
END;
WriteLn
END ovn1uppg4.

Uppgift 5:

TYP:  VÄRDE  VÄRDE  UTTRYCK

INTEGER  23           -3             i+12
CARDINAL      12           3000000000     c+10
REAL          1.0          13.4E-5        5.0 / 3.0
CHAR          '5'          40C            CHR(c)
BOOLEAN       TRUE         FALSE          (x=0) AND (y=0)
STRING        "hej"        'hej"hej"'

Uppgift 6: MODULE ovn1uppg6;
PROCEDURE INT2REAL(i:INTEGER):REAL;
BEGIN
  IF i>=0 THEN
    RETURN FLOAT(CARDINAL(i));
  ELSE
    RETURN -FLOAT(CARDINAL(-i));
  END;
END INT2REAL;
VAR i : INTEGER; r : REAL; c : CARDINAL;
BEGIN
r := INT2REAL(i)/FLOAT(c);
r := FLOAT(c);
i := i + INTEGER(c);
r := FLOAT(c) + 1.0;
END ovn1uppg6.

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

Uppgift 7: (a) Programmet

MODULE uppg7a;
FROM RealIO IMPORT ReadReal, WriteReal;
FROM InOut  IMPORT ReadInt, Read, WriteLn;
VAR r1,r2,r3 : REAL; i : INTEGER; c : CARDINAL;
    s : BOOLEAN;
BEGIN
ReadReal(r1,s);     ReadReal(r2,s);     ReadReal(r3,s);
WriteReal(r1,14,3); WriteReal(r2,14,3); WriteReal(r3,14,3);
WriteLn;
END uppg7a.

ger utskriften

      24.700  -3.300000E11         0.075

(b) Programmet

MODULE uppg7b;
FROM RealIO IMPORT ReadReal, WriteReal;
FROM InOut  IMPORT ReadInt, Read, WriteLn, WriteString,
                 WriteInt, Write;
VAR r1,r2,r3 : REAL; i : INTEGER; c : CHAR;
    s1, s2 : BOOLEAN;
BEGIN
ReadReal(r1,s1); ReadInt(i); Read(c); ReadReal(r3,s2);
WriteReal(r1,8,3);   WriteInt(i,8);
WriteString("-->");  Write(c);        WriteReal(r3,8,3);
WriteLn;
END uppg7b.

ger utskriften

24.700     -33-->0   0.075
Uppgift 8: MODULE ovn1uppg8;
FROM InOut IMPORT Read, WriteCard, WriteLn, Done;
VAR count : CARDINAL;
c : CHAR;
BEGIN
count := 0;
Read(c);
WHILE Done DO
IF c='x' THEN
    INC(count);
END;
Read(c);
END;
WriteCard(count,5); WriteLn;
END ovn1uppg8.

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

Uppgift 9: (a) MODULE ovn1uppg9a;
  FROM InOut IMPORT ReadCard, WriteCard, WriteLn,
                    WriteString;
  VAR i, n, tal : CARDINAL; max, min : CARDINAL;
      c : CHAR;
BEGIN
   WriteString("Antal tal: ");
   ReadCard(n);
   max := MIN(CARDINAL);
   min := MAX(CARDINAL);
   FOR i := 1 TO n DO
      ReadCard(tal);
      IF tal > max THEN max := tal END;
      IF tal < min THEN min := tal END;
   END;
   WriteCard(max,5); WriteCard(min,5); WriteLn;
END ovn1uppg9a.

(b) Ett sätt är att använda ett speciellt tal (t.ex. 0, -1 eller -348999) för att indikera slut på indata. Ett annat sätt är att man läser till filslut, dvs. tills variabeln Done i modulen InOut blir false.

(c) MODULE uppg9c;
  FROM InOut  IMPORT ReadCard, WriteCard, WriteLn, Done;
  FROM RealIO IMPORT WriteReal;
  VAR sum, antal, tal : CARDINAL;
      medel : REAL;
BEGIN
   sum := 0; antal := 0;
   LOOP
      ReadCard(tal);
      IF NOT Done THEN EXIT END;
      sum := sum + tal;
      antal := antal + 1;
   END;
   medel := FLOAT(sum) / FLOAT(antal);
   WriteReal(medel,0,2); WriteLn;
END uppg9c.

Det är inte speciellt lätt att ändra programmet så att det beräknar medianvärdet eftersom man då måste spara alla de inlästa talen i någon datastruktur. Man kan omöjligen veta hur många stora eller små tal som kommer i fortsättningen. Om man vill spara alla inlästa tal använder man lämpligtvis ett fält eller en länkad lista (mer om dessa senare).

Uppgift 10: (a) MODULE uppg10a;
  FROM InOut IMPORT WriteCard, WriteLn;
  VAR  i, sum : CARDINAL;
BEGIN

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

sum := 0;
FOR i:=2 TO 40 DO
    sum := sum + i*i + 2*i + 5
END;
WriteCard(sum,5); WriteLn;
END uppg10a.
(b) MODULE uppg10b;
FROM InOut   IMPORT WriteCard, WriteLn;
FROM RealIO  IMPORT ReadReal,  WriteReal;
FROM MathLib IMPORT Sqrt;
CONST sqrt2 = 1.4142;
VAR  eps, error, x : REAL;
     i : CARDINAL;
     s : BOOLEAN;
BEGIN
ReadReal(eps,s);
x := 1.0;
i := 0;
error := ABS(x - Sqrt(2.0));
WHILE error > eps DO
    x := (x + 2.0/x) / 2.0;
    error := ABS(x - Sqrt(2.0));
    INC(i)
END;
WriteCard(i,0); WriteLn;
END uppg10b.
Uppgift 11: MODULE uppg11;
FROM InOut IMPORT Done, Write, Read;
VAR ch  : CHAR;
big : BOOLEAN;
CONST diff = 32;
PROCEDURE isletter(c : CHAR) : BOOLEAN;
BEGIN
RETURN ('A'<= c) AND (c <= 'z')
END isletter;
BEGIN
big := TRUE;
LOOP
Read(ch);
IF NOT Done THEN EXIT END;
IF (ch='.') OR (ch='!') OR (ch='?') THEN    (* next character BIG *)
 Write(ch);
 big := TRUE

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

    ELSIF isletter(ch) THEN
       IF big THEN                              (* this character BIG *)
          Write(ch);
       ELSE
          Write(CHR(ORD(ch) + diff));
       END;
       big:=FALSE;
    ELSE
       Write(ch);
    END;
  END;
END uppg11.
Uppgift 12: MODULE uppg12;
(*** does not use ReadString, reads up to the next **)
(*** character following the number                **)
FROM InOut  IMPORT Done, Read, WriteInt, WriteLn, ReadString, WriteString;
FROM RealIO IMPORT WriteReal;
FROM SimpleIO IMPORT UndoRead;
VAR  ch : CHAR;
     i  : INTEGER;
     r  : REAL;
     s  : ARRAY[0..255] OF CHAR;
PROCEDURE ReadDigits(VAR res  : CARDINAL;
                     VAR digs : CARDINAL);
   PROCEDURE IsDigit(ch : CHAR) : BOOLEAN;
   BEGIN
     RETURN ('0' <= ch) AND (ch <= '9')
   END IsDigit;
   PROCEDURE DigitCard (ch : CHAR) : CARDINAL;
     CONST ORD0 = ORD('0');
   BEGIN
     RETURN ORD(ch) - ORD0
   END DigitCard;
BEGIN
   res := 0; digs:= 0;
   WHILE IsDigit(ch) AND Done DO
      res := 10 * res + DigitCard(ch);
      INC(digs);
      Read(ch);
   END;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

(*we have read one character to much*)
IF NOT (ch=12C) THEN
   UndoRead;
END;
END ReadDigits;
PROCEDURE ReadInt(VAR result : INTEGER);
CONST  EolCh         = 12C;
       TabCh         = 11C;
VAR    dgts, r  : CARDINAL;
       negative : BOOLEAN;
BEGIN
result := 0;
(** Get rid of space characters **)
REPEAT
   Read(ch);
UNTIL (ch # ' ')   AND (ch # TabCh) AND
      (ch # EolCh) OR  NOT Done;
(* Check sign **)
CASE ch
   OF '+' : negative := FALSE; Read(ch);
   |  '-' : negative := TRUE ; Read(ch);
   ELSE     negative := FALSE;
END;
ReadDigits(r,dgts);
result := INTEGER(r);
IF negative THEN result :=  -result  END;
END ReadInt;
PROCEDURE ReadReal(VAR r : REAL);
VAR i, e : INTEGER;
    f,dgts : CARDINAL;
PROCEDURE Exp10(e : INTEGER) : REAL;
   VAR i : CARDINAL;
       r : REAL;
BEGIN
   r:=1.0;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

   IF e >= 0
      THEN FOR i:=1 TO CARDINAL(e)  DO r:=r * 10.0 END
      ELSE FOR i:=1 TO CARDINAL(-e) DO r:=r / 10.0 END
   END;
   RETURN r
END Exp10;
BEGIN
(** read integer **)
ReadInt(i);
r := FLOAT(i);
(** '.' ???? **)
Read(ch);;
IF ch = '.' THEN (*** Read fraction ***)
   Read(ch);
   ReadDigits(f,dgts);
   r := r + FLOAT(f) / Exp10(dgts)
ELSIF (** 'E' ???? **) ch='E' THEN (*** Read exponent ***)
   ReadInt(e);
   r := r* Exp10(e);
ELSIF NOT (ch=12C) THEN
  UndoRead;
END;
END ReadReal;
BEGIN
 ReadInt(i); ReadString(s); WriteInt(i,0); WriteString(s) ;WriteLn;
 ReadInt(i); ReadString(s); WriteInt(i,0); WriteString(s) ;WriteLn;
 ReadInt(i); ReadString(s); WriteInt(i,0); WriteString(s) ;WriteLn;
 ReadReal(r); ReadString(s); WriteReal(r,10,-2); WriteString(s) ;WriteLn;
 ReadReal(r); ReadString(s); WriteReal(r,10,-2); WriteString(s) ;WriteLn;
 ReadReal(r); ReadString(s); WriteReal(r,10,-2); WriteString(s) ;WriteLn;
END uppg12.
Uppgift 13: MODULE uppg13;
 FROM InOut  IMPORT EOL, Done, ReadCard, Write,
                    WriteLn, WriteCard;
 FROM RealIO IMPORT ReadReal,  WriteReal;
 CONST inc = 1.08;
 VAR ok    : BOOLEAN;
     artnr : CARDINAL;
     price : REAL;
BEGIN

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

LOOP
ReadCard(artnr);
IF NOT Done THEN EXIT END;
ReadReal(price, ok);
WriteCard(artnr,5);
Write(' ');
WriteReal(price*inc,5,2);
WriteLn;
END;
END uppg13.

Om indata plötsligt får formen DDDD DD:DD så kan man modifiera programmet genom att till exempel skriva en egen version av ReadReal proceduren.

Uppgift 14: MODULE uppg14;
FROM InOut IMPORT EOL, Done, Read, WriteCard, WriteLn;
CONST TAB = 13C;
VAR ch : CHAR;
 wm : BOOLEAN;
 c,w,l : CARDINAL;
BEGIN
wm := TRUE;
c := 0; w := 0; l := 0;
LOOP
Read(ch);
IF NOT Done THEN EXIT END;
(* characters *)
INC(c);
(* words *)
IF wm THEN
   IF (ch#' ') AND (ch#EOL) AND (ch#TAB) THEN (** new word **)
      INC(w);
      wm := FALSE;
   END
ELSE
   IF (ch=' ') OR (ch=EOL) OR (ch=TAB) THEN (** end of word **)
      wm := TRUE;
   END
END;
(* lines *)
IF ch=EOL
   THEN INC(l)
END
END;
WriteCard(l,8); WriteCard(w,8); WriteCard(c,8);

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

WriteLn
END uppg14.
Uppgift 15: MODULE uppg15;
FROM InOut IMPORT EOL, Read, Done, WriteString, WriteLn;
CONST MaxStr = 200;
      EoStr  = 0C;
TYPE STRING = ARRAY [0..MaxStr] OF CHAR;
     CharType = (Vowel, Consonant, Blank, Other);
VAR  instr, outstr : STRING;
PROCEDURE ReadLine(VAR s:ARRAY OF CHAR);
   VAR i:CARDINAL;
       c:CHAR;
BEGIN
   i:=0;
   LOOP
      IF (i=HIGH(s)) THEN EXIT; END;
      Read(c);
      IF NOT Done OR (c=EOL) THEN EXIT; END;
      s[i]:=c;
      INC(i);
   END;
   s[i]:=EoStr;
END ReadLine;
PROCEDURE torobber (VAR in,out : ARRAY OF CHAR);
   VAR i,o : CARDINAL;
   PROCEDURE TypeOfChar(ch : CHAR) : CharType;
   BEGIN
       CASE ch
        OF 'a','o','u','}','e','i',
           'y','{','|'               : RETURN Vowel;
        |  'b','c','d','f','g','h',
           'j','k','l','m','n','p',
           'q','r','s','t','v','x',
           'z'                       : RETURN Consonant;
        |  ' '                       : RETURN Blank;
        ELSE                           RETURN Other;
       END;
   END TypeOfChar;
BEGIN

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

i:=0; o:=0;
WHILE (in[i] # EoStr) AND (o+2< HIGH(out)) DO
   CASE TypeOfChar(in[i])
     OF Consonant :        out[o]   := in[i];
                           out[o+1] := 'o';
                           out[o+2] := in[i];
                           INC(o,3);
     |  Vowel, Blank :     out[o]   := in[i];
                           INC(o);
     ELSE;
   END;
   INC(i);
END;
out[o] := EoStr;
END torobber;
BEGIN
LOOP
ReadLine(instr);
IF NOT Done THEN EXIT END;
torobber(instr,outstr);
WriteString(outstr); WriteLn;
END
END uppg15.

Övning 2

Uppgift 1: MODULE uppg1;
FROM InOut   IMPORT WriteCard, WriteLn;
FROM MathLib IMPORT Sqrt;
VAR i : CARDINAL;
PROCEDURE isprime (n : CARDINAL) : BOOLEAN;
VAR i,upto : CARDINAL;
BEGIN
 IF n=1 THEN RETURN FALSE;
 ELSIF n=2 THEN RETURN TRUE;
 END;
 upto := TRUNC(Sqrt(FLOAT(n)))+1;
 FOR i:=2 TO upto DO
   IF n MOD i =0 THEN RETURN FALSE;END;
 END;
 RETURN TRUE;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

END isprime;
BEGIN
FOR i:=1 TO 50 DO
   IF isprime(i) THEN WriteCard(i,0); WriteLn END;
END;
END uppg1.
Uppgift 2: MODULE uppg2;
FROM InOut IMPORT WriteCard, WriteLn;
VAR x,y : CARDINAL;
PROCEDURE swap (VAR c1,c2 : CARDINAL);
   VAR z : CARDINAL;
BEGIN
   z:=c1; c1:=c2; c2:=z
END swap;
BEGIN
x:=10; y:=20;
swap(x,y);
WriteCard(x,5); WriteCard(y,5);
WriteLn;
END uppg2.
Uppgift 3: MODULE uppg3;

(****** a ******)
PROCEDURE sum (x : ARRAY OF CARDINAL) : CARDINAL;
VAR s, i : CARDINAL;
BEGIN
s := 0;
FOR i:= 0 TO HIGH(x) DO
    s := s + x[i]
    (** s = SUM from j=0 to i OF x[j] **)
END;
RETURN s
END sum;

(****** b ******)
PROCEDURE sumarray (x,y : ARRAY OF CARDINAL;
 VAR z : ARRAY OF CARDINAL);
VAR i : CARDINAL;
BEGIN
FOR i:= 0 TO HIGH(x) DO
    z[i] := x[i] + y[i]

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

       (** z[k] = x[k] + y[k], for 0 <= k <= i **)
   END;
END sumarray;

(****** c ******)
PROCEDURE innerprod (x,y : ARRAY OF CARDINAL) : CARDINAL;
   VAR i,r : CARDINAL;
BEGIN
   r:=0;
   FOR i:= 0 TO HIGH(x) DO
       r := r + x[i]*y[i]
       (** r = SUM FROM k=1 TO i OF x[k] * y[k] **)
   END;
   RETURN r
END innerprod;

(****** d ******)
PROCEDURE maxmin (x : ARRAY OF CARDINAL;
  VAR maxi, mini : CARDINAL);
   VAR i,max,min : CARDINAL;
BEGIN
   max := x[0]; min := x[0];
   maxi:=0; mini:=0;
   FOR i:=1 TO HIGH(x) DO
       IF x[i] > max THEN
          max := x[i]; maxi:=i;
       ELSIF x[i] < min THEN
          min := x[i]; mini:=i;
       END;
   END;
END maxmin;
BEGIN
END uppg3.
Uppgift 4: MODULE uppg4;
FROM InOut IMPORT WriteCard, WriteLn, WriteString;
CONST MaxStr = 100;
      EosCh  = 0C;
TYPE STRING = ARRAY [0..MaxStr] OF CHAR;
VAR  x, y, z : STRING;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

(****** a ******)
PROCEDURE length (str : ARRAY OF CHAR) : CARDINAL;
VAR lgt : CARDINAL;
BEGIN
lgt := 0;
WHILE (lgt <= HIGH(str)) AND (str[lgt] # EosCh) DO
   INC(lgt);
END;
RETURN lgt
END length;

(****** b ******)
PROCEDURE append (VAR x : ARRAY OF CHAR;
               suff  : ARRAY OF CHAR);
VAR i,j : CARDINAL;
BEGIN
i:=0;
WHILE  (i <= HIGH(x)) AND (x[i] # EosCh) DO
    INC(i);
END;
j:=0;
WHILE  (i<=HIGH(x)) AND  (j<=HIGH(suff)) AND (suff[j] # EosCh) DO
    x[i] := suff[j];
    INC(j); INC(i);
END;
IF i< HIGH(x) THEN x[i] := EosCh END;
END append;

(****** c ******)
PROCEDURE stringeq (x,y : ARRAY OF CHAR) : BOOLEAN;
VAR i : CARDINAL;
BEGIN
i := 0;
WHILE (i<=HIGH(x)) AND (i<=HIGH(y)) AND
      (x[i]#EosCh) AND (y[i]#EosCh) AND
      (x[i]=y[i])
DO
   INC(i);
END;
RETURN  ((i=HIGH(x)) OR (x[i]=EosCh)) AND
        ((i=HIGH(y)) OR (y[i]=EosCh));
END stringeq;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

(****** d ******)
PROCEDURE delete (VAR x : ARRAY OF CHAR;
               st, en : CARDINAL);
(** delete from position st (inclusive) up to en (exclusive) **)
VAR i : CARDINAL;
BEGIN
(*** require that en > st ***)
i := 0;
WHILE (x[en+i]#EosCh) DO
   x[st+i] := x[en+i];
   INC(i)
END;
x[st+i] := EosCh;
END delete;

(****** e ******)
PROCEDURE insert (str   : ARRAY OF CHAR;
               VAR x : ARRAY OF CHAR;
               inx   : CARDINAL);
(** insert str from pos inx in x ***)
VAR l,j : CARDINAL;
BEGIN
(*** require that inx > 0 and < HIGH(x)              ***)
(*** make room for str in x from pos inx to inx+l    ***)
l := length(str);
j := HIGH(x);
WHILE (j <= inx+l) AND (j-l >= 0) DO
   x[j] := x[j-l];
   DEC(j)
END;
(*** insert the string ***)
FOR j:=0 TO l-1 DO
   IF (inx+j >= 0) AND (inx+j <= HIGH(x))
      THEN x[inx+j] := str[j]
   END
END
END insert;
BEGIN
x := "kent"; y := "petersson";
WriteCard(length(x),10);
WriteCard(length(y),10);
WriteLn;
append(x," ");  append(x,y);
WriteString(x);
WriteLn;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

   IF stringeq(x,"kentpetersson") THEN WriteString("equal")
                                  ELSE WriteString("unequal")
   END;
   WriteLn;
   delete(x,3,8); WriteString(x); WriteLn;
   insert("april",x,4); WriteString(x); WriteLn;
END uppg4.
Uppgift 5: MODULE uppg5;
FROM RandomModule IMPORT Random;
FROM InOut        IMPORT WriteCard, Write, WriteLn;
CONST max = 30;
VAR  x : ARRAY [1..max] OF CARDINAL;
VAR  i : CARDINAL;
PROCEDURE WriteArray(x : ARRAY OF CARDINAL);
VAR i : CARDINAL;
BEGIN
   FOR i:=0 TO HIGH(x) DO
       WriteCard(x[i],0); Write(' ');
   END;
   WriteLn
END WriteArray;
PROCEDURE RandomCard() : CARDINAL;
BEGIN
   RETURN TRUNC(100.0 * Random());
END RandomCard;
PROCEDURE sort (VAR x : ARRAY OF CARDINAL);
  VAR i : CARDINAL;
  PROCEDURE insert (n : CARDINAL;
                    VAR x : ARRAY OF CARDINAL;
                    l : CARDINAL);
     VAR i,j  : CARDINAL;
  BEGIN
     (*** the array x[0..l-1] is ordered                         **)
     (*** insert the element n in the right position in x[0..l]  **)
     i := 0;
     (** the right position is i **)
     WHILE (i<l) AND (x[i]<n) DO
        INC(i);
     END;
     (** make room **)
     j:= 1;
     WHILE INTEGER(l-j) >= INTEGER(i) DO

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

  x[l-j+1] := x[l-j];
  INC(j)
END;
x[i] := n;
END insert;
BEGIN
FOR i:=1 TO HIGH(x) DO
(** the array from 0 .. i-i is ordered **)
insert(x[i],x,i);
(** the array from 0 .. i is ordered   **)
END;
END sort;
BEGIN
FOR i:=1 TO max DO x[i] := RandomCard(); END;
WriteArray(x);
WriteLn;
sort(x);
WriteArray(x);
END uppg5.

Uppgift 6: MODULE uppg6;
FROM SORT  IMPORT sort;
FROM InOut IMPORT Write, WriteCard, WriteLn;
VAR i : CARDINAL;
 x : ARRAY[1..20] OF CARDINAL;
PROCEDURE find (n : CARDINAL;
             x : ARRAY OF CARDINAL) : BOOLEAN;
VAR i : CARDINAL;
BEGIN
FOR i:=0 TO HIGH(x) DO
    IF x[i] = n THEN RETURN TRUE END
END;
RETURN FALSE;
END find;
PROCEDURE BinSearch(n : CARDINAL;
                 x : ARRAY OF CARDINAL) : BOOLEAN;
VAR i : CARDINAL;
    m, l, h : CARDINAL;
BEGIN

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

   (** search for i in x[l]..x[h] ; h>l      **)
   l := 0; h := HIGH(x);
   (** the left middle **)
   WHILE h >= l DO
      m := (h+l) DIV 2;
      IF x[m]=n
         THEN RETURN TRUE
      ELSIF x[m]>n
         THEN h := m-1
      ELSE
              l := m+1
      (** search for i in x[l]..x[m-1]       **)
      (**         or in x[m+1]..x[h]         **)
      END
   END;
   RETURN FALSE
END BinSearch;
BEGIN
FOR i:=1 TO 20 DO x[i] := i*2-3 END;
FOR i:=1 TO 40 DO
    WriteCard(i,0);
    IF find(i,x) THEN Write('F') END;
    IF BinSearch(i,x) THEN Write('B') END;
    Write(' ');
END;
WriteLn;
END uppg6.
Uppgift 7: MODULE uppg7;
FROM RandomModule IMPORT Random;
FROM SORT         IMPORT sort;
FROM InOut        IMPORT Write, WriteCard, WriteLn;
FROM RealIO       IMPORT WriteReal;
CONST max = 19;
VAR i : CARDINAL;
VAR x : ARRAY[1..max] OF CARDINAL;
PROCEDURE RandomCard() : CARDINAL;
BEGIN
   RETURN TRUNC(100.0 * Random());
END RandomCard;
PROCEDURE WriteArray(x : ARRAY OF CARDINAL);
VAR i : CARDINAL;
BEGIN

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

   FOR i:=0 TO HIGH(x) DO
       WriteCard(x[i],0); Write(' ');
   END;
   WriteLn
END WriteArray;
PROCEDURE median(VAR x : ARRAY OF CARDINAL) : REAL;
   VAR m : CARDINAL;
BEGIN
    sort(x);
    IF ODD(HIGH(x))
       THEN (** even number of elements **)
            m := (HIGH(x)+1) DIV 2;
            RETURN FLOAT(x[m])
       ELSE
            m := (HIGH(x)+1) DIV 2;
            RETURN FLOAT(x[m-1]+x[m]) / 2.0
    END
END median;
BEGIN
   FOR i:=1 TO max DO x[i] := RandomCard(); END;
   WriteArray(x);
   WriteReal(median(x),0,5);
   WriteLn;
END uppg7.

Uppgift 8: En modul för listor kan implementeras genom följande två delar. Först definitionsmodulen (Observera att vi använder funktioner som returnerar fält vilket inte är standard Modula!):

DEFINITION MODULE ILIST;
CONST MaxList=25;
TYPE IList=RECORD
          lst:ARRAY[0..MaxList] OF INTEGER;
          lgt:CARDINAL;
         END;
PROCEDURE cons (e : INTEGER; l : IList) : IList;
PROCEDURE nil(): IList;
PROCEDURE hd (l : IList) : INTEGER;
PROCEDURE tl (l : IList) : IList;
PROCEDURE WriteIList (l : IList);
END ILIST.

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

Sedan kommer implementeringsmodulen:

IMPLEMENTATION MODULE ILIST;
FROM InOut IMPORT Write, WriteInt, WriteString, WriteLn;

PROCEDURE cons (e : INTEGER; l : IList) : IList;
BEGIN
   WITH l DO
      IF lgt = MaxList
         THEN WriteString("Too long list");
              WriteLn;
      END;
      INC(lgt);
      lst[lgt]:=e;
   END;
   RETURN l;
END cons;
PROCEDURE nil(): IList;
   VAR r : IList;
BEGIN
   WITH r DO
      lgt:=0;
   END;
   RETURN r;
END nil;
PROCEDURE hd (l : IList) : INTEGER;
BEGIN
   WITH l DO
      IF lgt = 0
         THEN WriteString("hd applied to []");
              WriteLn;
      END;
      RETURN lst[lgt];
   END;
END hd;
PROCEDURE tl (l : IList) : IList;
BEGIN
   WITH l DO
      IF lgt = 0
         THEN WriteString("tl applied to []");
              WriteLn;
      END;
      DEC(lgt);

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

         RETURN l;
      END;
   END tl;
   PROCEDURE null (l : IList) : BOOLEAN;
   BEGIN
      RETURN l.lgt = 0;
   END null;
   PROCEDURE WriteIList (l : IList);
      VAR i : CARDINAL;
   BEGIN
      WITH l DO
         Write('[');
         FOR i:= lgt TO 2 BY -1 DO
            WriteInt(lst[i],0);
            Write(',');
         END;
         WriteInt(lst[1],0);
         Write(']');
      END;
   END WriteIList;
END ILIST.

Om man implementerar lista m h a fält så använder man, av effektivitetsskäl, normalt inte funktionerna cons och tail utan man har procedurer (insert, remove) med VAR-parametrar.

Övning 3

Uppgift 1: Man kan till exempel beskriva varje punkt med ett värde som är antingen on eller off.

       TYPE B  = (on, off);

eller om man har en färgskärm

       TYPE Color = (white, red, green, blue, ...);

Ett fönster kan då representeras av ett värde av typen (antag att konstanterna xmax och ymax som definierar storleken av fönstret redan är definierade)

       TYPE Window  = ARRAY [0..xmax] [0..ymax] OF B;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

och en punkt i fönstret av ett värde av typen

 TYPE Point = RECORD
                x : [0..xmax];  y : [0..ymax]
              END;

Man kan till exempel tänka sig följande uppsättning operationer:

 PROCEDURE Clear  (VAR w : Window);
 PROCEDURE Line   (VAR w : Window; from,to : Point);
 PROCEDURE Circle (VAR w : Window; center : Point;
                   rad : CARDINAL);
 PROCEDURE Text   (VAR w : Window; where  : Point;
                   txt : String);

Uppgift 2: MODULE uppg2;
FROM InOut  IMPORT WriteCard, WriteLn, WriteString, Write;
VAR i : CARDINAL;
 x : ARRAY [1..30] OF CARDINAL;
 maxix,ant : CARDINAL;
PROCEDURE max(x:ARRAY OF CARDINAL;VAR maxx,ant: CARDINAL);
VAR i : CARDINAL;
BEGIN
maxx := x[0];
ant:=0;
FOR i:=1 TO HIGH(x) DO
    IF x[i]>maxx THEN
       maxx:=x[i];
    END;
END;
FOR i:=0 TO HIGH(x) DO
   IF x[i]=maxx THEN
      INC(ant);
   END;
END;
END max;
PROCEDURE WriteArray(x : ARRAY OF CARDINAL);
VAR i : CARDINAL;
BEGIN
FOR i:=0 TO HIGH(x) DO
    WriteCard(x[i],0); Write(' ');
END;
WriteLn

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

   END WriteArray;
   BEGIN
      FOR i:=1 TO 30 DO x[i] := (4*i+3) MOD 22 END;
      WriteArray(x);
      max(x,maxix,ant);
      WriteString("max: "); WriteCard(maxix,1);
      WriteLn;
      WriteString("antal: "); WriteCard(ant,1);
      WriteLn;
END uppg2.

Uppgift 3: Tabellen kan implementeras genom definitionsmodulen: (som tyvärr påminner lite för mycket om lab2)

DEFINITION MODULE TABLE;
????
   PROCEDURE empty (VAR t : Table);
   PROCEDURE insert (VAR t : Table; s : String);
   PROCEDURE find (VAR t : Table; s : String) : BOOLEAN;
   PROCEDURE delete (VAR t : Table; s : String);
END TABLE.

implementeringsmodulen: (denna också)

IMPLEMENTATION MODULE TABLE;
????
END TABLE.

Man kan sedan använda denna modul som till exempel i följande program.

MODULE uppg3;
   FROM  TABLE  IMPORT Table, String, insert, find, empty;
   FROM  InOut  IMPORT WriteString, WriteLn;
   VAR   t : Table;
   PROCEDURE ResWord (s : String);
   BEGIN
       IF find(t, s)  THEN WriteString("Reserved Word"); WriteLn;
                      ELSE WriteString("Identifier");    WriteLn;
       END;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

 END ResWord;
BEGIN
 empty(t);
 insert(t, "MODULE");         insert(t, "PROCEDURE");
 insert(t, "BEGIN");          insert(t, "END");
 insert(t, "WHILE");
 ResWord("BEGIN");
 ResWord("ident");
 ResWord("begin");
END uppg3.
Uppgift 4: MODULE uppg4;
FROM InOut IMPORT WriteString, WriteLn;
TYPE String     = ARRAY [0..100] OF CHAR;
TYPE StatusType = (grad, undergrad);
TYPE Person     = RECORD
                    name : String;
                    CASE status : StatusType
                    OF grad :     age : CARDINAL;
                    |  undergrad: weight : REAL;
                    END;
                  END;
VAR ann, kent : Person;
BEGIN
kent.name   := "Kent Petersson";
kent.status := undergrad;
kent.weight := 69.3;
ann.name    := "Ann Persson";
ann.status  := grad;
ann.age     := 36;
kent.status := grad;
kent.age    := 41;
IF kent.weight = 41.99 THEN WriteString('Correct') END;
IF ann.weight # 69.3 THEN WriteString('Incorrect') END;
WriteLn;
END uppg4.

Observera att utskriften av detta program blir Incorrect. Modula systemet kontrollerar inte att en post har rätt variant (i alla fall inte det som finns på Sun datorerna).

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

Uppgift 5: Första förslaget till lösning är:

MODULE uppg51;
MODULE SYMBOL;
  EXPORT Symbol, ReadSymbol, WriteSymbol, NewLevel, ReadError;
  TYPE Symbol  = ...
  PROCEDURE ReadSymbol (VAR sy : Symbol);
  BEGIN
  END ReadSymbol;
  PROCEDURE WriteSymbol (level : CARDINAL; sy : Symbol);
  BEGIN
  END WriteSymbol;
  PROCEDURE NewLevel (level : CARDINAL; sy : Symbol) : CARDINAL;
  BEGIN
  END NewLevel;
END SYMBOL;
PROCEDURE init();
BEGIN
END init;
VAR sy    : Symbol;
VAR level : CARDINAL;
BEGIN
init();
LOOP
   ReadSymbol(sy);
   IF ReadError THEN EXIT END;
   level := NewLevel(level,sy);
   WriteSymbol(level,sy);
END;
END uppg51.

Detta utvecklas sedan till:

MODULE uppg52;
CONST EOS = ...
TYPE  String = ...
MODULE SYMBOL;
  IMPORT EOS, String;
  EXPORT Symbol, ReadSymbol, WriteSymbol, NewLevel, ReadError;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

TYPE SymType = (resword, id, int, symbol, comment, string, nl);
TYPE Symbol  = RECORD
               before : String;
               symstr : String;
               type   : SymType;
            END;
TYPE Reswords = (if,then, else, end, while, do , ... );
VAR  ch : Char;  (*** the last read character ***)
PROCEDURE wresword(str : String) : Reswords;
(** translates a reserved word in a string to an element **)
(** of an enumeration type                               **)
BEGIN
END wresword;
PROCEDURE isresword(str : String) : BOOLEAN;
(** checks if a string is a reserved word                **)
BEGIN
END isresword;
PROCEDURE ReadSymbol (VAR sy : Symbol);
PROCEDURE readwhite(VAR str : STRING);
PROCEDURE isletter(ch : Char) : BOOLEAN;
PROCEDURE isdigit (ch : Char) : BOOLEAN;
PROCEDURE readstr(VAR str : String);
PROCEDURE readid (VAR str : String);
PROCEDURE readnum(VAR str : String);
PROCEDURE readcom(VAR str : String);
BEGIN
readwhite(sy.before);
IF isletter(ch)
   THEN
      readstring(sy.symstr);
      IF isresword(sy.symstr)
         THEN sy.type = resword
         ELSE sy.type = id
      END;
ELSIF isdigit(ch)
   THEN
      readnum(sy.symstr);
      sy.type := num;
ELSIF (ch = '"') OR (ch = "'")
   THEN
      readstr(sy.symstr);
      sy.type := string;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

   ELSIF ch = '('
      THEN Read(ch)
           IF ch='*'
              THEN readcom(sy.symstr);
                   sy.type := com;
           END;
      ELSE  sy.symstr := "(";
            sy.type := symbol;
   ELSIF ch = EOL
      THEN sy.symstr := EOL
           sy.type := nl;
           Read(ch);
   ELSE
         sy.symstr[0] := ch;
         sy.symstr[1] := EOS;
         Read(ch);
   END;
END ReadSymbol;
PROCEDURE WriteSymbol (level : CARDINAL; sy : Symbol);
   PROCEDURE Indent(level : CARDINAL);
BEGIN
  IF sy.type = resword
     THEN CASE wresword(sy.symstr)
          OF  (** reserved words that always begin a new line **)
              ....:   WriteLn;
                      Indent(level);
                      WriteString(sy.symstr);
          ELSE        WriteString(sy.before);
                      WriteString(sy.symstr);
          END;
  ELSIF sy.type = nl
     THEN ...
  ELSE  ...
  END;
END WriteSymbol;
PROCEDURE NewLevelBefore (level : CARDINAL; sy : Symbol) : CARDINAL;
BEGIN
  IF sy.type = resword
     THEN CASE wresword(sy.symstr)
          OF (** decrease indent before the symbol **)
             ...:       RETURN(level-1);
          ELSE          RETURN(level);
          END;
     ELSE RETURN level;
  END;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

  END NewLevelBefore;
  PROCEDURE NewLevelAfter (level : CARDINAL; sy : Symbol) : CARDINAL;
  BEGIN
    IF sy.type = resword
       THEN CASE wresword(sy.symstr)
            OF (** increase indent after the symbol **)
               ...:       RETURN(level+1);
            ELSE          RETURN(level);
            END;
       ELSE RETURN level;
    END;
  END NewLevelAfter;
BEGIN
  Read(ch);
END SYMBOL;
PROCEDURE init()
BEGIN
END init;
VAR sym : Symbol;
VAR level : CARDINAL;
BEGIN
init();
LOOP
   ReadSymbol(sy);
   IF ReadError THEN EXIT END;
   level := NewLevelBefore(level,sym);
   WriteSymbol(level,sym);
   level := NewLevelAfter(level,sym);
END;
END uppg52.

Övning 4

Uppgift 1: Om man löser uppg c genom att först göra insert (a) på alla element i l1 och sen på alla element i l2 så anänder man sig inte av att listorna är sorterade och resultatet blir en ineffektivare algoritm.

******** a ********
PROCEDURE insert(VAR l:IList;n:INTEGER);
  VAR k:IList;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

BEGIN
IF (l=NIL) OR (n<=l^.n) THEN
k:=l;
ALLOCATE(l,SIZE(Node));
l^.n:=n;
l^.next:=k;
ELSE
insert(l^.next,n);
END;
END insert;

******** b ********
PROCEDURE length(l:IList):CARDINAL;
VAR len:CARDINAL;
BEGIN
len:=0;
WHILE l#NIL DO
INC(len);
l:=l^.next;
END;
RETURN len;
END length;

******** c ********
PROCEDURE merge(l1,l2:IList):IList;
VAR l:IList;
BEGIN
IF (l1=NIL) AND (l2=NIL) THEN
RETURN NIL;
ELSE
ALLOCATE(l,SIZE(Node));
IF (l2=NIL) OR (l1#NIL) AND (l1^.n<=l2^.n) THEN
  l^.n:=l1^.n;
  l^.next:=merge(l1^.next,l2);
ELSE
  l^.n:=l2^.n;
  l^.next:=merge(l1,l2^.next);
END;
RETURN l;
END;
END merge;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

******** d ********
PROCEDURE concat(VAR l1:IList;l2:IList);
  VAR l:IList;
BEGIN
  IF l1=NIL THEN
    l1:=l2;
  ELSE
    l:=l1;
    WHILE l^.next#NIL DO
      l:=l^.next;
    END;
    l^.next:=l2;
  END;
END concat;

******** e ********
PROCEDURE backwards(l:IList);
BEGIN
  IF l#NIL THEN
    backwards(l^.next);
    WriteInt(l^.n,4);
  END;
END backwards;
Uppgift 2: DEFINITION MODULE IntStack;
TYPE IStack;
PROCEDURE init(VAR s:IStack);
PROCEDURE empty(s:IStack):BOOLEAN;
PROCEDURE push(VAR s:IStack;n:INTEGER);
PROCEDURE pop(VAR s:IStack);
PROCEDURE top(s:IStack):INTEGER;
END IntStack.

IMPLEMENTATION MODULE IntStack;
FROM Storage IMPORT ALLOCATE,DEALLOCATE;
FROM InOut IMPORT WriteString;
TYPE IStack=POINTER TO Node;
     Node=RECORD
    n:INTEGER;
    next:IStack;
  END;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

PROCEDURE init(VAR s:IStack);
BEGIN
  s:=NIL;
END init;
PROCEDURE empty(s:IStack):BOOLEAN;
BEGIN
  RETURN s=NIL;
END empty;
PROCEDURE push(VAR s:IStack;n:INTEGER);
  VAR k:IStack;
BEGIN
  k:=s;
  ALLOCATE(s,SIZE(Node));
  s^.n:=n;
  s^.next:=k;
END push;
PROCEDURE pop(VAR s:IStack);
  VAR k:IStack;
BEGIN
  IF s=NIL THEN
    WriteString("pop - stack tom");
  ELSE
    k:=s;
    s:=s^.next;
    DEALLOCATE(k,SIZE(INTEGER));
  END;
END pop;
PROCEDURE top(s:IStack):INTEGER;
BEGIN
  IF s=NIL THEN
    WriteString("top - stack tom");
    RETURN 0;
  END;
  RETURN s^.n;
END top;
END IntStack.

Uppgift 3: Definitionsmodulen är samma som i uppg2.

IMPLEMENTATION MODULE IntStack;
FROM Storage IMPORT ALLOCATE,DEALLOCATE;

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

FROM InOut IMPORT WriteString;
CONST max=100;
TYPE stack=RECORD
             f:ARRAY[1..max] OF INTEGER;
             ant:CARDINAL;
           END;
TYPE IStack=POINTER TO stack;
PROCEDURE init(VAR s:IStack);
BEGIN
  ALLOCATE(s,SIZE(stack));
  s^.ant:=0;
END init;
PROCEDURE empty(s:IStack):BOOLEAN;
BEGIN
  RETURN s^.ant=0;
END empty;
PROCEDURE push(VAR s:IStack;n:INTEGER);
BEGIN
  IF s^.ant=max THEN
    WriteString("push - stack full");
  ELSE
    INC(s^.ant);
    s^.f[s^.ant]:=n;
  END;
END push;
PROCEDURE pop(VAR s:IStack);
BEGIN
  IF s^.ant=0 THEN
    WriteString("pop - stack tom");
  ELSE
    DEC(s^.ant);
  END;
END pop;
PROCEDURE top(s:IStack):INTEGER;
BEGIN
  IF s^.ant=0 THEN
    WriteString("top - stack tom");
    RETURN 0;
  END;
  RETURN s^.f[s^.ant];

Institutionen för Datavetenskap ThomasH Övning

VT-94 inn01-b 19/4-94

               END top;
             END IntStack.