Einführung in die imperative Programmierung

WS 2015/16

Fakultät rekursiv

program fakultaet;

 uses crt;
   var i : real;
   
   function fak(n : real) : real;
   begin
   if (n=0) then
   fak := 1
   else
   fak := n * fak(n-1);
   end;

BEGIN
   readln(i);
   writeln(fak(i));
   
END.

Fibonacci rekursiv und iterativ

program fibonacci;

 var i : integer;
   
   function fibo(n : integer) : integer;
   begin
   if (n=0) then
   fibo := 0
   else 
   if (n=1) then
   fibo:= 1 
   else
   fibo := fibo(n-1) + fibo(n-2);
   end;
   
   function fibo_it(n: integer) : integer;
   var 
   i,j,k : integer;
   m : integer;
   begin
   if (n=0) then
   fibo_it := 0
   else 
   if (n=1) then
   fibo_it := 1
   else
   begin
   i := 0;
   j := 1;
   for m:=2 to n do
   begin
   k := j;
   j := i+j;
   i := k;
   end {for};
   fibo_it := j;
   end;
   end;

BEGIN
   readln(i);
   writeln(fibo_it(i));
   
END.

Türme von Hanoi rekursiv

program tuerme;

  var i : integer;

  procedure han(n:integer; von, ueber, nach : String);
  begin
    if (n>0) then
    begin
      han(n-1, von, nach, ueber);
      writeln('von ', von , ' nach ', nach);
      han(n-1, ueber, von, nach);
    end
  end;

  procedure hanoi(n: integer);
  begin
    han(n,'A','B','C');
  end;

BEGIN
  readln(i);
  hanoi(i);
END.

Aufgabe 1

program testeZeigListMax(input, output);
   { testet die Funktion ZeigListMax }

 type
   tRefListe = ^tListe;
   tListe = record
   info : integer;
   next : tRefListe
   end;

 var
   Liste,
   MaxZeig : tRefListe;

 function ZeigListMax (inRefAnfang : tRefListe) : tRefListe;
   { bestimmt rekursiv einen Zeiger auf das Listenelement mit
   der groessten Zahl }
   var zeiger: tRefListe;
   begin
   zeiger := inRefAnfang;
   if (zeiger=nil) then
   ZeigListMax := nil
   else
   if (zeiger^.next = nil) then
   ZeigListMax := zeiger
   else
   begin
   zeiger:= ZeigListMax(inRefAnfang^.next);
   if (inRefAnfang^.info > zeiger^.info) then
   zeiger := inRefAnfang;
   ZeigListMax := zeiger
   end;
   end;

procedure LiesListe(var outListe : tRefListe);
   { Liest eine (evtl. leere) Liste ein und gibt deren
   Anfangszeiger outListe zurueck. }

 var
   Anzahl : integer;
   i : integer;
   neueZahl : integer;
   Listenanfang,
   Listenende : tRefListe;
 

 begin
   Listenanfang := nil;
   repeat
   write ('Wie viele Zahlen wollen Sie eingeben? ');
   readln (Anzahl);
   until Anzahl >= 0;
   
   write ('Bitte geben Sie ', Anzahl, ' Zahlen ein: ');

 { Liste aufbauen }
   for i := 1 to Anzahl do
   begin
   read (neueZahl);
   if Listenanfang = nil then
   begin
   new (Listenanfang);
   Listenanfang^.next := nil;
   Listenanfang^.info := neueZahl;
   Listenende := Listenanfang;
   end
   else
   begin
   new (Listenende^.next);
   Listenende := Listenende^.next;
   Listenende^.next := nil;
   Listenende^.info := neueZahl
   end  { if Liste = nil }
   end; { for }
   outListe := Listenanfang;
   writeln
   end; { LiesListe }
 

begin 
   LiesListe (Liste);
   { Die zu testende Funktion wird zweimal aufgerufen, damit tatsaechlich
   ein Fehler auftritt, wenn die Liste durch den Aufruf zerstoert wird. }
   MaxZeig := ZeigListMax (Liste);
   MaxZeig := ZeigListMax (Liste);
   if MaxZeig = nil then
   writeln('Leere Eingabefolge!')
   else
   writeln ('Das Maximum ist ', MaxZeig^.info, '.')
   end. { testeZeigListMax }

