iterative funktion in rekursive umschreiben

[RandyK]

Hallo Leute,

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

[RandyK]

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

[unbenannt]

Hast Du nur ein Problem mit "nichtdeterministisch rekursiv" oder mit der Rekursion im Allgemeinen?

Bei einer nichtdeterministischen Programmierung muss ich leider passen. Folgender Hinweis sei aber erlaubt:

double li, re = a, y;

Damit initialisierst Du lediglich "re" - "li" und "y" bleiben undefiniert. Allein damit hast Du schon eine (wahrscheinlich ungewollt) große Dosis Zufall in Deinem Code.

[RandyK]

stimmt ja, da hast du recht..... hab allerdings festestellt, dass wenn ich li nicht mit 1 initialisiere, funktioniert der code zwar soweit, aber nich für quadrate von 16 und vielfachen, also 256, 1024, etc... keine ahnung warum....

also eigentlich hatte ich bisher keine probleme bei rekursion (Euklid, Fakultät, etc), allerdings ist ja diesmal der prototyp int wurzel(int a). Und ich hab keine ahnung wie ich die funktion mit manipuliertem li und re aufrufen kann...

danke im voraus

Randy

[Klotzkopp]

allerdings ist ja diesmal der prototyp int wurzel(int a)

Den wirst du wohl ändern müssen, damit das rekursiv funktioniert.

[RandyK]

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",;

	return 0;

}[/code]

Also, vielen Dank an alle Beteiligten und bis bald!

Grüße Randy

[RandyK]

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

[flashpixx]

Im Moment hast Du einen deterministischen Algorithmus entwickelt, d.h. wenn ich diesen mehrfach laufen lassen, dann wird immer nach endlich vielen Schritten das Ergebnis identisch berechnet.

Ein indeterministischer Algorithmus wäre z.B. ein stochastisches Verfahren

[Wodar Hospur]

Eine nichtdeterministische Lösung wäre z.b. zu testen ob das Quadrat einer zufälligen Zahl = der gegebenen Anfangszahl ist. Denn dann wäre ja gerade die zufällige Zahl = dem gesuchten Ergebnis

Dies kannst du ja dann noch um iterative und rekursive Komponenten ergänzen. (Intervallbereich aus dem die Zufallszahl stammt...)

[RandyK]

Danke für die Antworten... wie kann man denn bei c eine zufallszahl aus einem intervall wählen lassen?

mfg Randy