1613_02 Flashcards Preview

Hagen_1613 > 1613_02 > Flashcards

Flashcards in 1613_02 Deck (15):
1

function istSortiert(var inFeld: tFeld): Boolean;

{Ergebnis ist true, genau dann wenn inFeld aufsteigend sortiert ist, also keines der Elemente kleiner als sein Vorgänger ist.}

var i: tIndex;
sort: boolean;

begin

{Annahme "Feld ist sortiert"}

sort := true;
{Suche nach Gegenbeispiel, dazu jedes Arrayelement
(ab dem zweiten) mit Vorgänger vergleichen}

for i := 2 to GRENZE do
if inFeld[i] < inFeld[i-1] then
sort := false;
istSortiert := sort

end;

2

procedure tauschen(inVor1, inVor2:tRefElement);

{Vertauscht zwei Elemente einer Liste durch Änderung der Verkettung. inVor1 und inVor2 sind dabei Zeiger auf die Vorgängerelemente der zu vertauschenden Elemente.

Vorbedingung:
inVor1 und inVor2 zeigen jeweils auf ein existierendes
Element derselben Liste, jedoch nicht auf das selbe, nicht auf das letzte und nicht auf zwei direkt aufeinander folgende Elemente.}

var
Element1, Element2, Nach1, Nach2 : tRefElement;
begin

{Der Übersichtlichkeit halber setzen wir Hilfszeiger auf
die zu vertauschenden Elemente sowie ihre Nachfolger:}

Element1 := inVor1^.next;
Element2 := inVor2^.next;
Nach1 := Element1^.next;
Nach2 := Element2^.next;

{Damit ist die Verkettungsänderung nun einfach:}

inVor1^.next := Element2;
Element2^.next := Nach1;
inVor2^.next := Element1;
Element1^.next := Nach2;

end;

3

procedure NachVorn( inWert: integer;
var ioRefAnfang: tRefElement);
{Sucht das erste vorkommende Element mit inWert in der
info-Komponente und verschiebt dieses Element an den Anfang der Liste.
Vorbedingung: Ein solches Element muss in der Liste vorkommen!}

var lauf,
elem: tRefElement;
begin
{Sonderfallprüfung: Falls das erste Element den Wert
inWert hat, so ist nichts zu tun.}

if (ioRefAnfang^.info <> inWert) then
begin
{Den Vorgaenger des zu verschiebenden Elementes suchen:}

lauf := ioRefAnfang;

while lauf^.next^.info <> inWert do
lauf := lauf^.next;
elem := lauf^.next;

{elem zeigt nun auf das zu verschiebende Element,
lauf auf dessen Vorgaenger. Jetzt verschieben:}

lauf^.next := elem^.next;
elem^.next := ioRefAnfang;
ioRefAnfang := elem;

end; {if}

end; {NachVorn}

4

function fibonacci(inZahl: tNatZahl): tNatZahl;
{ Berechnet iterativ die inZahl-te Fibonacci-Zahl }
var letzte, vorletzte, aktuelle, lauf: tNatZahl;

Iterative Lösung

begin

if inZahl < 2 then
fibonacci := inZahl
else

begin
{ Initialisierung der Vorgänger (f(0) und f(1))
für die Berechnung von f(2) }

vorletzte := 0;
letzte := 1;
{ Berechnung von f(2) bis f(inZahl) }

for lauf := 2 to inZahl do

begin
aktuelle := vorletzte + letzte;
vorletzte := letzte;
letzte := aktuelle;
end;

fibonacci := aktuelle

end

end;

5

program Dreieck(input,output);
{Liest eine natürliche Zahl n ein und gibt ein Dreieck aus 1+…+n X-Symbolen aus.}

var
n:integer;
i:integer;
j:integer;

begin
writeln('Geben Sie eine natürliche Zahl ein: ');
readln(n);
for i:=1 to n do
begin
for j:=1 to i do
write('X');
writeln()
end
end.

6

function FeldSAbweichung(inFeld:tFeld):real;
{Berechnet die Standardabweichung der Werte im Feld inFeld.}

var
Mittelwert:real;
SAbweichung:real;
i:tIndex;

begin
{Mittelwert berechnen}

Mittelwert:=0;

for i:=1 to FELDGROESSE do
Mittelwert:=Mittelwert+inFeld[i];

Mittelwert:=Mittelwert/FELDGROESSE;

{Standardabweichung berechnen}
SAbweichung:=0;
for i:=1 to FELDGROESSE do
SAbweichung:=SAbweichung+sqr(inFeld[i]-Mittelwert);

SAbweichung:=SAbweichung/FELDGROESSE;

FeldSAbweichung:=sqrt(SAbweichung)

end;

7

procedure markDuplicates(var ioFeld : tFeld);
{zu erstellende Prozedur. Die Prozedur überschreibt Duplikate mit 0}

var
i,
k : integer;

begin
k := GROESSE;

for i:= 1 to GROESSE do
begin
for k:=GROESSE downto i+1 do
begin
if ioFeld[i] = ioFeld[k] then
ioFeld[k] := 0
end
end


end;

8

procedure VerschiebeZyklisch (var ioFeld : tFeld);

{ verschiebt die Werte innerhalb eines Feldes eine Position
nach rechts; der Wert ioFeld[MAX] wird nach ioFeld[1]
übertragen }

var
sicher: integer;
ix: tIndex;

begin
sicher := ioFeld[MAX];
(* Der letzte Feldinhalt wird gesichert *)

for ix := MAX downto 2 do
ioFeld[ix] := ioFeld[ix-1];

(* Die Feldinhalte mit Ausnahme des Letzten werden um eine Position nach rechts verschoben *)

ioFeld[1] := sicher