Aufgabe 2

program TesteBlattMax (input, output);

type
   tNatZahl = 1..maxint;
   tRefBinBaum = ^tBinBaum;
   tBinBaum = record
   Wert:tNatZahl;
   links:tRefBinBaum;
   rechts:tRefBinBaum
   end;
   
   var
   Wurzel : tRefBinBaum;
   blaetterSindMax : Boolean;
   
   function BlattMax ( inRefWurzel : tRefBinBaum; pfadMax : tNatZahl) : Boolean;
   { prüft ob alle Blätter des Baumes die Maxima der Pfade zu ihnen sind }
   var boollinks, boolrechts: Boolean;
   begin 
   if inRefWurzel=nil then
   BlattMax := true
   else
   if ( inRefWurzel^.links = nil) and (inRefWurzel^.rechts = nil) then
   if (inRefWurzel^.Wert > pfadMax) then
   BlattMax := true
   else 
   BlattMax := false
   else
   begin
   if inRefWurzel^.Wert > pfadmax then
   pfadmax:= inRefWurzel^.Wert;
   boollinks := BlattMax( inRefWurzel^.links, pfadMax);
   boolrechts := BlattMax( inRefWurzel^.rechts, pfadmax);
   BlattMax := boollinks and boolrechts;
   end;

end;
 

procedure BaumAufbauen (var outWurzel : tRefBinBaum) ;
   var 
   index,
   Zahl : integer;
   elter, neuerKnoten : tRefBinBaum; 
   
   function KnotenVonIndex (baum : tRefBinBaum; index : integer) : tRefBinBaum;
   var
   elter : tRefBinBaum;
   begin
   if (index = 1) then
   KnotenVonIndex := baum
   else
   begin
   elter := KnotenVonIndex(baum, index div 2);
   if ( (index mod 2 ) = 0 ) then
   KnotenVonIndex := elter^.links
   else
   KnotenVonIndex := elter^.rechts
   end;
   end;

 begin
   read (index);

 new (outWurzel);
   read (Zahl);
   outWurzel^.Wert := Zahl;
   outWurzel^.links := nil;
   outWurzel^.rechts := nil;

 read (index);
   while (index <> 0) do
   begin 
   elter := KnotenVonIndex(outWurzel, index div 2);
   
   new (neuerKnoten);
   read (Zahl); 
   neuerKnoten^.Wert := Zahl; 
   neuerKnoten^.links:=nil;
   neuerKnoten^.rechts:=nil;

 if ( (index mod 2 ) = 0 ) then
   elter^.links := neuerKnoten
   else
   elter^.rechts := neuerKnoten;
   
   read (index); 
   end; 
   end; { BaumAufbauen }

begin
   writeln('Bitte Baum in level-order eingeben Eingabeformat: Immer erst der Index eines Knotens, dann dessen Wert:');
   BaumAufbauen (Wurzel);
   
   blaetterSindMax := BlattMax(Wurzel, 1);
   
   if blaetterSindMax then
   writeln ('Alle Blaetter sind groesser als alle Knoten auf den jeweiligen Pfaden zu ihnen.')
   else
   writeln ('Mind. ein Blatt ist nicht groesser als alle Knoten auf seinem Pfad.');

end. { TesteBBKnotenzahl }
 

Aufgabe 3

program testeBerechneTiefeUndMaxTiefe (input, output);
   { testet die Prozedur BerechneTiefeUndMaxTiefe }

 type
   tRefBinbaum = ^tBinbaum;
   tBinBaum = record
   Info,
   Tiefe : integer;
   links,
   rechts : tRefBinBaum;
   end;
   tNatZahl = 0..maxint;

 var
   Wurzel : tRefBinBaum;
   Max : tNatZahl;

