Algorithmen mit Wiederholungen

Wiederholungsstruktur mit Endbedingung

Einführungsbeispiel

DAS HERON-Verfahren

Nach Heron von Alexandria  wird ein Verfahren zur Approximation von Quadratwurzeln zugeschrieben.

x_n+1 = 1/2 (x_n + a/ x_n)

a ... Radikant; x₁... Startwert

Beispiel, um es besser zu verstehen  

Gesucht ist die Wurzel aus 20 (20 =  5 · 4), also Startwert a = 20

	Annäherung   b	a / b	Mittelwert als Bruch	Näherungswert (auf 4 Dezimalen)
1.	5	20 / 5 = 4	9/2 (= 4,5)	4,5000
2.	9 / 2	20 / (9 / 2)) = 40/9	(9 / 2  +  40 / 9) / 2  =  171 / 36	4,7500
3.	171/36	20 / (171/36) = 720 / 171	(171² + 36 · 720) / (36 · 171 · 2)	4,4803
4.	(171² + 36 · 720) / (36 · 171 · 2)	20 / (171² + 36 · 720) / (36 · 171 · 2)		4,4721

 Zusammenfassend: Mit dem Heronverfahren lassen sich Wurzeln näherungsweise bestimmen.

 Algorithmus

 Struktogramm

Syntax

Die Wiederholungsanweisung mit Endbedingung ermöglicht es,  Anweisungen mehrfach auszufahren und zwar solange bis die Schleifenbedingung am Ende erfüllt ist.

REPEAT <Anweisung> UNTIL <Bedingung>

Quelltext

Program Heron_Verfahren;

uses crt; 

var 	a, x, y, xneu, yneu, epsilon: real; 

	k: integer; 

begin {+++ Heron +++} 

	clrscr;

	writeln; 

	writeln('          Das Heron-Verfahren '); 

	writeln('    zur Bestimmung der Quadratwurzel'); 

	writeln; 

	write('   Es soll die Wurzel aus a = '); read(a); writeln('   bestimmt werden'); {+++ Eingabe +++}

	write('   Toleranz: epsilon = '); readln(epsilon);

	k := 0; x := a; y := 1; 

		while abs(x*x - a) > epsilon do 

			begin 

				writeln(k : 4, x : 13 : 8, y : 12 : 8); 

				{+++ formatierte Ausgabe +++}

				k := k+1; xneu := (x + y) / 2; 

				yneu := a / xneu; x := xneu; y := yneu; 

			end;

		writeln(k : 4, x : 13 : 8, y : 12 : 8);

		writeln('Wurzel(a) = ', x : 12 : 8); 27: 

end.{+++ Heron +++}