PMG/Sammlung alt

Wiki-Quelltext dieser Seite.

<language>Pascal</language>
== "Sortieren" - Vergleich zweier Zahlen ==

<font size=1>(Ein Beispiel aus der Wissenschaftlichen Arbeit im Fach Informatik "Bildungsstandards Informatik - Aufgaben für den Unterricht zum Thema "Algorithmen" von Stefan Renz, TU Dresden, 2010)</font>

Am Kölner Dom wurde über 600 Jahre gebaut, als er 1880 fertig wurde, war er
allerdings nur für vier Jahre das höchste Gebäude der Welt. Hier eine Auswahl
sehr hoher Gebäude:

{| border="0"
 |-
 | '''Name''' || '''Höhe''' 
 |-
 | Kölner Dom || 157m
 |-
 | Eiffelturm || 300m
 |-
 | Cheops-Pyramide|| 147m
 |-
 | Burj Khalifa|| 828m
|-
 | Washington Monument|| 169m
|-
 | Sendemast Radio Warschau || 646m
|-
 | Empire State Building || 449m

 |}


# Überlege Dir einen Algorithmus, der zwei Zahlen als Eingabe verarbeitet und die größere von beiden als Ergebnis ausgibt. Halte diesen Algorithmus als Struktogramm fest.
# Was passiert bei Deinem Algorithmus, wenn die beiden Zahlen gleich groß sind?
# Setze den Algorithmus in der vorbereiteten Box um.


<code id="4cc726df708e4"></code>

<eval id="4cc726df709fc"></eval>

== Potenz und Betrag/Abstand ==


Gegeben ist folgendes Struktogramm. 
[[Bild:Struktogramm(v2).JPG]]

Teste den dargestellten Algorithmus mit den Werten x = 5, y = 8 und z = 3 sowie anderen, selbst gewählten Werten. 
Erläutere die Bedeutung der Variablen.<br>
Schreibe Deine Antwort in die Box hinter ''write'':

<eval id="4cc728e2c48fd">
begin 
write('  ');
end.
</eval>


Implementiere den dargestellten Algorithmus in der nachfolgenden Box als function ''xyz1'' (Teilalgorithmus '''Potenz''')<br>
<code id="4cc728e2c47c5">
function xyz1(
</code>

<eval id="4cc728e2c4a12">
begin
writeln(inttostr(xyz1(...)));
end.
</eval>


Implementiere den zweiten Teil des Algorithmus in der nachfolgenden Box als function ''xyz2'' (Teilalgorithmus '''Betrag/Abstand''')
<code id="4cda69bd019f1">
function xyz2(
</code>

<run id="4f62550ebabd8">
begin
writeln(inttostr(xyz2(...)));
end.
</run>

== Zufallszahlen und Würfelspiele ==


In den nächsten (letzten) Übungen mit dem PWiki werden wir noch ein paar "Spiele" mit Zufallszahlen erstellen.
Anschließend werden wir mit einer Anwendersoftware (Fischer-Technik) Modelle bauen und steuern!

Doch zunächst:

=== Erzeugen von Zufallszahlen ===



<code id="4cec1965a9796">
function zufall(a:integer):integer;
begin
result:=random(a);
end;
</code>



<eval id="4cec1965a9ae3">
begin
writeln(inttostr(zufall(100)));
end.

</eval>



=== Würfeln ===


Nun sollen nur Ergebnisse zufällig erzeugt werden, wie sie an einem idealen Würfel eintreten können.<br>
Ergänze die Boxen analog dem obigen Beispiel und teste das Ergebnis.<br>

<code id="4cec1965a98b5">
function wurf(a:integer):integer;
begin

end;
</code>



<eval id="4cec1965a9bf2">
begin
// dein Text
end.

</eval>



Simuliere nun ein Würfelspiel mit einem idealen Würfel.
Für eine Anzahl <math>n</math> von Würfen soll die Anzahl aller geworfenen Augenzahlen ausgegeben werden.<br>
 ''Hinweis:'' Es soll also für jede mögliche Augenzahl eine Variable vereinbart werden, eine beliebige Anzahl von (simulierten)
 Versuchen durchgeführt werden und die ''Anzahl'' der gewürfelten Einsen, Zweien, ..., Sechsen ausgegeben werden.

Stelle den notwendigen Algorithmus in einem Struktogramm dar.<br>
Benutze dazu das Tool ''structorizer''.
* Erstelle mit dem Programm das Struktogramm
* Speichere das Struktogramm als Bild (Format .jpg) 
* füge dein Bild im PWiki ein
<br>

{| border="1"
 |-
 | [[Bild:Struktugramm.jpg|Miniatur|250px]] ||  ||[[Bild:Nmalwürfeln.jpg|Miniatur|250px]]
 |-
 | Lucie || Martin || Jennifer
 |-
 | [[Bild:Wurf.jpg|Miniatur|250px]] || [[Bild:Würfel.jpg|Miniatur|250px]] || [[Bild:Wuerfelspiel.jpg|Miniatur|250px]]
 |-
 | Till || Florian || Sebastian
 |-
 | [[Bild:Wuerfeln.jpg|Miniatur|100px]]|| [[Bild:Wuerfel.jpg|Miniatur|100px]] || [[Bild:Structoricer.jpg|Miniatur|250px]]
 |-
 | Ivan || Ronny || Marko
 |-
 | [[Bild:Zufall-Würfeln.jpg|Miniatur|100px]]|| [[Bild:Würfeln_matschi.jpg|Miniatur|250px]] || [[Bild:Würfel2.jpg|Miniatur|100px]]
 |-
 | Claudia || Maximilian || Lucas
 |}


<code id="4cec1965a99c4">

</code>


<eval id="4cec1965a9d02">


</eval>


'''Wir stellen fest, dass eine ''function'' nur einen Wert (ein Resultat) zurückliefern kann.'''<br>
'''Daher brauchen wir eine weitere Möglichkeit, die mehrere Ergebnisse liefert.'''<br>
Dies geschieht unter Verwendung einer <font color="darkgreen">''procedure''</font>, wobei die Rückgabewerte (Ergebnisvariablen) mit ''var'' angefügt werden (vergleiche Box).


<code id="4d243865b3fab">
procedure wuerfeln(n:integer;var a,b,c,d,e,f:integer);
</code>


<eval id="4d243865b40ec">

</eval>



Formuliere anhand der Simulation eine Aussage über die Wahrscheinlichkeit der einzelnen Ergebnisse beim Würfeln.


<font color="darkgreen">'''''zum Weiterarbeiten:'''''</font> Zeige durch eine analoge Simulation, dass die Zufallsgröße "[[Augensumme beim Würfeln mit zwei idealen Würfeln]]" nicht gleichverteilt ist.
<br><br>

Die Bezeichnung ''Algorithmus'' geht auf den Namen '''Muhammad ibn Musa, Abu Dscha'far al-Chwarizmi''' (* um 780; † um 850), einem persischen Mathematiker, Astronomen und Geographen, zurück.
Diesem Universalgelehrten verdanken wir nicht nur die Einführung der Null aus dem indischen in das arabische Zahlensystem, sondern auch das Wort "Algebra", das der lateinischen Übersetzung seines Buches ''Kitāb al-muchtasar fi hisab al-dschabr wa-l-muqabala'' ("Rechnen durch Ergänzung und Ausgleich") entnommen ist.<br /><br />

== Der Algorithmusbegriff ==

Es existiert eine Vielzahl von Versuchen einer Definition für den Begriff ''Algorithmus''.<br />
z.B.:
<ol>
<li>Als ”Algorithmus [..] bezeichnet [man] heute in der Arithmetik einen Rechenvorgang (bzw.
die ihn beschreibenden Regeln) der nach einem bestimmten sich wiederholenden
Schema abläuft" (Meyers Enzyklopädie, 1971)
</li>
<li>”Ein Algorithmus [..] ist eine vollständige, präzise und in einer Notation oder
Sprache mit exakter Definition abgefasste, endliche Beschreibung eines schritt-
weisen Problemlösungsverfahrens zur Ermittlung gesuchter Datenobjekte (ihrer
Werte) aus gegebenen Werten von Datenobjekten, in dem jeder Schritt aus
einer Anzahl ausführbarer, eindeutiger Aktionen und einer Angabe über den
nächsten Schritt besteht.”(Pomberger, Gustav; Dobler, Heinz: Algorithmen und Datenstrukturen - Eine
systematische Einführung in die Programmierung. München : Pearson Education Deutschland GmbH, 2008)
</li>
<li>”Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen
Lösung eines Problems.”(Gumm, Heinz P.; Sommer, Manfred: Einführung in die Informatik. München :
Oldenbourg Wissenschaftsverlag, 2006)
</li>
</ol>

Wir begnügen uns mit einer anschaulichen ''(intuitiven)'' Erklärung:

<b>''Ein Algorithmus ist eine endliche Folge von eindeutigen und ausführbaren Anweisungen zur Lösung eines allgemeinen Problems.''</b><br>


== Eigenschaften von Algorithmen ==

<ol>
<li>'''Endlichkeit: (Finitheit)'''
* endliche Notation des Algorithmus, (statische Endlichkeit)
* Nutzung endlicher Ressourcen (z.B. begrenzter Arbeitsspeicher / begrenzte Rechenzeit) - dynamische Endlichkeit
</li>
<li>'''Terminiertheit'''
* endlich viele Abarbeitungsschritte - Endlichkeit im Ablauf (z.B. begrenzte Rekursionstiefe), der Algorithmus liefert also bei jeder Anwendung nach endlich vielen Verarbeitungsschritten ein Resultat <br>
* Bei Nichterfüllung: Endlosschleife (Ausnahmen: OS; interaktive Programme)
</li>
<li>'''Deterministisch'''
* nach jedem Abarbeitungsschritt besteht höchstens eine Möglichkeit der Fortsetzung
</li>
<li>'''Eindeutigkeit: (Determiniertheit)'''
* gleiche Eingabegrößen und Anfangsbedingungen liefern stets das gleiche Ergebnis
</li>
<li>'''Ausführbarkeit:'''
* jede Anweisung ist (z.B. für einen Prozessor) verständlich und ausführbar
</li>
<li>'''Allgemeingültigkeit:'''
* Anwendbarkeit auf gleiche Probleme einer Problemklasse.
</li>
</ol>




== Beispiele ==


=== Syntax von Funktionen ===


Beispiel für eine Funktion in einer imperativen Programmierumgebung

[[Bild:Function.JPG]]

Aufruf der Funktion im Hauptprogramm

[[Bild:Function_2.JPG]]

<br />
''hier nun Beispiele für die Syntax im PWIKI''




=== einfache Addition ===

<code id="4bc596ef036ea">
function addi(a,b:integer):integer;
begin
result:=a+b;
end;
</code>

<eval id="4bc596ef084eb">
begin
writeln(inttostr(addi(3,4)));
end.
</eval>

''Ergänze die ähnliche Funktion addi3 zur Bildung der Summe dreier reeller Zahlen!''

<code id="4bccb71f47f51">
function addi33 (a,b,c:integer):integer;
begin
result:=a+b+c;
end;
</code>

<eval id="4bccb71f48edc">
begin
writeln(floattostr(addi33(3,4,5)));
end.
</eval>


<check>
result := (addi33 (3,4,5) = 12) and (addi33 (8,4,15) = 27);
</check>

=== Quadrat einer Zahl ===


<code id="4bc596ef0560c">
function quadrat (x : integer):integer;
var erg: integer ;
begin
erg := x*x;
result := erg;
end;
</code>

<eval id="4bc4611f3a5f1">
begin
writeln(inttostr(quadrat(2)));
end.
</eval>


=== Beispiel 3 ===

''Untersuche diese Funktion.''<br>
Gib Deine Lösung in der zweiten Zeile zwischen den Anführungszeichen '' an.<br>

<code id="4bc596ef065ab">
function was(x,y,z:integer):integer;
var erg: integer;
begin
y:=x ;
erg:=z;
x:=erg;
erg:=y;
result:=erg;
end;
</code>

<eval id="4bc596ef0a437">
begin
writeln(inttostr(was(2,4,6)));
writeln('');
end.
</eval>

=== Gute Wünsche für den Tag ===


''Ergänze die Anweisungen so, dass in der Ausgabe Wünsche für die Tage 1 bis 5 ausgegeben werden.''<br>
Worin unterscheidet sich der Quelltext von den obigen Beispielen?


<code id="4bc596ef0754b">
var i:integer;
begin
for i:= 1 ....
begin
 writeln('Alles Gute am Tag ....+'.');
  ....
end; 
end.
</code>

<eval id="4bc596ef0b3cb"></eval>

'''Grundlagen der Unterprogrammarbeit (Modularisierung)'''


== function ==

Beispiel für eine Funktion in einer imperativen Programmierumgebung

[[Bild:Function.JPG]]

Aufruf der Funktion im Hauptprogramm

[[Bild:Function_2.JPG]]



''hier ein Beispiel für die Syntax im WIKI''


<code id="4b96b9dd4d2d7">
function addi(a,b:integer):integer;
begin
result:=a+b;
end;
</code>

<eval id="4b96b9dd51145">
begin
writeln(inttostr(addi(3,4)));
end.
</eval>

Ergänze die ähnliche Funktion addi3 zur Bildung der Summe dreier reller Zahlen!

<code id="4b96b9dd4e268">
function addi3
</code>

<eval id="4b96b9dd520e6">
begin
writeln(floattostr(addi3(3,4,5)));
end.
</eval>

<check>
result := ((addi3(3,4,5) = 12) and (addi3(8,4,15) = 27));
</check>


== procedure ==

Beispiel für eine Prozedure in einer imperativen Programmierumgebung

[[Bild:Prozeduren.JPG]]

Aufruf der Prozedur im Hauptprogramm

[[Bild:Prozeduren_2.JPG]]


''hier ein Beispiel für die Syntax im WIKI''


<code id="4b96b9dd4f206">
procedure dreieck(a,b,c:real; var erg:string);
begin
if (a*a+b*b=c*c) then erg:='ja'
else erg:='nein';
end;
</code>

<eval id="4b96b9dd53085">
var erg: string;
begin
dreieck(4,3,5.2,erg);
writeln(erg);
end.
</eval>



Neujahrswünsche in Pascal:

<code id="4b96b9dd501a5">
var i:integer;
begin
for i:= 1 to 9 do
begin
 writeln('Alles Gute am Tag '+inttostr(i)+'.');
 i:=i+1;
end; 
end.
</code>

<eval id="4b96b9dd54025"></eval>

'''Die folgenden Übungsaufgaben dienen der Festigung des Umgangs mit den algorithmischen Grundstrukturen.'''



1. Entwickle einen Algorithmus für die Berechnung der Summe der ersten n natürlichen Zahlen.

Setze diesen in Pascal um.


<code id="4bcecd8d173af">
function summe_erste_n(
</code>

<eval id="4bcecd8d1833c">
begin
writeln(inttostr(summe_erste_n(5)));
end.
</eval>




2. Übertrage diesen Algorithmus auf die Berechnung einer Fakultät!


<code id="4bced86215c2c">
function fak_n(
</code>

<eval id="4bced86216bbc">
begin
writeln(inttostr(fak_n(5)));
end.
</eval>




3. Gegeben ist folgendes Struktogramm. Implementiere den damit dargestellten Algorithmus in der nachfolgenden Box als function ''xyz'' und <br>

teste ihn mit den Werten x = 5, y = 8 und z = 3.
Erläutere die Bedeutung der Variablen.<br>
]
[[Bild:Struktogramm(v2).JPG]]


<code id="4bd7d28b3879b">
function xyz(
</code>

<eval id="4bd7d28b3972d">
begin
writeln(inttostr(xyz(...)));
end.
</eval>


'''Eine Funktion gibt nur einen Wert (a oder b) zurück.'''<br><br>

Daher nun diesen Algorithmus als procedure schreiben.

<code id="4bd80bd03dbb3">
procedure xyz(
</code>

<eval id="4bd80bd03eb3a">
begin
writeln(...);
end.
</eval>


4. Abschließend soll ein Programm geschrieben werden, das entscheidet, ob eine quadratische Funktion keine, genau eine oder genau zwei Nullstellen besitzt. Die Werte dieser Nullstellen sind auszugeben.
<br>
''vorher Algorithmus formulieren und z.B. Struktogramm entwerfen!''


<code id="4bd8132f80684">

</code>

<eval id="4bd8132f813eb">
begin
writeln(...);
end.
</eval>

Bei einer Mathematikolympiade wurde folgende Aufgabe gestellt:

''20 m Stoff werden auf einen Stab von 5 cm Durchmesser aufgewickelt.''<br>
''Der Stoff ist 1 mm dick.''
''Wie dick wird die Rolle?''<br><br>
Eine Realisierung des Sachverhalts als Programm könnte folgendermaßen aussehen:

<code id="4bde843d4f91a">
function dick:real;
var d, l:real;
begin
l:=0;
d:=0.05;
repeat
      l:=l+pi*d;
      d:=d+0.002;
until l>=20;
result:=d
end;
</code>

<eval id="4bde843d508a4">
begin
writeln(floattostr(dick));
end.
</eval>


'''Modifizieren Sie den Quelltext.'''<br>
Verwenden Sie anstelle ''repeat-until'' eine Schleife mit vorangestellter Bedingung.

<code id="4bde84feb8f27">
function dick2:real;
var d, l:real;
begin
....
end;
</code>

<eval id="4bde84feb9e7b">
begin
writeln(floattostr(dick2));
end.
</eval>


<font color="darkgreen">Sie werden festgestellt haben, dass unsere Lösung für die Problemstellung keinem Algorithmus entspricht. Es wird lediglixch ein konkretes Problem durch Programmierung gelöst!</font>
<br>
<font color="darkgreen">'''Die Aufgabe wird im Folgenden also verallgemeinert. Der aufzustellende Algorithmus löst dann eine Klasse gleichartiger Probleme, wobei die Abarbeitung abhängig von den Eingaben eindeutig, endlich erfolgt und unter gleichen Bedingungen zum gleichen Ergebnis führt.'''</font>


'''''Stoff beliebiger Länge wird auf einen Stab mit beliebigem Durchmesser aufgewickelt.''<br>'''
'''''Der Stoff ist beliebig dick.'''''
'''''Wie dick wird die Rolle?''<br><br>'''


<code id="4bde8752380e9">
function dick3(...):real;

begin
....
end;
</code>

<eval id="4bde875239072">
begin
writeln(floattostr(dick3(...)));
end.
</eval>

== Zufallszahlen ==


=== Erzeugen von Zufallszahlen ===

''zunächst als function, die aufgerufen wird:''

<code id="4be10a7306816">
function zufall(a:integer):integer;
begin
result:=random(a);
end;
</code>



<eval id="4be10a1ebb218">
begin
writeln(inttostr(zufall(100)));
end.

</eval>


''andere, kürzere Variante:''

<eval id="4be1207f5f5c1">
begin
writeln(inttostr(random(100)));
end.
</eval>

'''''Ist diese Variante für Programme praktikabel?'''''



=== Würfeln ===


Simulieren Sie ein Würfelspiel mit einem idealen Würfel.
Für eine Anzahl <math>n</math> von Würfen soll die Anzahl der geworfenen Augenzahlen ausgegeben werden.

<code id="4bf2b9d35501b">

</code>


<eval id="4bf2b9d356f46">


</eval>

Formulieren Sie anhand der Simulation eine Aussage über große Zahlen und die Wahrscheinlichkeit. ("Gesetz der großen Zahlen")


<font color="darkgreen">'''''zum Weiterarbeiten:'''''</font> Zeigen Sie durch eine analoge Simulation, dass die Zufallsgröße "[[Augensumme beim Würfeln mit zwei idealen Würfeln]]" nicht gleichverteilt ist.
<br><br><br>


 procedure wuerfelsumme(n:integer;var z,d,v,f,s,si,a,ne,ze,e,zw:integer);
 var i,zz1,zz2,sum:integer;
 begin
 z:=0;d:=0;v:=0;f:=0;s:=0;si:=0;a:=0;ne:=0;ze:=0;e:=0;zw:=0;
 for i:=1 to n do 
 begin
 zz1:=random(6)+1;
 zz2:=random(6)+1;
 sum:=zz1+zz2;
 if sum=2 then z:=z+1;
 if sum=3 then d:=d+1;
 if sum=4 then v:=v+1;
 if sum=5 then f:=f+1;
 if sum=6 then s:=s+1;
 if sum=7 then si:=si+1;
 if sum=8 then a:=a+1;
 if sum=9 then ne:=ne+1;
 if sum=10 then ze:=ze+1;
 if sum=11 then e:=e+1;
 if sum=12 then zw:=zw+1;
 end;
 end;

== Der Datentyp Feld (Array) ==


Neben den einfachen Datentypen gibt es auch zusammengesetzte, z.B. Felder (auch Listen, Array). 
In einem Array werden Werte gleichen Datentyps gespeichert.

Die Deklaration eines Arrays erfolgt folgendermaßen:
 var xyz: ''array''[startindex .. endindex] ''of'' Datentyp;

startindex..endindex gibt den Bereich zwischen Startwert und Endwert angeben (Randwerte werden mit eingeschlossen).
Dies entspricht dem bereitgehaltenen Speicherplatz.
Über den Index (meist mit <math>i</math> bezeichnet) kann man auf die einzelnen Werte zugreifen.

 var beispiel: ''array''[0..20] ''of'' integer;

Ein Feld wird über den Index gefüllt, z.B. für <math>i=1</math> und <math>i=5</math> so:

 beispiel[1]:=3;
 beispiel[5]:=22;

Das Feld sei dann z.B. so gefüllt ist: [10,3,6,7,9,22,...].<br>
''Bestimmen Sie die Werte, die dann die Variablen <math>a</math> und <math>b</math> nach den folgenden Anweisungen liefern!''

 a:=beispiel[0];
 b:=beispiel[2];


'''weitere Hinweise z.B. unter [http://www.delphi-treff.de/object-pascal/komplexe-datentypen/]'''


== Beispiele zu Feldern ==


=== Zufallszahlen und Felder ===

<code id="4bf2b9d355fac">
function zufall2(a:integer):integer;
begin
result:=random(a);
end;
</code>

<eval id="4bf2b9d357ee5">
var z:array[0..10] of integer;
var i:integer;
begin
for i:=0 to 5 do
begin
z[i]:=zufall2(100);
writeln(inttostr(z[i]));
end;
end.

</eval>

<font color="darkgreen">'''''zum Weiterarbeiten:'''''</font> Füllen Sie ein [[Feld mit 5 zufälligen Zahlen]]. Bestimmen Sie die Position (Index) des Maximums. Lassen Sie sich zur Kontrolle die Zufallszahlen anzeigen.

 var feld:array[0..4]of integer;
 var i,max,index:integer;
 begin
 max:=0;index:=0;
 for i:=1 to 5 do feld[i-1]:=random(100);
 for i:=1 to 5 do 
 if feld[i-1]>max then begin 
                       max:=feld[i-1];
                       index:=i;
                       end;
 for i:=1 to 5 do writeln(inttostr(feld[i-1]));
 writeln('Maximum an Position '+inttostr(index));
 end.



=== Hofstadter-Funktion ===

Eine sehr interessante, aber äußerst undurchsichtige Folge natürlicher Zahlen wird durch die Hofstadter-Funktion beschrieben:

<math>h(n) = h(n - h(n - 1) ) + h(n - h(n - 2) )</math>   für   <math>n > 2</math>  mit   <math>h(1) = h(2) = 1</math>

''(aus: Douglas R. Hofstadter:"Gödel, Escher, Bach: an eternal golden braid" (1979) - ein Beispiel für eine chaotische Zahlenfolge, die aber doch gesetzmäßig erzeugt wird)
''


<eval id="4bf2f8b405adc">
var hf:array[0..50] of integer;
var j,k:integer;
begin
 k:=15;
 hf[1]:=1;
 hf[2]:=1;
 for j:=3 to k do hf[j]:=hf[j-hf[j-1]]+hf[j-hf[j-2]];
 for j:=1 to k do write(inttostr(hf[j])+' '); 
end.
</eval>


Variieren Sie die Werte für <math>k</math> sowie den endindex des Feldes.<br>
'''''Verdeutlichen Sie sich die Abarbeitung des Quell-Codes anhand eines Ablaufplanes!'''''