PÜ 8: Einführung zyklischer Strukturen
- Quadratwurzel nach Heron -

Vorbemerkungen:

Dem Pascal-Programmierer mag es nicht schwer fallen, die Arbeit mit zyklischen Strukturen zu motivieren: man schreibe ein überschaubares lineares Programm und stelle dann die Frage, wie dem armen Nutzer zu helfen sei, der mit diesem Programm Hunderte von Berechnungen durchführen soll.
Die Lösung liegt schnell auf der Hand: man packe das ganze in eine Repeat-Schleife an deren Ende eine Nutzerauswahl "Neue Berechnung?" / "Ende?" erfolgt und entbinde damit den potentiellen Nutzer von der lästigen Aufgabe, für jede neue Berechnung auch einen neuen Programmstart veranlassen zu müssen.

Unter Delphi greift diese Motivierung natürlich nicht, denn bis zum ultimativen "Form1.Close", verbunden mit einem "Ende"-Button, kann ein Nutzer die Funktionalität des Programm-Fensters so oft strapazieren, wie er möchte, da dank der Ereignisorientierung ohnehin ein zyklisches Abfragen eingabesensitiver Komponenten erfolgt.
Bewährt hat sich m. E. der Einstieg über einen einfachen zyklischen Algorithmus, etwa der Iteration einer Quadratwurzel nach Heron. Hieraus werden für das Verständnis von Schleifen notwendige Erkenntnisse, wie z. B. die Bedeutung der Abbruchbedingung abgeleitet und dann auf weitere Beispiele angewandt.

Nichtabweisender Zyklus / Abweisender Zyklus / Zählzyklus?
Immer häufiger hört man die Frage "Müssen die Schüler denn wirklich (noch) alle drei Schleifenarten beherrschen?" Mein Standpunkt: wenn die Zeit dazu vorhanden ist, so hat 's noch keinem geschadet. Jedoch fehlt es meist an eben dieser Zeit. Nach dem Motto "Weniger ist meistens mehr" würde ich es für sinnvoller halten, wenn der Schüler im Extremfall mit nur einer einzigen Schleifenart eine Vielzahl von Problemen aufbereiten und lösen kann, als dass er zwar alle Schleifenarten formal kennt, jedoch kaum in der Lage ist, diese selbständig zur Problemlösung zu verwenden.

Die Kunst des Weglassens sollte unbedingt die Überlegung einschließen, dass "Repeat-" und "While-Schleifen" (also Nichtabweisende und Abweisende Zyklen) gegenüber dem Zählzyklus die universelleren Werkzeuge darstellen, d. h. alle auf iterativem Wege lösbaren Probleme lassen sich damit umsetzen, während mit der Zählschleife nur eine Teilmenge dieser Lösungen (sauber) programmiert werden kann. 
In meinen Kursen empfand ich es bisher als gangbaren Kompromiss, das Wesen zyklischer Algorithmen zunächst anhand der Repeat-Schleife zu verdeutlichen und nachfolgend "so zu tun", als gäbe es nur diese eine Schleifenart. Mit dieser Strukturkenntnis werden alsdann bei zunehmender Selbständigkeit einfache Problemstellungen aus verschiedenen Gebieten bearbeitet und erst am Ende werden eher überblicksartig die beiden verbleibenden Schleifenarten vorgestellt und Vergleiche dazu angestellt.

Der Iterationsbegriff:

Einführung des Nichtabweisenden Zyklus - Quadratwurzel nach Heron -

Szenario:

Interessant ist es Schüler der heutigen Generation mit der Frage zu konfrontieren, wie denn wohl unsere Vorfahren ohne Hilfsmittel die Quadratwurzel einer natürlichen Zahl "gezogen" haben. Der Gedanke, dass dies durch Näherungsverfahren geschehen sein muss, ist schnell geäußert; die Frage aber, wie man denn mit vertretbarem Aufwand eine möglichst hohe Genauigkeit erreichen konnte, bleibt meist unbeantwortet.
Ein knapp 2000 Jahre altes Verfahren, entwickelt durch HERON von Alexandria (ca. 20-62 n. Chr.), löst das Problem auf geniale und aus heutiger Sicht sehr computerfreundliche Weise!

