 |
|||
| HSG |
|
Das Sieb des Eratosthenes
Im Mathematik-Lehrbuch der 6.Klasse (Lambacher-Schweizer 6, Klett-Verlag, 73102) findet man folgende Beschreibung:
- Schreibe die Zahlen von 2 bis z.B. 100 auf.
- Die erste Zahl ist 2. Streiche alle Vielfachen von 2, außer 2 selbst.
- Suche die nächste nicht gestrichene Zahl; streiche alle Vielfachen von ihr, außer der Zahl selbst.
- Wiederhole 3., so lange man auf diese Art noch Vielfache streichen kann.
Alle übrig gebliebenen Zahlen sind die Primzahlen. Bei den Zahlen bis 100 kann man schon nach dem Streichen aller Vielfachen von 7 aufhören.
Aufgabe
Schreibe ein Delphi-Programm, das nach obigem Algorithmus Primzahlen sucht.
mögliche Schritte hin zur Lösung
- Der Algorithmus wird mit kleinen Zahlen (vielleicht bis 20) mit Papier und Bleistift durchgeführt. Auf diese Weise testet man, ob er hinreichend verstanden ist.
- Es wird überlegt, wie man die 'Wirklichkeit' in den Computer abbilden kann. Hier z.B.: Wie schreibt man die Zahlen 2 bis 100 auf?
- zahl : array[2..100] of integer; scheint eine passende Datenstruktur zu sein.
- Das Aufschreiben könnte mit for i := 2 to 100 do zahl[i] := i; erledigt werden.
- Wie könnte man das Streichen der Zahl 12 realisieren? Z.B. mit zahl[12] := 0;
- Beim Streichen der Vielfachen weiß man nicht vorher, wie oft man streichen muss. Ein typischer Fall für
eine while-Schleife. Hier muss man sich Gedanken über die Abbruchbedingung machen.
// es werden die Vielfachen von a getrichen v := 2; // v gibt die 'Vielfachheit' an while v*a <= 100 do begin zahl[v*a] := 0; v := v+1; end;
- Wie findet man die nächste nicht gestrichene Zahl? Es fällt auf, dass man sich irgendwie merken muss, welches
die letzte gefundene Zahl ist. Da diese Zahl eine Primzahl ist, scheint p : integer; eine passende Vereinbarung
zu sein. Wir führen einen Zeiger, einen Index i : integer ein und setzen den Zeiger auf p+1 (i := p+1;).
Dann rücken wir den Zeiger so oft weiter, bis wir eine nicht gestrichene Zahl gefunden haben.
i := p+1; while zahl[i] = 0 do i := i + 1;
Was ist aber, wenn schon alle Zahlen gestrichen sind? Dann läuft der Zeiger über die vereinbarte Feldgrenze hinweg.
i := p+1; while (i<=100) and (zahl[i] = 0) do i := i + 1;
Obige Lösung führt zu einem Abbruch, wenn i > 100 geworden ist. Dann sollte man aber nicht zahl[i] auswerten, da diese Stelle nicht mehr im Array, im Feld ist. In Delphi werden je nach Einstellung logische Ausdrücke von links nach rechts ausgewertet und die Auswertung abgebrochen, wenn das Ergebnis schon feststeht (Kurzschlussverfahren). -
Man wird versuchen, obige Teilüberlegungen zusammenzufassen, etwa:
for i := 2 to 100 do zahl[i] := i; p := 2; while p <= 100 do begin // es werden die Vielfachen von p getrichen v := 2; // v gibt die 'Vielfachheit' an while v*p <= 100 do begin zahl[v*p] := 0; v := v+1; end; // es wird die nächste nicht gestrichene Zahl gesucht i := p+1; while (i<=100) and (zahl[i] = 0) do i := i + 1; // die gefundene Zahl ist eine Primzahl oder zu groß p := i; end; - Es ist sinnvoll, den Algorithmus formal in der vertrauten Programmiersprache zu beschreiben, da so natürlich schnell erste Tests möglich sind.
- Oft wird man eine Memo-Komponente (z.B. mAusgabe) als 'Ausgabe-Bildschirm' gebrauchen und Zeilen mit mAusgabe.Lines.Add(...) ausgeben.
- Bis zu einer lauffähigen ersten Lösung sind vermutlich fehlende Vereinbarungen zu ergänzen und einige Syntax-Fehler zu beseitigen.
- Läuft das Programm. so wird man ausgiebige Tests machen. In unserem Fall, kannman sich die Primzahlen bis 100 auch anders beschaffen und mit der Programm-Ausgabe vergleichen.
Erste vorläufige Lösung
Kritik der Lösung
Es ist typisch, dass man bei der ersten Lösung in Teillösungen gedacht hat und nicht mehr einen klaren Blick für das Ganze hat. Hier sollte man kritisch über die Lösung sehen. Sind die Variablen sinnvoll benannt? Sind die Datentypen sinnvoll gewählt? Braucht man überhaupt alle Variablen oder sind Reste früherer Versuche im Programm-Code enthalten? Wurden Programmiersprachen-abhängige Besonderheiten benutzt?
Folgende Version ist an einigen Stellen verändert. Was bewirken die Änderungen? Ist das Programm 'besser'?
procedure TForm1.bRechneClick(Sender: TObject); const n = 200; var zahl : array[2..n] of boolean; p,i,v : integer; weiter : boolean; begin // Eingabe // Verarbeitung for i := 2 to n do zahl[i] := true; p := 2; while p <= n do begin // es werden die Vielfachen von p getrichen v := 2*p; // v ist das 'Vielfache' while v <= n do begin zahl[v] := false; v := v+p; end; // es wird die nächste nicht gestrichene Zahl gesucht p := p+1; if p <= n then weiter := true; // 'weiter' ist ein logischer Schalter while weiter do if (p<=n) and (zahl[p] = false) then p := p+1 else weiter := false; end;
Es folgt eine dritte Version:
for i := 2 to n do zahl[i] := true;
for i := 2 to n do
if zahl[i] = true
then
begin
// es werden die Vielfachen von zahl[i] getrichen
v := 2*i;
while v <= n do
begin
zahl[v] := false;
v := v+i;
end;
end;
Diese Version entspricht nicht mehr 1:1 der Beschreibung aus dem Mathematikbuch. Wie müsste hier die Beschreibung lauten?