Rekursive Wurzelberechnung mit Intervallhalbierung

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Dagon
User
Beiträge: 6
Registriert: Donnerstag 9. Februar 2006, 22:03

Rekursive Wurzelberechnung mit Intervallhalbierung

Beitragvon Dagon » Sonntag 26. März 2006, 21:28

Hi Leute,
Ich habe folgendes Problem:
Ich will eine Funktion schreiben, die die Wurzel eines gegebenen Radikanten durch rekursive Intervallhalbierung berechnet. Dafür hab ich bisher folgendes:

Code: Alles auswählen

def Intervall(radikant,unten,oben):
    mitte=(unten+oben)/2.0
    print mitte
    if mitte**2 < radikant:             
       unten=Intervall(radikant,mitte,oben)
    else:
       oben=Intervall(radikant,unten,mitte)


Das Problem ist, dass ich keine vernünftige Abbruchbedingung zu Stande bekomme. Es wird zwar eine immer bessere Annäherung ausgegeben (später sogar der genaue Wert) aber irgendwann wiederholt sich das Ergebnis nurnoch bis ein Fehler kommt.
Kann mir da jemand weiterhelfen?
helmut
User
Beiträge: 57
Registriert: Mittwoch 2. November 2005, 07:45
Wohnort: Dormagen

Beitragvon helmut » Sonntag 26. März 2006, 22:36

Hallo Dagon,
nachfolgend 2 Loesungen, einmal iterativ und einmal rekursiv.

Code: Alles auswählen

from math import fabs

def iter_sqrt(q_zahl,curval):
   while fabs(q_zahl/curval-curval)>.0001:
      curval = (q_zahl/curval+curval)/2.
   return curval

def rec_sqrt(q_zahl,curval):
   if fabs(q_zahl/curval-curval)<.0001:
      res = curval
   else:
      res = rec_sqrt(q_zahl,(q_zahl/curval+curval)/2.)
   return res

print iter_sqrt(900,10)                      #30.000000014
print rec_sqrt(900, 10)                     #30.000000014

Gruss, Helmut
Dagon
User
Beiträge: 6
Registriert: Donnerstag 9. Februar 2006, 22:03

Beitragvon Dagon » Montag 27. März 2006, 13:09

Danke auf jeden Fall für die Antwort, nur ist sie nicht ganz das, was ich gesucht habe. Gibt es keine Möglichkeit meiner Funktion noch eine Abbruchbedingung hinzuzufügen, dass sie einfach ab einer bestimmter Schrittzahl/Genauigkeit aufhört? Denn es werden ja die richtigen Näherungswerte ausgegeben, nur halt endlos.
Benutzeravatar
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Beitragvon Joghurt » Montag 27. März 2006, 13:24

Wie wäre es mit

Code: Alles auswählen

if abs(oben-unten)<1e-5


Diese Funktion solltest du aber nicht rekursiv schreiben, da du das jeweilige Ergebnis des rekursiven Aufrufs eh nicht benötigst. (Und du früher oder später einen Stack-overflow produzierst, wenn du zuviele Schritte brauchst)

Warum nicht einfach iterativ (was du praktisch ja eh schon machst)

Code: Alles auswählen

def Intervall(radikant, unten, oben):
  mitte = (unten+oben)/2.0
  while abs(unten-oben)>1e-5:
      mitte = (unten+oben)/2.
      if mitte*mitte < radikant:
        unten = mitte
      else:
        oben = mitte
  return mitte

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]