(* Das ehemalig letzte Element wird neues erstes *)
end;{VerschiebeZyklisch}

9

procedure VerschiebeBis (inWert : integer;
var ioFeld : tFeld);

{ verschiebt den Inhalt von ioFeld solange zyklisch nach
rechts, bis inWert vorne steht. Falls inWert nicht im Feld
vorkommt, wird der Feldinhalt nicht verändert }

var
vorhanden : boolean;
ix: tIndex;

begin
vorhanden := false;
ix := 0;

while ((not vorhanden) and (ix < MAX)) do
(* Die Schleife wird solange durchlaufen, bis inWert
gefunden wird oder das ganze Feld durchsucht ist *)

begin
ix := ix + 1;
if ioFeld[ix] = inWert then
vorhanden := true
end;

if vorhanden then
(* Wenn der Suchwert im Feld vorkommt, wird solange verschoben, bis sich dieser an der ersten Position befindet *)

while ioFeld1[1] <> inWert do

VerschiebeZyklisch(ioFeld)

end; {VerschiebeBis}

10

procedure suchen(inSuchwert: integer; inRefAnf: tRefListe; var outPos: tRefListe);

{ Gibt mit outPos einen Zeiger auf das letzte Vorkommen von inSuchwert in der Liste inRefAnfang zurück }

var
lauf,
pos: tRefListe;

begin
pos := inRefAnfang;
lauf := inRefAnfang^.next;
while lauf <> NIL do

(* Die Liste wird vollständig durchlaufen und dabei das *)
(* jeweils letzte Vorkommen von inSuchwert gespeichert *)

begin
if lauf^.info = inSuchwert then

pos := lauf;
lauf := lauf^.next
end; { while lauf <> NIL }

outPos := pos;
end; {suchen}

11

procedure loeschen(inSuchwert: integer;
var ioRefAnf: tRefListe);

{ löscht das letzte Vorkommen von inSuchwert in der Liste, deren Anfangszeiger ioRefAnf ist}

var lauf,
pos: tRefListe;

begin
suchen(inSuchwert, ioRefAnf, pos);

if pos = ioRefAnf then (* Sonderfall: Löschen des Listenanfangs*)
ioRefAnf := ioRefAnf^.next

else
begin
lauf := ioRefAnf;

while lauf^.next <> pos do
(* Finden des Vorgängers von pos *)
lauf := lauf^.next;

(* Das Element pos wird aus der Liste entfernt: *)

lauf^.next := pos^.next
end; { if pos = ioRefAnf }

dispose(pos)

end; {loeschen}

12

procedure Pruefen(inWurzel: tRefBinBaum;
var ioBalanciert: boolean);

{ setzt ioBalanciert auf false, wenn der in inWurzel übergebene Baum nicht balanciert ist }

begin

if inWurzel <> NIL then

begin
(* Sind alle Teilbaeume balanciert ? *)

Pruefen(inWurzel^.links, ioBalanciert);
Pruefen(inWurzel^.rechts, ioBalanciert);

(* Gilt die Balancierteigensschaft zusätzlich auch für die Wurzel?*)

if abs(Hoehe(inWurzel^.links)-Hoehe(inWurzel^.rechts)) >1
then

ioBalanciert := false

end { if inWurzel <> NIL }

end; {Pruefen}

13

program perfekteZahl (input, output);

{ berechnet alle "perfekten Zahlen" zwischen 1 und 1000 }

const
MINIMAL = 1;
MAXIMAL = 1000;

type
tNatZahl = 0..maxint;
tLoesungsbereich = MINIMAL..MAXIMAL;

var
n : tLoesungsbereich;
i,
Summe : tNatZahl;

begin
writeln;
write ('perfekte Zahlen: ');
{ alle Zahlen zwischen 1 und 1000 untersuchen }

for n := MINIMAL to MAXIMAL do
begin
Summe := 0;
{ alle Teiler von n zwischen 1 und n/2 summieren }

for i := 1 to (n div 2) do
if n mod i = 0 then
Summe := Summe + i;

if n = Summe then
write (n,', ')

end

end. { perfekteZahl }

14

function finden (inWert : integer;
inRefListe : tRefListe) : tRefListe;

{ sucht den Wert inWert in der Liste, auf deren Anfang
inRefListe zeigt. Wird der Wert gefunden, liefert die
Funktion einen Zeiger auf das Element zurueck,
ansonsten nil }

var
refLauf : tRefListe;

begin
gefunden := false;
refLauf := inRefListe;

while ((refLauf <> nil) and (not gefunden)) do
if refLauf^.info = inWert then
gefunden := true

else
refLauf := refLauf^.next;

finden := refLauf

end; { einfuegen }

15

procedure Tausche(var ioRefListe: tRefListe);

Implementieren Sie eine Prozedur Tausche, die in einer übergebenen Liste das Element mit
info-Komponente 0 sucht und mit dem Nachfolger nur durch Ändern der Verkettung vertauscht. Sie
können davon ausgehen, dass die 0 in der Liste genau einmal, aber nicht als letztes Element vorkommt.

var such,
vor,
nach : tRefListe;

begin
vor := NIL;
such := ioRefListe;
while such^.info <> 0 do

begin
vor := such;
such := such^.next
end;
nach := such^.next^.next;

{Jetzt sind alle Zeiger positioniert. such zeigt auf das
Element mit dem Wert 0, vor auf dessen Vorgaenger oder auf nil, nach auf den Nachfolger von such^.next}

if vor=NIL then
{D.h. es muss am Anfang getauscht werden }

ioRefListe := such^.next
else
vor^.next := such^.next;

such^.next^.next := such;

{such^.next ist ungleich nil, da nach Voraussetzung 0 in der Liste nicht als letztes Element vorkommt }

such^.next := nach
end;