Einführung
in die imperative Programmierung
WS 2014/15
Fakultät rekursiv
program fakultaet;
uses crt;
var
n,
erg : integer;
function fak(n: integer) : integer;
begin
if (n=0) then
fak := 1
else
fak:= fak(n-1) * n;
end;
BEGIN
readln(n);
erg := fak(n);
writeln(erg);
END.
Fibonacci rekursiv
program fibo;
uses crt;
var
n,
erg : 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;
BEGIN
readln(n);
erg := fibo(n);
writeln(erg);
END.
Fibonacci Iterativ
program fibo_iterativ;
uses crt;
var
n,erg : integer;
function fibo(n: integer) : integer;
var
i,
erg1, erg2, hilf : integer;
begin
if (n<2) then
fibo := n
else
begin
erg1 := 0; erg2:=1;
for i:=2 to n do
begin
hilf:=erg2;
erg2 := erg1 + erg2;
erg1:= hilf;
end;
fibo := erg2;
end;
end;
BEGIN
readln(n);
erg := fibo(n);
writeln(erg);
END.
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.
Türme von Hanoi
program hanoi (input, output);
var n: integer;
procedure han(n:integer; von,ueber,nach: string);
begin
if (n=1) then
writeln(von,'->',nach)
else
begin
han(n-1,von,nach,ueber);
writeln(von,'->',nach);
han(n-1,ueber,von,nach);
end;
end;
procedure hanoi(n: integer);
begin
han(n, 'A','B','C');
end;
begin
readln(n);
hanoi(n);
end.
inorder preorder
program preorderinorder (input, output);
type
tNatZahl = 0..maxint;
tRefBinBaum = ^tBinBaum;
tBinBaum = record
info : integer;
links : tRefBinBaum;
rechts : tRefBinBaum;
end;
var
Wurzel : tRefBinBaum;
Anzahl : integer;
procedure inorder (
inRefWurzel : tRefBinBaum) ;
{ bestimmt die Anzahl der Knoten des Binaerbaumes,
auf dessen Wurzel inRefWurzel zeigt }
begin
if (inRefWurzel <> nil) then
begin
inorder(inRefWurzel^.links);
writeln(inRefWurzel^.info);
inorder(inRefWurzel^.rechts);
end;
end;
procedure preorder (
inRefWurzel : tRefBinBaum) ;
{ bestimmt die Anzahl der Knoten des Binaerbaumes,
auf dessen Wurzel inRefWurzel zeigt }
begin
if (inRefWurzel <> nil) then
begin
writeln(inRefWurzel^.info);
preorder(inRefWurzel^.links);
preorder(inRefWurzel^.rechts);
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;
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 bin ren 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 }
begin
writeln('Bitte integer-Zahlen eingeben (0=Ende):');
BBAufbauen (Wurzel);
writeln();
writeln('Baum in preorder-Folge');
preorder (Wurzel);
writeln();
writeln('Baum in inorder-Folge');
inorder (Wurzel);
end. { TesteBBKnotenzahl }
Aufgabe 2
program TesteBBKnotenzahl (input, output);
type
tNatZahl = 0..maxint;
tRefBinBaum = ^tBinBaum;
tBinBaum = record
info : integer;
links : tRefBinBaum;
rechts : tRefBinBaum;
end;
var
Wurzel : tRefBinBaum;
Anzahl : integer;
function BBKnotenzahl (
inRefWurzel : tRefBinBaum) : tNatZahl;
{ bestimmt die Anzahl der Knoten des Binaerbaumes,
auf dessen Wurzel inRefWurzel zeigt }
var anz: integer;
begin
if (inRefWurzel <> nil) then
begin
anz:=1;
anz:= anz+ BBKnotenzahl(inRefWurzel^.links) + BBKnotenzahl(inRefWurzel^.rechts);
end;
{else anz:=0;}
BBKnotenzahl:= anz;
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;
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 bin ren 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 }
begin
writeln('Bitte integer-Zahlen eingeben (0=Ende):');
BBAufbauen (Wurzel);
{ 2 mal aufrufen wie bei Aufg. 1 }
Anzahl := BBKnotenzahl (Wurzel);
Anzahl := BBKnotenzahl (Wurzel);
writeln ('Der Baum hat ', Anzahl, ' Knoten.');
end. { TesteBBKnotenzahl }
Aufgabe 2 Alternative
program TesteBBKnotenzahl (input, output);
type
tNatZahl = 0..maxint;
tRefBinBaum = ^tBinBaum;
tBinBaum = record
info : integer;
links : tRefBinBaum;
rechts : tRefBinBaum;
end;
var
Wurzel : tRefBinBaum;
Anzahl : integer;
function BBKnotenzahl (
inRefWurzel : tRefBinBaum) : tNatZahl;
{ bestimmt die Anzahl der Knoten des Binaerbaumes,
auf dessen Wurzel inRefWurzel zeigt }
begin
if (inRefWurzel = nil) then
BBKnotenzahl:=0
else
BBKnotenzahl:= 1 + BBKnotenzahl(inRefWurzel^.links) + BBKnotenzahl(inRefWurzel^.rechts);
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;
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 bin ren 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 }
begin
writeln('Bitte integer-Zahlen eingeben (0=Ende):');
BBAufbauen (Wurzel);
{ 2 mal aufrufen wie bei Aufg. 1 }
Anzahl := BBKnotenzahl (Wurzel);
Anzahl := BBKnotenzahl (Wurzel);
writeln ('Der Baum hat ', Anzahl, ' Knoten.');
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 (inWurzel: tRefBinbaum; instufe: integer;
var ioMax: integer);
begin
if (inWurzel <> nil) then
begin
inWurzel^.Tiefe:= instufe;
if ( ioMax < instufe) then
ioMax := instufe;
BerechneTiefeUndMaxTiefe(inWurzel^.links, instufe+1, ioMax);
BerechneTiefeUndMaxTiefe(inWurzel^.rechts, instufe+1, ioMax);
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 bin ren 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 }