procedure BerechneTiefeUndMaxTiefe (
   inRefWurzel : tRefBinBaum;
   inTiefe : tNatZahl;
   var ioMaxTiefe : tNatZahl);
   { berechnet die Tiefe aller Knoten in einem Binaerbaum, auf
   dessen Wurzel inRefWurzel zeigt; ioMaxTiefe muss vor dem Aufruf
   mit Null initialisiert sein und liefert die maximale Tiefe }

begin
   if inRefWurzel <> nil then
   begin
   inRefWurzel^.Tiefe := inTiefe;
   if ioMaxTiefe< inRefWurzel^.Tiefe then
   ioMaxTiefe := inRefWurzel^.Tiefe ;
   BerechneTiefeUndMaxTiefe(inRefWurzel^.links, inTiefe+1, ioMaxTiefe);
   BerechneTiefeUndMaxTiefe(inRefWurzel^.rechts, inTiefe+1, ioMaxTiefe);
   end;
   end;

procedure BBKnotenEinfuegen (
   inZahl : integer;
   var ioWurzel : tRefBinBaum);
   { fuegt in den Suchbaum, auf dessen Wurzel ioWurzel
   zeigt, ein Blatt mit Wert inZahl an. }

 var
   Zeiger : tRefBinBaum;

 begin
   if ioWurzel = nil then

 begin
   new (Zeiger);
   Zeiger^.Info := inZahl;
   Zeiger^.links := nil;
   Zeiger^.rechts := nil;
   Zeiger^.Tiefe := 0;
   ioWurzel := Zeiger
   end { if }
   else { ioWurzel <> nil }
   if inZahl < ioWurzel^.info then
   BBKnotenEinfuegen (inZahl, ioWurzel^.links)
   else
   BBKnotenEinfuegen (inZahl, ioWurzel^.rechts);
   end; { BBKnotenEinfuegen }

 procedure BBAufbauen (var outWurzel : tRefBinBaum);
   { Liest eine Folge von Integer-Zahlen ein (0 beendet die
   Eingabe, gehoert aber nicht zur Folge) und speichert
   die Folge in einem binren Suchbaum. }

 var 
   Zahl : integer;

 begin
   outWurzel := nil; { mit leerem Baum initialisieren }
   read (Zahl);
   while Zahl <> 0 do
   begin
   BBKnotenEinfuegen (Zahl, outWurzel);
   read (Zahl)
   end
   end; { BBAufbauen }

 procedure BaumAusgeben(inWurzel : tRefBinBaum);
   { Durchlaeuft den Binaerbaum mit Wurzel inWurzel und gibt
   die Knoteninhalte und Knotentiefen in preorder-Reihenfolge aus. }

 var
   Knoten : tRefBinBaum;

 begin
   if inWurzel <> nil then
   begin
   write (inWurzel^.info, ':', inWurzel^.Tiefe,' ');
   BaumAusgeben (inWurzel^.links);
   BaumAusgeben (inWurzel^.rechts);
   write('u ');
   end; { if }
   end; { BaumAusgeben }
 

begin
   writeln('Bitte integer-Zahlen eingeben (0=Ende):');
   BBAufbauen (Wurzel);
   Max := 0;
   BerechneTiefeUndMaxTiefe (Wurzel, 1, Max);
   WriteLn('Jetzt wird der Baum in preorder-Reihenfolge durchlaufen und die');
   WriteLn('Knoteninhalte in der Form Knoten:Tiefe ausgegeben.');
   WriteLn('Um die Knotentiefen kontrollieren zu koennen, wird bei jedem ');
   WriteLn('Ruecksprung aus der Prozedur ein "u" ausgegeben.');
   BaumAusgeben (Wurzel);
   writeln ('Maximale Tiefe: ', Max);
   end. { testeBerechneTiefeUndMaxTiefe }
 

Forward Deklaration

program forward;

 uses crt;
   
   var i : integer;
   
   function b(i: integer) : string; forward;
   
   function a(i: integer) : string;
   begin
   if (i=0) then 
   a:= ''
   else 
   a := b(i-1) + 'a';
   end;
   
   function b(i: integer) : string;
   begin
   if (i=0) then 
   b:= ''
   else 
   b := a(i-1) + 'b';
   end;

BEGIN
   readln(i);
   writeln(a(i));
   
END.