Einführung
in die imperative Programmierung
WS 2017/18
Prozedur Fakultät
program fakultaet;
var n : integer;
function fak(inZahl: integer) : integer;
begin
if inZahl = 0 then
fak := 1
else
fak := inZahl * fak(inZahl -1);
end;
BEGIN
readln(n);
writeln(fak(n));
END.
Prozedur Fibonacci
program fibonacci;
var n : integer;
function fibo(inZahl: integer) : integer;
begin
if inZahl = 0 then
fibo := 0;
if inZahl = 1 then
fibo := 1;
if inZahl > 1 then
fibo := fibo(inZahl-1) + fibo(inZahl-2);
end;
BEGIN
readln(n);
writeln(fibo(n));
END.
Prozedur Hanoi
program Hanoi_Programm;
uses crt;
var n : integer;
procedure hanoi(inN: integer; inVon, inUeber, inNach: string);
begin
if inN=1 then
writeln(inVon, '->', inNach)
else
begin
hanoi(inN-1, inVon, inNach , inUeber);
writeln(inVon, '->', inNach);
hanoi(inN-1, inUeber, inVon , inNach);
end;
end;
BEGIN
readln(n);
hanoi(n, 'a', 'b', 'c');
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 maximumZeiger : tRefListe;
begin
if inRefAnfang=nil then
ZeigListMax := nil
else
begin
maximumZeiger := ZeigListMax(inRefAnfang^.next);
if maximumZeiger=nil then
ZeigListMax := inRefAnfang
else
if inRefAnfang^.info > maximumZeiger^.info then
ZeigListMax := inRefAnfang
else
ZeigListMax := maximumZeiger;
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 (Fallunterscheidungen im else-Zweig)
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; inPfadMax : tNatZahl) : Boolean;
{ prüft ob alle Blätter des Baumes die Maxima der Pfade zu ihnen sind }
var
Pfadmax: tNatZahl;
ErgLinks, ErgRechts: boolean;
begin
if (inRefWurzel^.links=nil) and (inRefWurzel^.rechts=nil) then
{Abbruchbedingung}
begin
if inRefWurzel^.Wert <= inPfadMax then
BlattMax := false
else
BlattMax:= true;
end
else
begin
if inRefWurzel^.Wert > inPfadMax then
Pfadmax:= inRefWurzel^.Wert
else
Pfadmax := inPfadMax;
if inRefWurzel^.links=nil then
ErgLinks := true
else
ErgLinks := BlattMax(inRefWurzel^.links,Pfadmax);
if inRefWurzel^.rechts=nil then
ErgRechts := true
else
ErgRechts := BlattMax(inRefWurzel^.rechts,Pfadmax);
BlattMax := ErgLinks and ErgRechts;
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;{ KnotenVonIndex }
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 2 (2 Abbruchbedingungen)
function BlattMax ( inRefWurzel : tRefBinBaum; inPfadMax : tNatZahl) : Boolean;
{ prüft ob alle Blätter des Baumes die Maxima der Pfade zu ihnen sind }
var
Pfadmax: tNatZahl;
begin
if inRefWurzel=nil then
{Abbruchbedingung}
BlattMax:= true
else
if (inRefWurzel^.links=nil) and (inRefWurzel^.rechts=nil) then
{Abbruchbedingung}
begin
if inRefWurzel^.Wert <= inPfadMax then
BlattMax := false
else
BlattMax:= true;
end
else
begin
if inRefWurzel^.Wert > inPfadMax then
Pfadmax:= inRefWurzel^.Wert
else
Pfadmax := inPfadMax;
BlattMax := BlattMax(inRefWurzel^.links,Pfadmax) and BlattMax(inRefWurzel^.rechts,Pfadmax);
end;
end;
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 ??RefWurzel zeigt; ??MaxTiefe muss vor dem Aufruf
mit Null initialisiert sein und liefert die maximale Tiefe }
begin
if inRefWurzel<>nil then
begin
inRefWurzel^.Tiefe:= inTiefe;
if inTiefe> ioMaxTiefe then
ioMaxTiefe:= inTiefe;
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 }