Der Heronsche Algorithmus - an einem Zahlenbeispiel vorgestellt:

Ausgangspunkt:	1. Iterationsschritt:	... nach unendlich vielen Iterationsschritten:
	b' = (a+b)/2 a' = A / b'

Umsetzung des Heronschen Algorithmus mit einer Nichtabweisenden Schleife:

Struktogramm:	Quelltext:
	... a:=1; b:=zahl; repeat   b:=(a+b)/2;   a:=zahl/b; until b-a < fehler; ...

Die Variable fehler legt in der Abbruchbedingung die erlaubte Abweichung zwischen b und a fest. Wird fehler z. B. im Rahmen der Eingabe mit 0.0004 belegt, so bewirkt dies eine Genauigkeit des Ergebnisses auf 3 Nachkommastellen.
Der Rechner prüft nach jedem Schleifendurchlauf, ob die sog. Abbruchbedingung erfüllt ist (hier: b-a < fehler). Ist diese erfüllt, wird die Schleife verlassen und mit derjenigen Anweisung fortgesetzt, die der Abbruchbedingung folgt. Bei Nichterfüllung der Abbruchbedingung wird der sog. Schleifenkörper erneut durchlaufen.
Wichtig ist es daher, dass über die der Schleife vorangehenden Anweisungen in Verbindung mit dem Schleifenkörper selbst eine Struktur vorliegt, die nach endlich vielen Durchläufen die Abbruchbedingung auch wirklich erreicht.
Andernfalls hätte man eine "Endlosschleife" programmiert, die im schlimmsten Fall einen kompletten Rechnerabsturz zur Folge haben könnte.
Spätestens dann stellt man sich die bange Frage: "Wann habe ich mein Programm eigentlich das letzte Mal gesichert?" ;-)

Programmierung der Quadratwurzel nach Heron

a) Grundvariante

Oberflächengestaltung:	Quelltext:
	procedure TForm1.Button1Click(Sender: TObject);   var zahl: integer;       a,b,fehler:real;   begin     zahl := strtoint(edit1.text);     fehler := strtofloat(edit2.text);     a:=1; b:=zahl;     repeat       b:=(a+b)/2;       a:=zahl/b     until b-a < fehler;     edit3.text := floattostr(b);   end;

b) Erweiterte Variante

• der Heronsche Algorithmus ist nur für natürliche Zahlen x>=1 definiert, das Eingabe-Textfeld erlaubt jedoch auch Einträge von Werten x<=0 (Absturzgefahr / falsches Ergebnis);
  Lösungshinweis: Eingabesicherung
    
• im mathematischen Sinne ganzzahlige Ergebnisse sind aufgrund ihrer iterativen Erzeugung mit "fehlerhaften" Nachkommastellen belastet;
  Lösungshinweis: Formatierung mittels FloatToStrF
    
• es ist nicht abzusehen, wie viele Schleifendurchläufe zum Erreichen der geforderten Genauigkeit notwendig waren;
  Lösungshinweis: Zählfunktion in Schleifen
    
• dem Nutzer müsste erklärt werden, was mit max. Fehler gemeint ist und welche Werte hier als Eingabe sinnvoll sind.
  Lösungshinweis: Eingabefunktion mittels TScrollBar

Aufgabe:

Das Programm ist so zu erweitern, dass möglichst viele der oben aufgeführten Kritikpunkte überwunden werden.

Zur Orientierung kann die nebenstehende Abbildung verwendet bzw. das Programm heron2.exe downgeladen werden.

Bemerkenswert ist die geringe Anzahl an Iterationen, die zum Erreichen hoher Genauigkeiten erforderlich ist. Immerhin ist nach 7 Schritten die Wurzel der Zahl 78 auf 6 Nachkommastellen genau bestimmt!

Anmerkungen:

