Informatik I

WS 2000/2001, Prof. Jürg Gutknecht

Konvergenzübungen - Lösunsgsvorschlag

Aufgabe 1. Die nicht gelistete Fälle sind korrekt.

  si = ORD(CHR(71))

falsch: ORD liefert ein INTEGER zurüruck

  i := 1 + ENTIER(r)

falsch: ENTIER liefert LONGINT zurüruck

  si := SHORT(ENTIER(3.14))

falsch: SHORT von LONGINT ist INTEGER

  b := 3 < MAX(REAL) OR li > i + 4

falsch: OR bindet särker als die Relationsoperatoren. "MAX(REAL) OR li" wird als SimpleExpression zusammengruppiert.

  ch := "this is true"

falsch: ch ist ein CHAR, "this is true" ist eine Stringkonstante

  i := 4 + CHR("a")

falsch: CHR nimmt ein Zahl als Parameter und liefert ein CHAR zurück

Aufgabe 2.

(a.) X * Y

(b.) x := x-1

Aufgabe 3.

M.i ist in M, C sichtbar
M.j ist in M, A, C sichtbar
M.A ist in M, A, B, C sichtbar
M.A.i ist in A sichbar
M.A.B ist in A, B sichtbar
M.A.B.i ist in B sichtbar
M.A.B.j ist in B sichtbar
M.A.B.k ist in B sichtbar
M.C ist in C, M sichtbar

Fehler: [ B* ] eine lokale Prozedur darf nicht exportiert werden.

i = 4; j = 2;

Aufgabe 4. Die zweite und die letzte Prozedursignaturen sind legal

Aufgabe 5. Die nicht gelistete Fälle sind korrekt.

  Root(1, 3, 4, x1, x2, x3, x4)

die VAR-Parametern müssen REAL-Variablen sein

  Sin(3.14159)

Sin ist eine Funktion

  i := Min(x, x1)

x ist ein REAL, es wird ein INTEGER erwartet

  Root(a, b, c, 3, 4, 5, 6)

die VAR-Parametern müssen REAL-Variablen sein

Aufgabe 6. Sonst wird die übergebene Variable nicht modifiziert

Aufgabe 7.

  COPY(src, dst)

Aufgabe 8.

(a.)

  PROCEDURE Length(x: ARRAY OF CHAR): INTEGER;
    VAR i: INTEGER;
  BEGIN
    i := 0; WHILE x[i] # 0X DO INC(i) END;
    RETURN i
  END Length;

  6  7  5  32

Aufgabe 9.

  Proc2: 0

  Proc4: 1

  Proc5: 0

Die Variable global in Proc5 is local definiert, während Proc3 die globale Variable ändert

Aufgabe 10.

  5  25  25 

Aufgabe 11.

  PROCEDURE Min(a: ARRAY OF REAL): REAL;
    VAR m: REAL; i: INTEGER;
  BEGIN
    m := a[0];
    FOR i := 1 TO LEN(a)-1 DO
      IF a[i] < m THEN m := a[i] END
    END;
    RETURN m
  END Min;

  PROCEDURE Max(a: ARRAY OF REAL): REAL;
    VAR m: REAL; i: INTEGER;
  BEGIN
    m := a[0];
    FOR i := 1 TO LEN(a)-1 DO
      IF a[i] > m THEN m := a[i] END
    END;
    RETURN m
  END Max;

  PROCEDURE Average(a: ARRAY OF REAL): REAL;
    VAR s: REAL; i: INTEGER;
  BEGIN
    s := a[0];
    FOR i := 1 TO LEN(a)-1 DO s := s + a[i] END;
    RETURN s / LEN(a)
  END Average;

Aufgabe 12.

  3 2 1 1 2 3 

Aufgabe 13.

  PROCEDURE Concat(a, b: Node): Node;
    VAR c: Node;
  BEGIN
    IF a = NIL THEN
      RETURN b
    ELSIF b = NIL THEN
      RETURN a
    ELSE
      c := a;
      WHILE c.next # NIL DO c := c.next END;
      c.next := b;
      RETURN a
    END
  END Concat;


  PROCEDURE Mix(a, b: Node): Node;
    VAR r, na, nb: Node;
  BEGIN
    IF a = NIL THEN
      r := b
    ELSIF b = NIL THEN
      r := a
    ELSE
      r := a;
      LOOP
        na := a.next; a.next := b;
        IF na = NIL THEN EXIT END;
        nb := b.next; b.next := na;
        IF nb = NIL THEN EXIT END;
        a := na; b := nb
      END
    END;
    RETURN r
  END Mix;

Aufgabe 14.

  PROCEDURE Height(tree: Node): INTEGER;
    VAR n: INTEGER;

    PROCEDURE Max(a, b): INTEGER;
    BEGIN
      IF a > b THEN RETURN a ELSE RETURN b END
    END Max;

  BEGIN
    IF tree = NIL THEN
      RETURN 0
    ELSE
      RETURN Max(Height(tree.left), Height(tree.right))+1
    END
  END Height;

Aufgabe 15. Falls diese Funktionen Seiteneffekte haben (d.h. sie lesen/schreiben globale Variablen)

Aufgabe 16.

(a)

  FOR i := 0 TO LEN(A) DO c[i] := 0;
    FOR j := 0 TO LEN(A,1) DO
      c[i] := c[i] + a[i, j]*b[j]
    END
  END

(b) Katastrophe! Jede Änderung von c wirkt auf b!

(c) b soll kein VAR-Parameter sein

Aufgabe 17. Lösung fehlt (noch).

Aufgabe 18. Lösung fehlt (noch).

Aufgabe 19. Lösung fehlt (noch).

Aufgabe 20. 

PROCEDURE Merge (VAR dst : Element; src1, src2 : Element);
VAR
    tmp : Element;
BEGIN
    /* First check for special cases: is one or both of the input lists empty? */
    IF (src1 = NIL) & (src2 = NIL) THEN
        dst := NIL;
    ELSE
        IF src1 = NIL THEN
            dst := src2;
            src2 := src2.next;
        ELSE
            IF src2 = NIL THEN
                dst := src1;
                src1 := src1.next;
            ELSE
                IF src1.val < src2.val THEN
                    dst := src1;
                    src1 := src1.next;
                ELSE
                    dst := src2;
                    src2 := src2.next;
                END;
            END;
        END;
        /* Main loop: append the smallest element of src1/src2 to list. */
        tmp := dst; /* tmp always points to the last element of list. */
        WHILE (src1 # NIL) & (src2 # NIL) DO
            IF src1.val < src2.val THEN
                tmp.next := src1;
                src1 := src1.next;
            ELSE
                tmp.next := src2;
                src2 := src2.next;
            END;
            tmp := tmp.next;
        END;
        /* Append the rest of the non-empty list. */
        IF src1 # NIL THEN
            tmp.next := src1;
        ELSE
            tmp.next := src2;
        END;
    END;
END Merge;