[UE ALGO 2 Homepage] Übungen zu Algorithmen und Datenstrukturen 2 WS 98/99

9. Übung - abzugeben am 15. 12. 1998 in Ihrer Übungsgruppe

9.a Theorie (Schriftliche Ausarbeitung)

Geben Sie von folgenden Prozeduren an, welche asymptotische Zeitkomplexität sie besitzen. Begründen Sie jeweils Ihre Meinung (Keine mathematische Ableitung notwendig!). 
PROCEDURE matmpy*(N:INTEGER);
VAR i,j,k:INTEGER;
BEGIN
  FOR i:=0 TO N-1 DO
    FOR j:=0 TO N-1 DO
      FOR k:=0 TO N-1 DO
        (*Einfache Anweisung*)
      END;
    END;
  END;
END matmpy;


PROCEDURE mystery*(N:INTEGER);
VAR i,j,k:INTEGER;
BEGIN
  FOR i:=1 TO N-1 DO
    FOR j:=i+1 TO N DO
      FOR k:=1 to j DO
        (*Einfache Anweisung*)
      END;
    END;
  END;
END mystery;


PROCEDURE strange*(N:INTEGER);
VAR i,j,k:INTEGER;
BEGIN
  FOR i:=2 TO N-1 DO
    FOR j:=i-1 TO N DO
      FOR k:=i-1 to i+1 DO
        (*Einfache Anweisung*)
      END;
    END;
  END;
END strange.


PROCEDURE recurs*(N:INTEGER):INTEGER;
BEGIN
  IF N<=1 THEN
    RETURN 1;
  ELSE
    RETURN recurs(N-1)+recurs(N-1);
  END;
END recurs;


PROCEDURE veryodd*(N:INTEGER);
VAR i,j:INTEGER;
BEGIN
  FOR i:=1 TO N DO
    IF ODD(i) THEN
      FOR j:=i TO N DO
        (*Einfache Anweisung*)
      END;
      FOR j:=1 TO i DO
        (*Einfache Anweisung*)
      END;
    END;
  END;
END veryodd;


PROCEDURE fibr*(N:INTEGER):INTEGER;
BEGIN
  IF N<=1 THEN
    RETURN 1
  ELSE 
    RETURN fibr(N-2)+fibr(N-1);
  END;
END fibr;


PROCEDURE fibi*(N:INTEGER):INTEGER;
VAR i,prev,act,next:INTEGER;
BEGIN
  prev:=1;act:=1;next:=1;
  FOR i:=2 TO N DO
    next:=prev+act;
    prev:=act;
    act:=next;
  END;
  RETURN next;
END fibi;
Geben Sie mit Begründung an, welche Zeitkomplexität folgende Problemstellungen haben:
  1. Suchen eines Elementes x in sortierter/unsortierter verketteter/konsekutiver Liste mit jeweils N Elementen
  2. Suchen von Minimum und Maximum in
    • einfach verketteter sortierter Liste mit N Elementen
    • in konsekutiver Liste mit N Elementen
    • in sortierter konsekutiver Liste mit N Elementen
    • einfach verketteter sortierter Liste mit Last-Zeiger

9.b Programm

Schreiben Sie ein Programm gemäß folgender Interface Definition. In einer Liste stehen die jeweiligen Kursänderungen einer Aktie je Zeiteinheit (z.B. Tag) in Euro. Es soll jener Kauf- und Verkaufstag im Beobachtungszeitraum ermittelt werden, an dem der erzielbare Gewinn ein Maximum ist. (Keine Berücksichtigung von Spesen etc., nur je eine Kauf- und Verkaufstransaktion)

Überlegen Sie sich die Zeitkomplexität ihrer Lösung und begründen Sie diese.

Versuchen Sie das Problem möglichst effizient zu lösen! 

MODULE BuySell;
  CONST N*=...; (* Anzahl der Listeneinträge *)
  TYPE  Liste*=ARRAY N OF LONGINT;
        Date*=INTEGER; (* Der wievielte Tag = Nummer des Listeneintrags *)

  PROCEDURE BuySellDate*(L:Liste; VAR Buy,Sell:Date; VAR Profit:LONGINT);
    (* Soll den besten Kaufs- und Verkaufstag sowie den maximal
       möglichen Gewinn laut den Aktienpreisänderungen
       der Liste L ermitteln. Ist der Profit 0, so können
       Buy und Sell undefiniert sein.
       Keine Prüfungen auf Overflow / Underflow von LONGINT
       notwendig.
    *)
END BuySell;
Beispiel (Profit = 23):
   +12  -10   -5  +15   -5  +10   -5   +8
                 *Buy                    *Sell

Last modified: hoermanseder@fim.uni-linz.ac.at 98-11-30