Algorithmische GrundstrukturenAlgorithmische Grundstrukturen
IFB 2002
Klaus Becker
2
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nTeil 1Teil 1
Algorithmisches Problemlösen
3
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProblemProblem
Eine Lokomotive soll die auf Gleis A (oben) befindlichen Wagen in umgekehrter Reihenfolge auf Gleis B (unten) abstellen.
AZ
ZZ
B ?
Problem: AZ ZZ Barriere Ausgangszustand Zielzustand
Problem: AZ ZZ Barriere Ausgangszustand Zielzustand
B ZZ
4
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProblemspezifikationProblemspezifikation
AZ
ZZ
Problem:
Problemspezifikation:
vollständige und eindeutige Beschreibung des Ausgangs- und Zielzustandes
Problemspezifikation:
vollständige und eindeutige Beschreibung des Ausgangs- und Zielzustandes
5
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProblemlösen mit einem ProzessorProblemlösen mit einem Prozessor
AZ
ZZ
Prozessor: legt die zulässigen Operationen festProzessor: legt die zulässigen Operationen fest
Lokomotive: fahren; ankoppeln; abkoppeln; Weiche stellen; ..
6
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAlgorithmusAlgorithmus
AZ
ZZ
Algorithmus: Problemlösebeschreibung
Algorithmus:
endliche Folge von eindeutig ausführbaren Anweisungen zur Lösung des Problems
Algorithmus:
endliche Folge von eindeutig ausführbaren Anweisungen zur Lösung des Problems
7
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nKorrektheitKorrektheit
AZ
ZZ
Spezifikation:
Korrektheit bzgl. einer Spezifikation:
Algorithmus überführt tatsächlich den AZ in den ZZ (für alle möglichen AZ-Konstellationen)
Korrektheit bzgl. einer Spezifikation:
Algorithmus überführt tatsächlich den AZ in den ZZ (für alle möglichen AZ-Konstellationen)
8
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nEffizienzEffizienz
AZ
ZZ
Spezifikation:
Effizienz:
Algorithmus löst das Problem mit möglichst geringen Aufwand
Effizienz:
Algorithmus löst das Problem mit möglichst geringen Aufwand
9
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nZieleZiele
Wie sind Algorithmen zur Lösung von Problemen aufgebaut?
„Grundbausteine von Algorithmen“
Wie formuliert man Algorithmen, so dass sie vom Computer ausgeführt werden können?
„Grundelemente von Programmiersprachen“
Einschränkungen
- imperative Algorithmen
- Pascal als Programmiersprache
10
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nTeil 2Teil 2
Variablenkonzept
11
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nMäusepopulationMäusepopulation
Wir betrachten die Entwicklung einer Mäusepopulation. Die Population wird unterteilt in junge Mäuse, erwachsene Mäuse und alte Mäuse. Wir gehen von den folgenden Annahmen aus:- In einem Simulationsschritt wird die Hälfte der jungen Mäuse erwachsen.- In einem Simulationsschritt erzeugt jede erwachsene Maus (im Durchschnitt) 4 junge Mäuse. Nur ein Drittel der erwachsenen Mäuse wird in einem Simulationsschritt alt.- In einem Simulationsschritt erzeugt jede alte Maus (im Durchschnitt) 2 junge Mäuse. Alle alten Mäuse sterben innerhalb dieses Simulationsschrittes.
Wir betrachten die Entwicklung einer Mäusepopulation. Die Population wird unterteilt in junge Mäuse, erwachsene Mäuse und alte Mäuse. Wir gehen von den folgenden Annahmen aus:- In einem Simulationsschritt wird die Hälfte der jungen Mäuse erwachsen.- In einem Simulationsschritt erzeugt jede erwachsene Maus (im Durchschnitt) 4 junge Mäuse. Nur ein Drittel der erwachsenen Mäuse wird in einem Simulationsschritt alt.- In einem Simulationsschritt erzeugt jede alte Maus (im Durchschnitt) 2 junge Mäuse. Alle alten Mäuse sterben innerhalb dieses Simulationsschrittes.
12
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nEntwicklung der MäusepopulationEntwicklung der Mäusepopulation
Schritt Anzahl der Anzahl der Anzahl derjungen Mäuse erw. Mäuse alten
Mäuse0 6 9 12
1 60 = 4*9 + 2*12 3 = 6:2 3 = 9:32 18 = 4*3 + 2*3 30 = 60:2 1 = 3:3
3 122 = 4*30 + 2*1 9 = 18:2 10 = 30:3
4 56 = 4*9 + 2*10 61 = 122:2 3 = 9:3
5 250 = 4*61 + 2*3 28 = 56:2 20,3.. = 61:3
...
Ziel: Automatisierung der Berechnung Berechnungsmodell
13
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nBerechnungsmodellBerechnungsmodell
0
6.0
...
...
Register (Speicherplat
z)
Variable (Name des Registers)
Schritt :
jung :
erwachsen :
alt :
integer-Registerreal-Register
Berechnungsmodell: Variablen-basierte RegistermaschineBerechnungsmodell: Variablen-basierte Registermaschine
14
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nVariablendeklarationVariablendeklaration
Schritt : integer
...
jung : real ...
erwachsen : real ...
alt : real ...
Register (Speicherplat
z)
Datentyp (legt zulässigen Registerinhalte fest)
Variable(Name des Registers)
Eine Variablendeklaration legt die zu benutzenden Register fest.Eine Variablendeklaration legt die zu benutzenden Register fest.
Schritt :
jung :
erwachsen :
alt :
15
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nVariablenwertVariablenwert
0
6.0
9.0
...
Schritt :
jung :
erwachsen :
alt :
{Schritt: [0]; jung: [6.0]; erwachsen: [9.0]; alt: [...]}
Kurzschreibweise für Variablenzustände:
Variablenzustand: Gesamtheit der Variablenwerte
Der Variablenwert stellt den Registerinhalt dar.Der Variablenwert stellt den Registerinhalt dar.
16
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nWertzuweisungWertzuweisung
alt := 12.0
vorher
Wertzuweisung
{Schritt: [0]; jung: [6.0]; erwachsen: [...]; alt: [...]}
nachher{Schritt: [0]; jung: [6.0]; erwachsen: [...]; alt: [12.0]}
erwachsen := jung / 2
vorher
Wertzuweisung
{Schritt: [0]; jung: [6.0]; erwachsen: [...]; alt: [12.0]}
nachher{Schritt: [0]; jung: [6.0]; erwachsen: [3.0]; alt: [12.0]}
Schritt := Schritt +1
vorher
Wertzuweisung
{Schritt: [0]; jung: [6.0]; erwachsen: [3.0]; alt: [12.0]}
nachher{Schritt: [1]; jung: [6.0]; erwachsen: [3.0]; alt: [12.0]}
Mit Wertzuweisungen werden Variablenwerte verändert. Mit Wertzuweisungen werden Variablenwerte verändert.
17
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nWertzuweisungWertzuweisung
Semantik:Syntax:
<Variable> := <Term>
Schritt := Schritt +1
Beachte: Variable und Term müssen typkonform sein.
Der Wert des Terms wird bzgl. des aktuellen Variablenzustands ermittelt und der Variablen als neuer Wert zugewiesen.(Überschreiben des Registers)
{ Schritt: [3]; ...}
4{ Schritt: [4]; ...}
Beispiel:
Schritt := Schritt +1
18
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProblemspezifikationProblemspezifikation
AZ: Die eingeführten Variablen beschreiben die Anfangspopulation. {Schritt: [0]; jung: [6.0]; erwachsen: [9.0]; alt: [12.0]}
EZ: Die Variablen beschreiben die Population nach einem Simulationsschritt.. {Schritt: [1]; jung: [60.0]; erwachsen: [3.0]; alt: [3.0]}
Erweiterung:Die Anfangspopulation soll vom Benutzer vorgegeben werden.Die neue Population nach einem Simulationsschritt soll dem Benutzer angezeigt werden.
19
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nLösungsvorschlag 1Lösungsvorschlag 1
Variablenzustand - Trace-Tabelle
Schritt jung erw. alt
0 6.0 9.0 12.0
1 6.0 9.0 12.0
1 60.0 9.0 12.0
1 60.0 30.0 12.0
1 60.0 30.0 10.0
Wertzuweisung
Schritt := Schritt + 1
jung := erwachsen*4 + alt*2
erwachsen := jung / 2
alt := erwachsen / 3
beachte:
Der Algorithmus ist nicht korrekt!
20
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nLösungsvorschlag 2Lösungsvorschlag 2
Variablenzustand - Trace-Tabelle
Schritt jung erw. alt hilf
0 6.0 9.0 12.0
1 6.0 9.0 12.0
1 6.0 9.0 12.0 60.0
1 6.0 9.0 3.0 60.0
1 6.0 3.0 3.0 60.0
1 60.0 3.0 3.0 60.0
Wertzuweisung
Schritt := Schritt + 1
hilf := erwachsen*4 + alt*2
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
beachte:
Reihenfolge der Wertzuweisungen
21
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAlgorithmusAlgorithmus
Eingabe: jung, erwachsen, alt
Schritt := 0
Schritt := Schritt + 1
hilf := erwachsen*4 + alt*2
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
Ausgabe: Schritt, jung, erwachsen, alt
EVA-Prinzip:Eingabe - Verarbeitung - Ausgabe
EVA-Prinzip:Eingabe - Verarbeitung - Ausgabe
E
V
A
22
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nPascal-ProgrammPascal-Programm
PROGRAM Maeuse1;
VAR Schritt : integer; jung, erwachsen, alt : real; hilf : real;
BEGIN{ Eingaben und Initialisierungen }...
{ Berechnungen }Schritt := Schritt+1;hilf := erwachsen*4 + alt*2;alt := erwachsen/3;erwachsen := jung/2;jung := hilf;
{ Ausgaben }...END.
23
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProgrammstrukturProgrammstruktur
PROGRAM Maeuse1;
VAR <Variablendeklaration> ; <Variablendeklaration> ; <Variablendeklaration> ;
BEGIN
...
{ Kommentar }<Anweisung> ;<Anweisung> ;<Anweisung> ;
...
END.
Deklarationsteil - erzeugt die Register
Anweisungsteil - verändert die Registerinhalte
Programmkopf
24
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nBasisanweisungenBasisanweisungen
BEGIN{ Eingaben und Initialisierungen }writeln('Geben Sie die Anfangspopulation ein.');write('Anzahl der jungen Mäuse : ');readln(jung);write('Anzahl der erwachsenen Mäuse : ');readln(erwachsen);write('Anzahl der alten Mäuse : ');readln(alt);Schritt := 0;
{ Berechnungen }Schritt := Schritt+1;...
{ Ausgaben }writeln('Anzahl der Schritte: ', Schritt);writeln('Anzahl der jungen Mäuse : ', jung:6:2);writeln('Anzahl der erwachsenen Mäuse : ', erwachsen:6:2);writeln('Anzahl der alten Mäuse : ', alt:6:2);END.
Eingabeanweisung: read(ln)
Wertzuweisung: :=
Ausgabeanweisung: write(ln)
Eingabeanweisung: read(ln)
Wertzuweisung: :=
Ausgabeanweisung: write(ln)
25
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAnweisungen - eine ÜbersichtAnweisungen - eine Übersicht
Anweisung
Basisanweisung Kontrollanweisung
Wertzuweisung
Eingabeanweisung
Ausgabeanweisung
...
Wertzuweisung
Eingabeanweisung
Ausgabeanweisung
...
...
26
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nTeil 3Teil 3
Kontrollstrukturen
27
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nSequenzbildungSequenzbildung
{Eingabe und Initialisierung}
Eingabe: jung, erwachsen, alt
Schritt := 0
{Verarbeitung}
Schritt := Schritt + 1
hilf := erwachsen*4 + alt*2
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
{Ausgabe}
Ausgabe: Schritt, jung, erwachsen, alt
28
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nSequenzSequenz
BEGIN
<Anweisung1>;<Anweisung2>;<Anweisung3>;...
END
PASCAL
Anweisung1
Anweisung2
Anweisung3
...
Struktogramm
Anweisung1
PAP
Anweisung2
Anweisung3
...
29
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProblemspezifikationProblemspezifikation
Ziel: Die Entwicklung der Mäusepopulation soll über 20 Schritte verfolgt werden.
Spezifikation
Eingaben: Die Werte der Anfangspopulation werden eingegeben. Z B.: jung: 6.0; erwachsen: 9.0; alt: 12.0
Ausgaben: Die Populationswerte nach 20 Simulationsschritten werden ausgegeben.
30
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nWiederholungWiederholung
Variablenzustand
Schritt jung erw. alt hilf
0 6.0 9.0 12.0
1 6.0 9.0 12.0
1 6.0 9.0 12.0 60.0
1 6.0 9.0 3.0 60.0
1 6.0 3.0 3.0 60.0
1 60.0 3.0 3.0 60.0
2 60.0 3.0 3.0 60.0
2 60.0 3.0 3.0 18.0
2 60.0 3.0 1.0 18.0
2 60.0 30.0 1.0 18.0
2 18.0 30.0 1.0 18.0
...
Anweisung
{Eingaben / Initialisierung}
Schritt := Schritt + 1
hilf := erwachsen*4 + alt*2
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
Schritt := Schritt + 1
hilf := erwachsen*4 + alt*2
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
...
31
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
n
Ausgabe: jung, erwachsen, alt, gesamt
WiederholungWiederholung
Eingabe: jung, erwachsen, alt
gesamt := jung + erwachsen + alt
Schritt := 0
Schritt := Schritt +1
hilf := erwachsen*4 + alt*2
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
gesamt := jung + erwachsen + alt
SOLANGE Schritt < 20
32
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nWiederholungWiederholung
Eingabe: ...; gesamt := ...; Schritt := 0
Schritt := Schritt +1
hilf := erwachsen*4 + alt*2
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
gesamt := jung + erwachsen + alt
Schritt < 20
wahr
falsch
Ausgabe: jung, erwachsen, alt, gesamt
33
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nMäusepopulationMäusepopulation
Schritt < 100
Die Entwicklung der Mäusepopulation wird wie folgt abgeändert: Sind weniger als 1000 Mäuse in der Population, so verhalten sich die Mäuse wie bisher. Ab 1000 Mäuse wird das Futter knapp. Alte Mäuse erzeugen dann keine jungen Mäuse mehr und jede erwachsene Maus erzeugt (im Durchschnitt) nur noch 1.5 junge Mäuse.
Spezifikation: wie oben
Die Entwicklung der Mäusepopulation wird wie folgt abgeändert: Sind weniger als 1000 Mäuse in der Population, so verhalten sich die Mäuse wie bisher. Ab 1000 Mäuse wird das Futter knapp. Alte Mäuse erzeugen dann keine jungen Mäuse mehr und jede erwachsene Maus erzeugt (im Durchschnitt) nur noch 1.5 junge Mäuse.
Spezifikation: wie oben
34
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
n
gesamt := jung + erwachsen + alt
Schritt := Schritt +1
FallunterscheidungFallunterscheidung
Eingabe: jung, erwachsen, alt
gesamt := jung + erwachsen + alt
Schritt := 0
hilf := erwachsen*4 + alt*2
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
SOLANGE Schritt < 20
hilf := erwachsen*1.5
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
gesamt < 1000wahr falsch
35
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nFallunterscheidungFallunterscheidung
Schritt := 0; ... ; gesamt := jung + erwachsen + alt
hilf := erwachsen*4 + alt*2
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
Schritt < 20
hilf := erwachsen*1.5
alt := erwachsen / 3
erwachsen := jung / 2
jung := hilf
gesamt < 1000
gesamt := jung + erwachsen + alt
wahr falsch
wahr
falsch
...
Schritt := Schritt + 1
36
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nPascal-ProgrammPascal-Programm
...BEGIN{Eingaben und Initialisierung};...WHILE Schritt < 20 DO BEGIN Schritt := Schritt+1; IF gesamt < 1000 THEN BEGIN hilf := erwachsen*4 + alt*2; ... END ELSE BEGIN hilf := erwachsen*1.5; ... END; gesamt := jung + erwachsen + alt; END;{Ausgaben}... END.
37
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nKontrollstrukturenKontrollstrukturen
Kontrollstrukturen dienen dazu, den genauen Ablauf von Aktionen festzulegen.Kontrollstrukturen dienen dazu, den genauen Ablauf von Aktionen festzulegen.
Ablaufmuster:
- sequentieller Ablauf
- wiederholter Ablauf
- bedingter Ablauf
- paralleler Ablauf
- ereignisgesteuerter Ablauf
Kontrollstrukturen:
- Sequenz
- Wiederholung
- Fallunterscheidung / Auswahl
38
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAnweisungen - eine ÜbersichtAnweisungen - eine Übersicht
Anweisung
Basisanweisung Kontrollanweisung
Wertzuweisung
Eingabeanweisung
Ausgabeanweisung
...
Wertzuweisung
Eingabeanweisung
Ausgabeanweisung
...
Sequenzanweisung
Wiederholungs-anweisung
Fallunterscheidungs-anweisung
Sequenzanweisung
Wiederholungs-anweisung
Fallunterscheidungs-anweisung
...
39
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nSchachtelung von AnweisungenSchachtelung von Anweisungen
BEGINreadln(jung);...WHILE Schritt < 20 DO BEGIN Schritt := Schritt+1; IF gesamt < 1000 THEN BEGIN hilf := erwachsen*4 + alt*2; ... END ELSE BEGIN hilf := erwachsen*1.5; ... END; gesamt := jung + erwachsen + alt; END;writeln('Anzahl der Schritte: ', Schritt);... END.
40
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 1Übungen - Aufgabe 1
AZ
ZZ
Formulieren Sie (umgangssprachlich) einen Algorithmus zur Lösung des Rangierproblems. Die Lokomotive kann folgende „Operationen“ ausführen: vorwärts / rückwärts fahren; ankoppeln; abkoppeln; Weiche umstellen. Der Algorithmus soll für eine beliebige Anzahl von Waggons korrekt sein.
41
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 2Übungen - Aufgabe 2
AZ: { A: [a]; B: [b]; C: [c] }
EZ: { A: [c]; B: [a]; C: [b] }
Abstraktes Rangierproblem:
Gegeben sind drei Variablen A, B und C. Die Werte der Variablen sollen wie folgt ausgetauscht werden:
a
b
c
A:
B:
C:
42
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 3Übungen - Aufgabe 3
B := A
A := B
Vertauschungsproblem:
Die Werte der Variablen A und B sollen ausgetauscht werden:
AZ: { A: [a]; B: [b] }
EZ: { A: [b]; B: [a] }
Beurteile die folgenden Algorithmen hinsichtlich Korrektheit und Aufwand.
H := A
A := B
B := H
C := A
D := B
A := D
B := C
A := A - B
B := A + B
A := B - A
43
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 4Übungen - Aufgabe 4
Mäusepopulation:
Der Algorithmus / das Programm zur Beschreibung der Entwicklung der Mäusepopulation soll wie folgt abgeändert werden:
A) Der jeweilige Populationszustand (Anzahl der jungen, erwachsenen und alten Mäuse) soll nach jedem Schritt ausgegeben werden.
B) Nach jedem Schritt sollen die prozentualen Anteile der jungen, erwachsenen und alten Mäuse an der momentanen Gesamtpopulation berechnet und ausgegeben werden.
44
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 5Übungen - Aufgabe 5
Trace-Tabelle:
Erstellen Sie eine Trace-Tabelle für die Eingaben A 10 und B 24. Was leistet der folgende Algorithmus?
BEGINReadln(A);Readln(B);REPEAT WHILE A > B DO A := A – B; WHILE B > A DO B := B – A;UNTIL A = BWriteln(A);END
45
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 6Übungen - Aufgabe 6
Problem:
Eine Folge positiver Zahlen soll eingelesen und ihr Minimum bestimmt und ausgegeben werden. Das Ende der Folge wird durch die Eingabe der Zahl 0 erkannt.
Bsp.: Eingabefolge: 5, 3, 6, 7, 0 Ausgabe: 3Eingabefolge: 0 Ausgabe: 0
Ist der folgende Algorithmus korrekt? Ändern Sie ihn gegebenenfalls geeignet ab.
Eingabe: zmin := zSOLANGE z > 0 Eingabe: z WENN z < min DANN min := zAusgabe: min
46
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 7Übungen - Aufgabe 7
Mit Hilfe eines Programms soll die Kapitalentwicklung bei einer Verzinsung mit einem festen Zinssatz von p = 3% berechnet werden.
Problemspezifikation 1:Eingaben : Anfangskapital, Anzahl der JahreAusgabe : erreichtes Endkapital
Problemspezifikation 2:Eingaben : Anfangskapital, EndkapitalAusgabe : Anzahl der benötigten Jahre
Erstellen Sie entsprechende Algorithmen / Programme.
47
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 8Übungen - Aufgabe 8
Für Fortgeschrittene:
Ziel ist es, das Spiel „17 und 4“ zu simulieren. Das Spiel soll wie folgt funktionieren:In jedem Spielzug wird eine Karte mit einer Zahl aus dem Bereich [1;...;11] bestimmt und auf einen Kartenstapel gelegt. Der Spieler kann nach jedem Spielzug entscheiden, ob er aufhört oder weiter spielt. Ist die Summe der Zahlen der Karten des Stapels größer als 21, so hat der Spieler verloren. Hört der Spieler bei einer Stapelsumme kleiner oder gleich 21 auf, so wird die nächste Karte gezogen. Ist die neue Stapelsumme immer noch kleiner oder gleich 21, so hat der Spieler verloren, andernfalls gewonnen.
Erstellen Sie einen passenden Algorithmus.
48
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAufgabe 1 - LösungsvorschlagAufgabe 1 - Lösungsvorschlag
Solange noch mindestens ein Waggon auf Gleis A steht:
vorwärts fahren;
ankoppeln;
rückwärts fahren;
Weiche umstellen;
vorwärts fahren;
abkoppeln;
rückwärts fahren;
Weiche umstellen.
49
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAufgabe 2 - Lösungsvorschlag Aufgabe 2 - Lösungsvorschlag
AZ: { A: [a]; B: [b]; C: [c] }
H := A
A := C
C := B
B := H
EZ: { A: [c]; B: [a]; C: [b] }
Abstraktes Rangierproblem:
Gegeben sind drei Variablen A, B und C. Die Werte der Variablen sollen wie folgt ausgetauscht werden:
a
b
c
A:
B:
C:
50
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAufgabe 3 - LösungsvorschlagAufgabe 3 - Lösungsvorschlag
B := A
A := B
Vertauschungsproblem:
Die Werte der Variablen A und B sollen ausgetauscht werden:
AZ: { A: [a]; B: [b] }
EZ: { A: [b]; B: [a] }
H := A
A := B
B := H
C := A
D := B
A := D
B := C
A := A - B
B := A + B
A := B - A
nicht korrekt
Korrektgrößter Aufwand
Korrektkleinster Aufwand
Korrekt nur für Zahl-Variablen
51
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAufgabe 5 - LösungsvorschlagAufgabe 5 - Lösungsvorschlag
BEGINReadln(A);Readln(B);REPEAT WHILE A > B DO A := A – B; WHILE B > A DO B := B – A;UNTIL A = BWriteln(A);END
Anw. A BReadln(A) 10Readln(B) 10 24A > B ? FB > A ? WB := B - A 10 14B > A ? WB := B - A 10 4B > A ? FA = B ? FA > B ? WA := A - B 6 4A > B ? WA := A - B 2 4A > B ? FB > A ? WB := B - A 2 2B > A ? FA = B ? WWriteln(A) --> 2
52
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAufgabe 6 - LösungsvorschlagAufgabe 6 - Lösungsvorschlag
Problem:
Eine Folge positiver Zahlen soll eingelesen und ihr Minimum berechnet und ausgegeben werden. Das Ende der Folge wird durch die Eingabe der Zahl 0 erkannt.
Eingabe: zmin := zSOLANGE z > 0 Eingabe: z WENN z < min DANN min := zAusgabe: min
Die Eingabefolge 3, 0 liefert die Ausgabe 0. Der Algorithmus ist also nicht korrekt.
Eingabe: zmin := zSOLANGE z > 0 WENN z < min DANN min := z Eingabe: zAusgabe: min
Die Eingabefolge 3, 0 liefert jetzt die Ausgabe 3 - so, wie es sein soll.
53
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nTeil 4Teil 4
Schleifentypen
54
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nKapitalberechnungenKapitalberechnungen
Mit Hilfe eines Programms soll die Kapitalentwicklung bei einer Verzinsung mit einem festen Zinssatz von p = 3% berechnet werden.
Problemspezifikation 1:Eingaben : Anfangskapital, Anzahl der JahreAusgabe : erreichtes Endkapital
Problemspezifikation 2:Eingaben : Anfangskapital, EndkapitalAusgabe : Anzahl der benötigten Jahre
Mit Hilfe eines Programms soll die Kapitalentwicklung bei einer Verzinsung mit einem festen Zinssatz von p = 3% berechnet werden.
Problemspezifikation 1:Eingaben : Anfangskapital, Anzahl der JahreAusgabe : erreichtes Endkapital
Problemspezifikation 2:Eingaben : Anfangskapital, EndkapitalAusgabe : Anzahl der benötigten Jahre
55
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProgramm „Kapital1“Programm „Kapital1“
...
BEGIN{ Eingaben }write('Anfangskapital : '); readln(Kapital);write('Anzahl der Jahre : '); readln(Jahre);
{ Berechnungen }Zaehler := 1;WHILE Zaehler <= Jahre DO BEGIN Kapital := Kapital + Kapital * p/100; Zaehler := Zaehler + 1; END;
{ Ausgaben }writeln('Endkapital : ', Kapital:8:2);readln;END.
56
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProgramm „Kapital2“Programm „Kapital2“
...
BEGIN{ Eingaben }write('Anfangskapital : '); readln(Kapital);write('Anzahl der Jahre : '); readln(Jahre);
{ Berechnungen }FOR Zaehler := 1 TO Jahre DO Kapital := Kapital + Kapital * p/100;
{ Ausgaben }writeln('Endkapital : ', Kapital:8:2);readln;END.
57
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProgramm „Kapital3“Programm „Kapital3“
...
BEGIN{ Eingaben }write('Anfangskapital : '); readln(Kapital);write('Anzahl der Jahre : '); readln(Jahre);
{ Berechnungen }FOR Zaehler := JAHRE DOWNTO 1 DO Kapital := Kapital + Kapital * p/100;
{ Ausgaben }writeln('Endkapital : ', Kapital:8:2);readln;END.
58
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
n
falsch
ZählschleifeZählschleife
Ausgabe: Kapital
Eingabe: Kapital, Jahre
Kapital := Kapital + ...
Zaehler := Zaehler + 1
SOLANGE Zaehler <= Jahre
Zaehler := 1
Zaehler<=Jahre
wahr
Kapital := Kapital + ...
Zaehler := Zaehler + 1
Eingabe: Kapital, Jahre
Zaehler := 1
Ausgabe: KapitalAusgabe: Kapital
Eingabe: Kapital, Jahre
Kapital := Kapital + ...
FÜR Zaehler VON 1 BIS Jahre
59
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProgramm „Kapital4“Programm „Kapital4“
...
BEGIN{ Eingaben }write('Anfangskapital : '); readln(Anfangskapital);write('Endkapital : '); readln(Endkapital);
{ Berechnungen }Kapital := Anfangskapital;Jahre := 0;WHILE Kapital < Endkapital DO BEGIN Kapital := Kapital + Kapital * p/100; Jahre := Jahre + 1; END;
{ Ausgaben }writeln('Anzahl der Jahre : ', Jahre);readln;END.
60
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProgramm „Kapital5“Programm „Kapital5“
...
BEGIN{ Eingaben }write('Anfangskapital : '); readln(Anfangskapital);write('Endkapital : '); readln(Endkapital);
{ Berechnungen }Kapital := Anfangskapital;Jahre := 0;REPEAT Kapital := Kapital + Kapital * p/100; Jahre := Jahre + 1;UNTIL Kapital >= Endkapital;
{ Ausgaben }writeln('Anzahl der Jahre : ', Jahre);readln;END.
61
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nWiederholungWiederholung
Ausgabe: Jahre
Eingabe: AKapital, EKapital
Kapital := Kapital + ...
Jahre := Jahre + 1
SOLANGE Kapital < EKapital
Kapital := AKapital
Jahre := 0
Ausgabe: Jahre
Eingabe: AKapital, EKapital
Kapital := Kapital + ...
Jahre := Jahre + 1BIS Kapital >= EKapital
Kapital := AKapital
Jahre := 0
Wiederholung mit Anfangsbedingung
Wiederholung mit Endbedingung
62
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
n
falsch
WiederholungWiederholung
Kapital<EKapital
wahr
Kapital := Kapital + ...
Jahre := Jahre + 1
Eingabe: AKapital, EKapital
Jahre := 0
Ausgabe: Jahre
Kapital := AKapital
falschKapital>=EKapit
alwahr
Kapital := Kapital + ...
Jahre := Jahre + 1
Eingabe: AKapital, EKapital
Jahre := 0
Ausgabe: Jahre
Kapital := AKapital
63
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
n
Wiederholung mit Wiederholung mit AnfangsbedingungAnfangsbedingung
WHILE <Bedingung> DO
<Anweisung>
PASCAL
SOLANGE Bed.
Anweisung
Struktogramm
PAP
Bed.
Anw
w
f
Beachte:
Erst Bedingung überprüfen, dann Anweisung ausführen!
64
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nWiederholung mit EndbedingungWiederholung mit Endbedingung
REPEAT
<Anweisung>
UNTIL <Bedingung>
PASCAL
Anweisung
BIS Bedingung
Struktogramm
PAP
Bed.
Anw.
wf
Beachte:
Erst Anweisung ausführen, dann Bedingung überprüfen!
Die Anweisung wird mindestens einmal ausgeführt.
65
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAchtung: EndlosschleifeAchtung: Endlosschleife
...
BEGIN{ Eingaben }write('Anfangskapital : '); readln(Anfangskapital);write('Endkapital : '); readln(Endkapital);
{ Berechnungen }Kapital := Anfangskapital;Jahre := 0;WHILE Kapital < Endkapital DO BEGIN Jahre := Jahre + 1; END;
{ Ausgaben }writeln('Anzahl der Jahre : ', Jahre);readln;END.
66
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nTeil 5Teil 5
Fallunterscheidungstypen
67
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nRückerstattungsberechnungenRückerstattungsberechnungen
Mit Hilfe eines Programms soll der Rückerstattungsbeitrag bei einer Versicherung berechnet werden. Folgende Rückerstattungssätze seien vereinbart:0 bis 3 Jahre: 0 %4 bis 5 Jahre: 10 %mehr als 5 Jahre: 15 %
Problemspezifikation:Eingaben : Versicherungsbetrag, VersicherungsdauerAusgabe : Rückerstattungsbetrag
Mit Hilfe eines Programms soll der Rückerstattungsbeitrag bei einer Versicherung berechnet werden. Folgende Rückerstattungssätze seien vereinbart:0 bis 3 Jahre: 0 %4 bis 5 Jahre: 10 %mehr als 5 Jahre: 15 %
Problemspezifikation:Eingaben : Versicherungsbetrag, VersicherungsdauerAusgabe : Rückerstattungsbetrag
68
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProgramm „Beitrag1“Programm „Beitrag1“
...
BEGIN{ Eingaben }write('Versicherungsbetrag : '); readln(Betrag);write('Versicherungsdauer : '); readln(Dauer);
{ Berechnungen }IF Dauer <= 3 THEN Erstattung := 0ELSE IF Dauer <= 5 THEN Erstattung := 0.1 * Betrag ELSE Erstattung := 0.15 * Betrag;
{ Ausgaben }writeln('Rückerstattung : ', Erstattung:6:2);readln;END.
69
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nZweiseitige FallunterscheidungenZweiseitige Fallunterscheidungen
Ausgabe: E(erstattung)
Eingabe: B(etrag), D(auer)
D <= 3
D <= 5
E := 0.1 * B E := 0.15 * BE := 0
wahr falsch
wahr falsch
...IF Dauer <= 3 THEN Erstattung := 0ELSE IF Dauer <= 5 THEN Erstattung := 0.1 * Betrag ELSE Erstattung := 0.15 * Betrag;...
70
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nProgramm „Beitrag2“Programm „Beitrag2“
...
BEGIN{ Eingaben }write('Versicherungsbetrag : '); readln(Betrag);write('Versicherungsdauer : '); readln(Dauer);
{ Berechnungen }IF (Dauer >= 0) AND (Dauer <= 3) THEN Erstattung := 0;IF (Dauer = 4) OR (Dauer = 5) THEN Erstattung := 0.1*Betrag;IF Dauer > 5 THEN Erstattung := 0.15 * Betrag;
{ Ausgaben }writeln('Rückerstattung : ', Erstattung:6:2);readln;END.
71
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nEinseitige FallunterscheidungenEinseitige Fallunterscheidungen
Ausgabe: E(erstattung)
Eingabe: B(etrag), D(auer)
D >= 0 UND D <= 3
E := 0
wahr falsch
...IF (Dauer >= 0) AND (Dauer <= 3) THEN Erstattung := 0;IF (Dauer = 4) OR (Dauer = 5) THEN Erstattung := 0.1*Betrag;IF Dauer > 5 THEN Erstattung := 0.15 * Betrag;...
D = 4 ODER D = 5
E := 0.1 * B
wahr falsch
D > 5
E := 0.15 * B
wahr falsch
72
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nMehrfachauswahlMehrfachauswahl
Ausgabe: E(erstattung)
Eingabe: B(etrag), D(auer)
D
0..3
E := 0 E := 0.1 * B E := 0.15 * B
...CASE Dauer OF 0..3 : Erstattung := 0; 4,5 : Erstattung := 0.1 * Betrag; ELSE Erstattung := 0.15 * Betrag;END;...
4,5 sonst.
73
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nEinseitige FallunterscheidungEinseitige Fallunterscheidung
IF <Bedingung>
THEN <Anweisung>
PASCAL
Bed.w f
Struktogramm
PAP
Anw
Bed.
Anw
w f
74
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nZweiseitige FallunterscheidungZweiseitige Fallunterscheidung
IF <Bedingung>
THEN <Anweisung1>
ELSE <Anweisung2>
PASCAL
Bed.w f
Struktogramm
PAP
Anw1 Anw2
Bed.
Anw1 Anw2
w f
75
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nMehrfachauswahlMehrfachauswahl
CASE <Ausdruck> OF
<Wert1>: <Anweisung1>;<Wert2>: <Anweisung2>;...ELSE <Anweisung>
END
PASCAL
Ausdruck
Wert1 Wert2 sonst.
Struktogramm
Anw1 Anw2 ... Anw
Beachte:
Der Ausdruck muss „aufzählbare“ Ergebnisse liefern.
76
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 9Übungen - Aufgabe 9
Problem:
Eine Folge nicht-negativer Zahlen soll eingelesen und ihre Summe berechnet und ausgegeben werden. Das Ende der Folge wird durch die Eingabe einer negativen Zahl erkannt.
Bsp.: Eingabefolge: 3, 6, 0, 7, -1 Ausgabe: 16Eingabefolge: -1 Ausgabe: 0
Erstellen Sie einen Algorithmus mit einer WHILE-Schleife und einen Algorithmus mit einer REPEAT-Schleife. Warum kann der Algorithmus nicht mit einer FOR-Schleife erstellt werden? Kontrollieren Sie die Korrektheit der erstellten Algorithmen mit Hilfe einer Trace-Tabelle. Implementieren Sie einen Algorithmus in Pascal und testen Sie seine Korrektheit.
77
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 10Übungen - Aufgabe 10
A) Worin besteht der Unterschied zwischen den beiden folgenden Anweisungen?
IF B1 THEN IF B2 THEN A1 ELSE A2IF B1 THEN BEGIN IF B2 THEN A1 END ELSE A2
B) Worin besteht der Unterschied zwischen den beiden folgenden Anweisungen?
IF B THEN A1; A2IF B THEN BEGIN A1; A2 END
C) Was ist hier falsch?
IF B THEN A1; ELSE A2IF B THEN A1; A2 ELSE A3
78
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAufgabe 9 - LösungsvorschlagAufgabe 9 - Lösungsvorschlag
Summe := 0Eingabe: zSOLANGE z >= 0 Summe := Summe + z Eingabe: zAusgabe: Summe
Summe := 0Eingabe: zWENN z >= 0 DANN WIEDERHOLE Summe := Summe + z Eingabe: z BIS z < 0Ausgabe: Summe
79
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAufgabe 10 - LösungsvorschlagAufgabe 10 - Lösungsvorschlag
A) Worin besteht der Unterschied zwischen den beiden folgenden Anweisungen?
IF B1 THEN IF B2 THEN A1 ELSE A2
IF B1 THEN BEGIN IF B2 THEN A1 END ELSE A2
80
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAufgabe 10 - LösungsvorschlagAufgabe 10 - Lösungsvorschlag
B) Worin besteht der Unterschied zwischen den beiden folgenden Anweisungen?
IF B THEN A1; A2
IF B THEN BEGIN A1; A2 END
C) Was ist hier falsch?
IF B THEN A1; ELSE A2IF B THEN A1; A2 ELSE A3
Ende der Anweisung
81
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nTeil 6Teil 6
Datentypen
82
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nSiebzehn-und-VierSiebzehn-und-Vier
Ziel ist es, das Spiel „17 und 4“ zu simulieren. Das Spiel soll wie folgt funktionieren:In jedem Spielzug wird eine Karte mit einer Zahl aus dem Bereich [1;...;11] bestimmt und auf einen Kartenstapel gelegt. Der Spieler kann nach jedem Spielzug entscheiden, ob er aufhört oder weiter spielt. Ist die Summe der Zahlen der Karten des Stapels größer als 21, so hat der Spieler verloren. Hört der Spieler bei einer Stapelsumme kleiner oder gleich 21 auf, so wird die nächste Karte gezogen. Ist die neue Stapelsumme immer noch kleiner oder gleich 21, so hat der Spieler verloren, andernfalls gewonnen.
Ziel ist es, das Spiel „17 und 4“ zu simulieren. Das Spiel soll wie folgt funktionieren:In jedem Spielzug wird eine Karte mit einer Zahl aus dem Bereich [1;...;11] bestimmt und auf einen Kartenstapel gelegt. Der Spieler kann nach jedem Spielzug entscheiden, ob er aufhört oder weiter spielt. Ist die Summe der Zahlen der Karten des Stapels größer als 21, so hat der Spieler verloren. Hört der Spieler bei einer Stapelsumme kleiner oder gleich 21 auf, so wird die nächste Karte gezogen. Ist die neue Stapelsumme immer noch kleiner oder gleich 21, so hat der Spieler verloren, andernfalls gewonnen.
83
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nSpielablaufSpielablauf
Karte: 8
Summe: 8
Noch eine Karte? (j/n): jKarte: 5
Summe: 13
Noch eine Karte? (j/n): jKarte: 4
Summe: 17
Noch eine Karte? (j/n): jKarte: 6 | 4
Summe: 23 | 21
verloren | gewonnen
Karte: 6
Summe: 23
gewonnen
Karte: 3
Summe: 20
verloren
Karte: 8
Summe: 8
Noch eine Karte? (j/n): jKarte: 5
Summe: 13
Noch eine Karte? (j/n): jKarte: 4
Summe: 17
Noch eine Karte? (j/n): n
Noch eine Karte? (j/n):
84
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAblaufmodellierungAblaufmodellierung
WIEDERHOLE
Karte ziehen; Summe bestimmen
WENN Summe < 21 DANN
Ausgabe: ‘ Noch eine Karte? (j/n): ‘
Eingabe: Antwort
BIS Summe >= 21 oder Antwort = ‘ n‘
WENN Summe >= 21 DANN
WENN Summe > Ausgabe: ‘ verloren ‘
SONST Ausgabe: ‘ gewonnen ‘
SONST Karte ziehen; Summe bestimmen
WENN Summe > 21 DANN Ausgabe: ‘ gewonnen ‘
SONST Ausgabe: ‘ verloren ‘
85
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nDatenmodellierungDatenmodellierung
Karte: integer (ganze Zahl)
Summe: integer (ganze Zahl)
Antwort: char (Zeichen)
10
14
‘n‘
86
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAlgorithmus - Version 1, Teil 1Algorithmus - Version 1, Teil 1
Karte := random(11)+1 {Zufallszahl aus Bereich 1..11}
Summe := Summe + Karte
Ausgabe: Karte, Summe
randomize {Initialisierung des Zufallsgenerators}
Summe := 0
Ausgabe: ‘Noch eine Karte?‘
Eingabe: AntwortBIS (Summe >= 21) OR (Antwort = ‘n‘)
Summe < 21wahr falsch
87
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAlgorithmus - Version 1, Teil 2Algorithmus - Version 1, Teil 2
Summe >= 21wahr falsch
Summe > 21falsch
Ausg.: ‘verl.‘ Ausg.: ‘gew.‘
wahrKarte := random(11)+1
Summe := Summe + Karte
Ausgabe: Karte, Summe
Summe > 21falsch
Ausg.: ‘gew.‘ Ausg.: ‘verl.‘
wahr
88
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nSpielablaufSpielablauf
Karte: 8
Summe: 8
Noch eine Karte? (j/n): jKarte: 5
Summe: 13
Noch eine Karte? (j/n): jKarte: 4
Summe: 17
Noch eine Karte? (j/n): jKarte: 6 | 4
Summe: 23 | 21
Spiel entschieden
Karte: 6
Summe: 23
gewonnen
Karte: 3
Summe: 20
verloren
Karte: 8
Summe: 8
Noch eine Karte? (j/n): jKarte: 5
Summe: 13
Noch eine Karte? (j/n): jKarte: 4
Summe: 17
Noch eine Karte? (j/n): n
Noch eine Karte? (j/n):
Benutzer hat genug
verloren | gewonnen
89
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nDatenmodellierungDatenmodellierung
Karte: integer (ganze Zahl)
Summe: integer (ganze Zahl)
Antwort: char (Zeichen)
entschieden: boolean (Wahrheitswert)
genug: boolean (Wahrheitswert)
10
14
‘n‘
true
false
90
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAlgorithmus - Version 2, Teil 1Algorithmus - Version 2, Teil 1
Karte := random(11)+1 {Zufallszahl aus Bereich 1..11}
Summe := Summe + Karte
Ausgabe: Karte, Summe
randomize {Initialisierung des Zufallsgenerators}
Summe := 0
entschieden := false
genug := false
Ausgabe: ‘Noch eine Karte?‘
Eingabe: Antwort
BIS entschieden OR genug
NOT entschiedenwahr falsch
entschieden := true
Summe >= 21wahr falsch
Antwort = ‘ n‘ f
genug :=true
w
91
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAlgorithmus - Version 2, Teil 1Algorithmus - Version 2, Teil 1
Karte := random(11)+1 {Zufallszahl aus Bereich 1..11}
Summe := Summe + Karte
Ausgabe: Karte, Summe
entschieden := (Summe >= 21)
randomize {Initialisierung des Zufallsgenerators}
Summe := 0
Ausgabe: ‘Noch eine Karte?‘
Eingabe: Antwort
genug := (Antwort = ‘ n‘)BIS entschieden OR genug
NOT entschiedenwahr falsch
92
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nAlgorithmus - Version 2, Teil 2Algorithmus - Version 2, Teil 2
entschiedenwahr falsch
Summe > 21falsch
Ausg.: ‘verl.‘ Ausg.: ‘gew.‘
wahrKarte := random(11)+1
Summe := Summe + Karte
Ausgabe: Karte, Summe
Summe > 21falsch
Ausg.: ‘gew.‘ Ausg.: ‘verl.‘
wahr
93
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nDatentypenDatentypen
Ein Datentyp legt einen Wertebereich und die Grundoperationen, die auf die Elemente des Wertebereichs angewandt werden können, fest.
Ein Datentyp legt einen Wertebereich und die Grundoperationen, die auf die Elemente des Wertebereichs angewandt werden können, fest.
Beispiele (für elementare Datentypen):
> boolean (Wahrheitswert)
> char (Zeichen)
> integer (ganze Zahl)
> real (Dezimalzahl)
94
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nDatentyp booleanDatentyp boolean
Wertebereich: {false; true}
Grundoperationen: NOT, AND, OR
a b a AND b
false false falsefalse true falsetrue false falsetrue true true
a NOT a
false truetrue false
a b a OR b
false false falsefalse true truetrue false truetrue true true
95
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nDatentyp charDatentyp char
Wertebereich: ... siehe ASCII-Tabelle ...
Code Zeichen Code ZeichenCode Zeichen
0 NUL 33 ! 65 A... ... 66 B4 EOT 40 ( ...... ... 90 Z13 CR 48 0 ...... 49 1 97 a27 ESC ... 98 b... 57 9 ...... ... 122 z... ... ...
96
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nDatentyp charDatentyp char
Grundoperationen: ord, chr, succ, pred, =, >, <, <>, >=, <= (De)Kodieroperationen:
ord: char {0; ...; 255} z.B.: ord(´A´) 65
chr: {0; ...; 255} char z.B.: chr(65) ´A´
Ordnungsoperationen:
succ: char char z.B.: succ(´A´) ´B´
pred: char char z.B.: pred(´A´) ´@´
Vergleichsoperationen:
=: char, char boolean z.B.: ´A´ = ´A´ true
>: char, char boolean z.B.: ´A´ > ´B´ false
...
97
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nDatentyp integerDatentyp integer
Wertebereich: -32768; ...; 32767
Grundoperationen: +, -, *, div, mod, succ, pred, =, >, <, ... Divisionsoperationen:
div: ganzzahlige Division
20 div 6 = 380 div 7 = 11
mod: Rest bei der ganzzahligen Division
20 mod 6 = 280 mod 7 = 3
98
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nDatentyp realDatentyp real
Wertebereich: ..., 1.0; -4.56; 6.3E16; -6.3E-16; ...
Grundoperationen: +, -, *, /, =, >, <, ..., round, trunc, sqr, ... Beispiele:
round: real integer (Runden)
round(3.84) = 4
trunc: real integer (Abschneiden)
trunc(3.84) = 3
int: real real (ganzer Teil)
int(3.84) = 3.0
frac: real real (Nachkommateil)
frac(3.84) = 0.84
99
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nTypumwandlungTypumwandlung
integer real: erfolgt automatisch
Bsp.: VAR r: real; r := 3;
real integer: trunc, round
char integer: ord
integer char: chr
100
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 11Übungen - Aufgabe 11
Miniprojekt Mäusepopulation:
Der Algorithmus / das Programm zur Beschreibung der Entwicklung der Mäusepopulation soll wie folgt abgeändert werden:
Der Benutzer kann wiederholt die Entwicklung einer Population starten. Er kann dabei jedesmal die Anfangspopulation und die Anzahl der Schritte eingeben und entscheiden, wie die Ergebnisse ausgegeben werden:
A) absolute Werte: jung: 34; ...
B) prozentuale Werte: Gesamtanzahl: 123; jung: 30%; ...
C) grafische Darstellung von Anteilen: Gesamtanzahl: 145 jung: XXXXXX erwachsen: XXXXXXXXXX alt: XXX
101
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nÜbungen - Aufgabe 12Übungen - Aufgabe 12
Miniprojekt Zahlenraten:
Der Benutzer soll eine vom Programm vorgegebene Zahl aus dem Intervall [0; 100] mit maximal 8 Rateversuchen ermitteln. Das Programm gibt nach jedem Rateversuch eine passende Rückmeldung.
Erweiterungen:
A) Führen Sie eine Variable „geraten“ vom Typ boolean ein, mit deren Hilfe das Programm gut lesbar gestaltet werden kann.
B) Der Benutzer kann wiederholt das Ratespiel durchführen, ohne das Programm neu starten zu müssen.
C) Der Benutzer kann selbst das Intervall, aus dem die zu erratende Zahl stammt, festlegen. Die Anzahl der Rateversuche muss dann natürlich entsprechend angepasst werden.
102
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nTeil 7Teil 7
Hinweise zum algorithmischen Problemlösen
103
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nEin erstes PhasenschemaEin erstes Phasenschema
Spezifikation des Problems
Entwicklung eines
Algorithmus
Implementierung des Algorithmus
Validierung des Algorithmus
104
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nSpezifikation des ProblemsSpezifikation des Problems
Hinweise:
Das Problem sollte möglichst genau und eindeutig beschrieben werden.
Beschreibungstechniken:
AZ: ... VariablenwerteZZ: ... Variablenwerte; Bildschirmgestaltung
Eingaben: ...Ausgaben: ...
105
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nEntwicklung eines AlgorithmusEntwicklung eines Algorithmus
Hinweise:
- sich Klarheit über die zu bearbeitenden und verwendenden Daten verschaffen
- sich mögliche Abläufe klar machen (typische Fälle / extreme Fälle)
- eine Ablaufbeschreibung mit Hilfe von Kontroll- strukturen konstruieren
Entwurfsmethoden:
(top-down; bottom-up; objektorientiert; ...)
106
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nImplementierung des AlgorithmusImplementierung des Algorithmus
Hinweise:
Programme sollten gut strukturiert sein:- Verschiedene Teile des Algorithmus sollten optisch voneinander abgesetzt werden.- Die Struktur des Algorithmus sollte durch systematisches Einrücken optisch sichtbar gemacht werden.
Programme sollten gut lesbar sein:- sinntragende Bezeichner wählen- entscheidenden Stellen kommentieren
107
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nValidierung des AlgorithmusValidierung des Algorithmus
Hinweise:
Validierung während der Erstellung: - Überprüfung mit Trace-Tabellen
Validierung nach der Implementierung:- durch systematisches Testen (der Standardfälle, Sonderfälle, ...)
108
KB
Alg
ori
thm
isch
e
Gru
ndst
rukt
ure
nLiteraturhinweiseLiteraturhinweise
Es gibt eine Vielzahl guter Einführungen in die Thematik „Algorithmische Grundstrukturen“. Manche entwickeln die Grundstrukturen ohne Anbindung an eine Programmiersprache, viele verdeutlichen sie parallel an gängigen und aktuellen Sprachen (früher oft Pascal, heute vermehrt Java, Delphi, ...). Einige Beispiele:
- Rüdeger Baumann: Informatik für die Sekundarstufe II, Klett-Verlag.
- Ocker / Schöttle / Simon: Algorithmen und ihre Programmierung in Pascal. Oldenbourg Verlag.
- Laubach / Knoch: Grundkurs Informatik 1 / 2. bsv-Verlag.
- Helmut Balzert: Lehrbuch Grundlagen der Informatik. Spektrum-Verlag.
- Gumm / Sommer: Einführung in die Informatik. Addison-Wesley.