rekursive Funktion stoppen
-
Hallo zusammen!
Ich soll ein Programm schreiben, das mithilfe der Bisektionsmethode die Nullstelle einer streng monoton steigenden Funktion wie folgt berechnet:
1. Setzel=a und r=b.
2. Teste, ob [l, r] eine Nullstelle entha ̈lt. Wenn nicht: Abbruch.
3. Teste, ob r − l < ε ist. Wenn ja, dann ist das Lo ̈sungsintervall gefunden.
4. Sonst teile [l, r] in der Mitte und setze das Verfahren mit beiden Teilintervallen rekursiv bei (2) fort.
Das soll mit folgender signatur geschehen:
void bisection(std::vector <double >& interval , double eps);Mein Versuch sieht nun so aus:
void Tbisection(std::vector <double >& interval, double eps) {
double l;
double r;
l = interval[0];
r = interval[1];
cout << "l = " << l << endl;
cout << "r = " << r << endl;
//cout << "f(l) = " << f(l) << endl;
//cout << "f(r) = " << f(r) << endl;
if (f(l) < 0 && f(r) > 0) {
if (r - l < eps) {
interval[0] = l;
interval[1] = r;
cout << "Die Nullstelle liegt im Interval: [" << interval[0] << "," << interval[1] << "]" << endl;
return;
}
else {
double a = (r - l)/2;
vector<double> inta(2);
inta[0] = l + a;
inta[1] = r;
Tbisection(inta, eps);
vector<double> intb(2);
intb[0] = l;
intb[1] = r - a;
Tbisection(intb, eps);
}
}
else {
cout << "Das Interval enthält keine Nullstellen.";
}
}Mein Problem ist nun, dass die Funktion das Interval zwar findet, jedoch die Berechnung nicht stoppt sondern die Rekursion weiterführt.
Vielleicht kann mir jemand weiterhelfen..
-
Was soll der vector?
Zeig mal ein komplettes Minimalbeispiel. Siehe dritten Link in meiner Signatur. Der Code sieht zwar äußerst ungeschickt, aber nicht direkt falsch aus. A propos Aussehen: Benutz bitte unbedingt die Formatierungstags, wenn du hier Code postest (unter den Smileys). Es kann gut sein, dass ich gerade einen ganz einfachen Fehler übersehen habe, da der Code vollkommen unformatiert ist.
-
Ich sehe gerade keinen Fehler aber der Code ist doch ziemlich umstaendlich. Hier eine Idee wie man das etwas eleganter implementieren kann:
void Tbisection(double left, double right, double eps) { if ( f(left) < 0 && f(right) > 0 ) { if ( right - left < eps ) { // Intervall ausgeben } else { double middle = (left + right) / 2; Tbisection(left, middle, eps); Tbisection(middle, right, eps); } } else { cout << "Das Intervall enthaelt keine Nullstelle."; } }(Ungetestet und nur kurz so hingeschrieben).
-
Es wäre natürlich noch hübsch, die Funktion f nicht fest ein zu programmieren.
void bisection(double left, double right, double eps, double (&f)(double))bietet sich als Signatur an. Kann man natürlich nochmal verallgemeinern mittels Templates. Aber die Funktion f flexibel zu machen ist erst einmal das wichtigste.
-
Ich hab mal den Code von icarus2 auf die eigentliche Frage angepasst.
// true zurückgeben, wenn Nullstelle gefunden bool Tbisection(double left, double right, double eps) { if ( f(left) < 0 && f(right) > 0 ) { if ( right - left < eps ) { // Intervall ausgeben return true; // gefunden } else { double middle = (left + right) / 2; if (Tbisection(left, middle, eps)) return true; // wurde schon gefunden, kann abbrechen if (Tbisection(middle, right, eps)) return true; // wurde schon gefunden, kann abbrechen } } else { cout << "Das Intervall enthaelt keine Nullstelle."; } return false; // schade, (noch) nichts gefunden. }
-
ahnfgydt schrieb:
Ich hab mal den Code von icarus2 auf die eigentliche Frage angepasst.
Er will nicht wissen, ob es in einem Intervall eine Nullstelle gibt, sondern alle Nullstellen im Intervall berechnen.
Fuer die Frage der Existenz einer Nullstelle in einem Intervall fuer stetige monoton wachsende Funktionen das Bisektionsverfahren anzuwenden ist onehin komplett sinnfrei.
-
chiral schrieb:
Hallo zusammen!
Ich soll ein Programm schreiben, das mithilfe der Bisektionsmethode die Nullstelle einer streng monoton steigenden Funktion wie folgt berechnet:
1. Setzel=a und r=b.
2. Teste, ob [l, r] eine Nullstelle entha ̈lt. Wenn nicht: Abbruch.
3. Teste, ob r − l < ε ist. Wenn ja, dann ist das Lo ̈sungsintervall gefunden.
4. Sonst teile [l, r] in der Mitte und setze das Verfahren mit beiden Teilintervallen rekursiv bei (2) fort.
Das soll mit folgender signatur geschehen:
void bisection(std::vector <double >& interval , double eps);Keine Chance, sinnvollen Code zu schreiben, wenn Du Dich an diese Beschreibung und Signatur halten sollst.
#include <iostream> #include <vector> #include <iomanip> using namespace std; double f(double x){ return x*x-2; } //Erster Versuch void bisection1(vector<double>& interval,double eps){//seltsame schnittstelle if(interval[1]-interval[0]<eps) return; double m=(interval[0]+interval[1])/2; if(f(m)>0) interval[1]=m; else interval[0]=m; bisection1(interval,eps); } //Leider ist hier die Rekursaion völlig sinnfrei, das ist eine recht einfache Schleife //Mal sich an den Text halten. //Zweiter Versuch void bisection2(vector<double>& interval,double eps){//seltsame schnittstelle //1. Setze l=a und r=b. //recht sinnfrei double l=interval[0]; double r=interval[1]; //2. Teste, ob [l, r] eine Nullstelle entha ̈lt. Wenn nicht: Abbruch. //autsch, das soll die Entscheidung beim Aufruf ersetzen. //mangels rückgabe, wird das aua machen. if(not(f(l)<=0 and f(r)>=0)) return; //3. Teste, ob r − l < ε ist. Wenn ja, dann ist das Lo ̈sungsintervall gefunden. if(r-l<eps) return; //4. Sonst teile [l, r] in der Mitte und setze das Verfahren mit beiden Teilintervallen //rekursiv bei (2) fort. else{ double m=(l+r)/2; interval[0]=l; interval[1]=m; bisection2(interval,eps); interval[0]=m; interval[1]=r; bisection2(interval,eps); //und nu, welcher Aufruf war der bessere? } } //Nee, so nicht. So ergibt das gar keinen Sinn. //Dritter Versuch void bisection3(vector<double>& interval,double eps){ //1. Setzel=a und r=b. //ok, die Schleife muss der schrägen Schnittstelle nicjht folgen. l1: double l=interval[0]; double r=interval[1]; //2. Teste, ob [l, r] eine Nullstelle entha ̈lt. Wenn nicht: Abbruch. //ok, vorher mal testen, sonst suchen wir uns blöd. l2: if(not(f(l)<=0 and f(r)>=0)) return; //3. Teste, ob r − l < ε ist. Wenn ja, dann ist das Lo ̈sungsintervall gefunden. l3: if(r-l<eps){ interval[0]=l; interval[1]=r; return; } l4: //4. Sonst teile [l, r] in der Mitte double m=(l+r)/2; //und setze das Verfahren mit beiden Teilintervallen //nee, nur mit dem besseren if(f(m)>0) r=m; else l=m; //rekursiv bei (2) fort. //nee, nicht rekursiv. Und nicht bei (2), weil bei (3) ausreicht. goto l3; } int main(){ vector<double> interval; interval.push_back(0); interval.push_back(10); bisection3(interval,0.000001); cout<<setprecision(10)<<interval[0]<<" <= wurzel(2) <= "<<interval[1]<<'\n'; }
-
Vielen vielen Dank für eure Antworten!! Ihr habt mir sehr geholfen!!
