Quadratwurzel mithilfe Intervallhalbierung in C?

Hi, also ich soll ein C-Programm schreiben, dass die ganzahlige Quadratwurzel einer Zahl berechnen soll mithilfe Intervallhalbierung:

für zb 9:

1.Durchgang:

9 + 0/2 = 4 -> 4*4 = 16 > 9

2.Durchgang:

4 + 0/ 2 = 4-> 2*2 = 4 < 9

3.Durchgang:

2 + 4 / 2 = 3 -> 3*3 = 9 = 9 (passt)

Ich versteh nicht so ganz was ich als Schleifenbedingung nehmen muss.

Answer 1

[regex9]

Das Halbierungsverfahren setzt ja darauf auf, dass du zwei Grenzen definierst, die sich Schritt für Schritt annähern, indem man den Durchschnitt ermittelt.

$a^{2\ }<\ r\ \ <\ b^2$

Dabei handelt es sich jedoch um ein Annäherungsverfahren. Deine Rechnung ist ja ziemlich vereinfacht, da sie nur mit ganzen Zahlen arbeitet (hierzu noch ein Kommentar am Rande: Es gilt Punkt- vor Strichrechnung. Bei dir fehlen Klammern für die Addition der Grenzen). Würdest du mit Dezimalzahlen arbeiten, sollte die Anzahl an Nachkommastellen zunehmend (und endlos) steigen. Um ein Ende für die Rechnung zu finden, definiert man daher üblicherweise noch eine Genauigkeit k.

So lange die Differenz zwischen beiden Grenzen größer als die definierte Genauigkeit ist, sollte demzufolge eine weitere Annäherung stattfinden.

so lange obere Grenze - untere Grenze >= k:
  berechne mittelwert [obere Grenze; untere Grenze]
  wenn mittelwert * mittelwert > r
    nutze mittelwert als obere Grenze
  sonst
    nutze mittelwert als untere Grenze

Bei einer Genauigkeit von 0.1 würde man demzufolge auf 3.0234375 als Ergebnis kommen. Umso weiter man den Wert senkt, umso genauer wird das Ergebnis, aber umso länger dauert auch die Berechnung.

Wenn mit ganzen Zahlen gerechnet werden soll, müsste die Genauigkeit höher gesetzt werden. Es wäre an der Stelle zudem noch sinnvoll, die Verzweigung innerhalb der Schleife zu erweitern, sodass die Schleife abbricht, sobald der quadierte Mittelwert dem Wert von r entspricht.