4. [C] iterative Funktion in rekursive umschreiben

[C] iterative Funktion in rekursive umschreiben

  • R

    Hallo Leute,

    bin neu hier. Hab mich angemeldet, weil ich gerade angefangen habe Informatik zu studieren und ich wohl öfter nochd den einen oder anderen Ratschlag brauchen werde... und vielleicht auch irgendwann mal geben kann 😉

    also mein Problem ist folgendes:
    Wir haben die Aufgabe bekommen, eine kleine Funktion in C zu implementieren, die mittels Intervall-Schachtelung die Wurzel einer ganzen positiven Zahl berechnet. Dies soll in 4 Versionen geschehen: eine rekursiv deterministisch, eine rekursiv nichtdeterministisch, eine iterativ deterministisch und eine iterativ nichtdeterministisch.

    Die iterativ deterministische ist kein Problem, allerdings hab ich nich die geringste vorstellung, wie ich die Funktion nichtdeterministisch und vor allem rekursiv darstellenn soll. Mein bisheriger Code sieht so aus:

    double wurzel(int a) {
	double li = 1.0, re = a, y;
	while(li<re) {
		y = (li+re)/2;
		if(y*y<a) {li=li+0.0001;}
		if(y*y>a) {re=re-0.0001;}
	}
	return y;
}

    Ich würde mich freuen, wenn mir jemand helfen könnte!
    Liebe Grüße
    Randy 🙂

    0
  • R

    Okay ne, der Code von vorhin war viel zu ineffizient.... so ist es besser:

    double wurzel(int a) {
	double li, re = a, y;
	while(li<re-0.000001) {
		y = (li+re)/2;
		if(y*y<a) {li=y;}
		if(y*y>a) {re=y;}
	}
	return y;
}

    meine frage ist aber immernoch die gleiche 😉

    grüße
    Randy

    0
  • D

    Bei rekursiven Funktionen ist die Schleife im Prinzip die ganze Funktion, d.h. z.b. kannst du deine Schleife momentan so schreiben:

    // Berechne Wurzel von a anhand von li und re
    while(1) {
        if (li<re-0.000001) {
          break;
        }
        y = (li+re)/2;
        if(y*y<a) {
              // Berechne Wurzel von a anhand von y und re
           li=y;
     //Durchlaufe GENAU den gleichen Code wieder (nur mit anderen Werten für li)
           continue;
       }
        if(y*y>a) {
         // Berechne Wurzel von a anhand von li und y
           re=y;
           //Durchlaufe GENAU den gleichen Code wieder (nur mit anderen Werten für re)
           continue;
       }
    }

    Und das machst du jetzt nicht als Schleife, sondern als Funktion. D.h. anstelle die Variablen li und re in der Funktion zu ändern und dann die Funktion "im Prinzip" wieder neuzustarten, rufst du die Funktion gleich richtig neu auf und übergibst ihr die geänderten Parameter li und re. (Schau mal ob du damit zu recht kommst. Rekursion muss man verstehen, sonst wird das nie was. Deshalb sag ich erstmal nicht mehr dazu)

    Und nichtdeterministisch?
    Pack an einer Stelle ne Zufallszahl rein mit der du weiterarbeitest. (Is dann halt lang nicht so effizient)

    Mfg
    DerBaer

    0
  • M

    DerBaer schrieb:

    Rekursion muss man verstehen, sonst wird das nie was. Deshalb sag ich erstmal nicht mehr dazu

    Muss man nicht erst Rekursion verstehen?

    0
  • R

    Schon,danke für die schnellen antworten... also mir is aufgefallen, dass die eh schon nichtdeterministisch ist, weil li nicht initialisiert wird. Komischerweise funktioniert die funktion, wenn man li nicht mit = 1 initialisiert für alle zahlen außer quadratzahlen von 16 und vielfachen (256,512,1024,etc.), warum?! keine ahnung....

    jo, also was rekursion ist hab ich verstaden, is ja jetz auch nich allzu schwer... ich kapier allerdings nicht, wie ich re und li beim nächsten aufruf manipulieren kann...
    der prototyp ist ja int wurzel(int a), da kann man ja beim aufruf nur das a manipulieren, oder geht das auch irgendwo anders?

    danke im voraus

    Grüße Randy

    0
  • M

    RandyK schrieb:

    ich kapier allerdings nicht, wie ich re und li beim nächsten aufruf manipulieren kann...y

    Die beiden einfach als Parameter der rekursiven Funktion einführen. Bei jedem rekursiven Aufruf kannst du dann die beiden neuen Werte als Argumente übergeben.

    0
  • R

    ok, danke jetz hab ichs...

    #include <stdio.h>

double wurzel(double li,double re,int a) {
	double y;
	y = (li+re)/2;
	if(li>=re-0.000001) {return y;}
	if(y*y<a) {return wurzel(y,re,a);}
	if(y*y>a) {return wurzel(li,y,a);}
}

int main() {
	int a;
	double b;
	printf("bitte positive ganze zahl eingeben:\n");
	scanf("%i",&a);
	b = wurzel(1,a,a);
	printf("%.4f",b);
	return 0;
}

    Also, vielen Dank an alle Beteiligten und bis bald!
    Grüße Randy

    0
  • R

    ok, sorry jetz bin ichs nochmal...
    hätt ich fast vergessen: hat von euch einer ne ahnung, wie ich die jetzt noch nichtdeterministisch machen kann? Wär für jeden ratschlag dankbar.

    ach ja, oben muss an die funktion als re a/2 übergeben werden und nicht a.... sonst funktionierts iwie nich...

    grüße Randy

    0
  • V

    Ich möchte dich ungern in deiner Euphorie bremsen, aber hast du dir mal die Ergebnisse ausgeben lassen und verglichen?
    sqrt_bisection1 ist hier zu finden.

    typedef union
{
	double f;
	struct
	{
		unsigned long long    frac:52;   // Mantisse
		unsigned long long    exp:11;    // Exponent
		unsigned long long    sign:1;    // Vorzeichen
	}b;
} IEEE754_double;

double sqrt_bisection1(double a)
{
	IEEE754_double s;
	s.f = a;
	s.b.exp = (s.b.exp - 1023) / 2 + 1022;
	double u = s.f;
	s.b.exp += 2;
	double o = s.f;
	double x=0;
	int i;
	for (i = 1; i <= 30; ++i)
	{
		x = 0.5 * (u + o);
		if (x*x > a)
		{
			o = x;
		}
		else
		{
			u = x;
		}
	}
	return x;
}

double wurzel(double li,double re,int a) {
	double y;
	y = (li+re)/2;
	if(li>=re-0.000001) {return y;}
	if(y*y<a) {return wurzel(y,re,a);}
	if(y*y>a) {return wurzel(li,y,a);}
}

int main()
{
    int i;
    for(i=1;i<=100;++i)
		printf("%f\t%f\t%f\t%f\n",i/5.0,wurzel(1,i/5.0,i/5.0),sqrt_bisection1(i/5.0),sqrt(i/5.0));
    return 0;
}

    Ausgabe (eingegrenzt)

    Zahl        wurzel      bisection1  sqrt
--------------------------------------------
4.000000	2.000000	2.000000	2.000000
4.200000	2.000000	2.049390	2.049390
4.400000	2.000000	2.097618	2.097618
4.600000	2.000000	2.144761	2.144761
4.800000	2.000000	2.190890	2.190890
5.000000	2.236068	2.236068	2.236068
5.200000	2.236068	2.280351	2.280351
5.400000	2.236068	2.323790	2.323790
5.600000	2.236068	2.366432	2.366432
5.800000	2.236068	2.408319	2.408319
6.000000	2.449490	2.449490	2.449490
6.200000	2.449489	2.489980	2.489980
6.400000	2.449489	2.529822	2.529822
6.600000	2.449489	2.569047	2.569047
6.800000	2.449490	2.607681	2.607681
7.000000	2.645752	2.645751	2.645751
7.200000	2.645751	2.683282	2.683282
7.400000	2.645752	2.720294	2.720294
7.600000	2.645751	2.756810	2.756810
7.800000	2.645751	2.792848	2.792848
8.000000	2.828427	2.828427	2.828427
8.200000	2.828428	2.863564	2.863564
8.400000	2.828427	2.898275	2.898275
8.600000	2.828427	2.932576	2.932576
8.800000	2.828427	2.966479	2.966479
9.000000	nan	3.000000	3.000000
    0
  • R

    Ich hab vielleicht vergessen zu erwähnen, dass die ausgabe auf 4 nachkommastellen genau und die eingabe nur ganze zahlen sein sollen... aber trotzdem danke 😃

    EDIT: Achso und wegen der nan meldung bei 9... deshalb hab ich ja gemeint, als re muss a/2 übergeben werden und nicht a...

    0
  • M

    RandyK schrieb:

    Ich hab vielleicht vergessen zu erwähnen, dass die ausgabe auf 4 nachkommastellen genau und die eingabe nur ganze zahlen sein sollen... aber trotzdem danke 😃

    Wenn's für ganze double's geht, wird's auch für nichtganze double's gehen.

    RandyK schrieb:

    Achso und wegen der nan meldung bei 9... deshalb hab ich ja gemeint, als re muss a/2 übergeben werden und nicht a...

    Deine Schuld. Ich hätte einen Wrapper erwartet, etwa so:

    inline double wrapper(double x)
{
    return wurzel(1, x / 2, x);
}
    0
Anmelden zum Antworten