Um alle Näherungswerte (im Bsp. der Verlauf von b) anzeigen zu können, empfiehlt sich die Verwendung einer ListBox-Komponenten. Natürlich muss die "Bestückung" der ListBox (ListBox1.Items.Add(FloatToStr(b));) innerhalb der Schleife erfolgen.

Lösungshinweise:

Eingabesicherung

Das Prinzip ist schnell erklärt: der Nutzer ist so oft zur Wiederholung seiner Eingabe aufzufordern, bis sein Eingabewert im erlaubten Bereich liegt!

Beispiel: Es dürfen über Edit1 nur ganzzahlige Werte 10 <= x <= 20 eingelesen werden.

Über ein Dialogfenster soll der Nutzer über seinen Fehler informiert werden; anschließend ist das entsprechende Edit-Feld zu löschen und der Cursor zwecks Neueingabe wieder in diesem zu positionieren. In der zugehörigen Ereignisbehandlungsroutine, meist  Procedure Button*Click(...); wären an den Anfang folgende Anweisungen einzuarbeiten:

  x := StrToInt (Edit1.Text);
  if (x < 10) OR (x>20) then begin
    ShowMessage ('Wert muss zwischen 10 und 20 liegen!');
    Edit1.Clear;
    ActiveControl := Edit1;
  end
  else begin
    {Jetzt folgen die Anweisungen zur Verarbeitung von x}
    {...........}
  end;

Da die Verarbeitung des x-Wertes im Else-Zweig erfolgt, kommt diese erst nach korrekter Eingabe zustande.

Formatierung mittels FloatToStrF

Während der Programmierer bei der Verwendung der Funktion "FloatToStr" keinen Einfluss auf das Erscheinungsbild der String-Ausgabe des Real-Wertes hat, eröffnen sich durch "FloatToStrF" vielfältige Formatierungsmöglichkeiten. So lässt sich Beispielsweise die Anzahl der angezeigten Nachkommastellen in Abhängigkeit der iterierten Genauigkeit einstellen. Näheres zur Verwendung von "FloatToStrF" ist der Delphi-Hilfe zu entnehmen.

Zählfunktion in Schleifen

So wie Kinder mit den Fingern zählen, kann man's auch den Schleifen "beibringen". Man führe einfach eine ganzzahlige Zählvariable ein, setze deren Wert vor der Schleife auf Null und erhöhe diesen bei jedem Schleifendurchlauf um den Wert 1. Am Ende gibt die Zählvariable Auskunft darüber, wie oft die Schleife durchlaufen wurde.

Eingabefunktion mittels TScrollBar

Zur Einstellung der Nachkommastellen und damit des zulässigen Fehlers wurde hier eine Komponente TScrollBar verwendet, deren aktueller Wert in dem darüber liegenden Textfeld (TEdit) zur Anzeige gelangt. Um die bei Realtypen verwalteten Nachkommastellen nicht überzustrapazieren, wären über den Objektinspektor für ScrollBar1 die Eigenschaften Min=1 und Max=10 zu setzen. Die Eigenschaft ScrollBar1.Position gibt den vom Nutzer eingestellten ganzzahligen Wert (zwischen Min und Max) zurück.
Zu beachten ist auch der Zusammenhang zwischen eingestellten Nachkommastellen und dem sich daraus ergebenden zulässigen Fehler. In der Abb. bedeuten z.B. 6 Nachkommastellen einen Fehler von 0.0000004.

c) Zusatzaufgabe

1. Transformieren Sie mit einem einfachen Zahlenbeispiel die oben gezeigten Lösungsskizzen auf das Problem der Kubikwurzel und entwickeln Sie die entsprechenden Gleichungen bzw. Wertzuweisungen für die Iteration der Ergebnisses!
     
2. Verallgemeinern Sie die Lösungsidee zu einem Algorithmus in Struktogrammform.
     
3. Erstellen Sie ein nutzerfreundliches Delphi-Programm zur iterativen Berechnung der 3. Wurzel einer natürlichen Zahl.

Diplomarbeiten zum Runterladen: