|
|
Hi Leute,
ich habe gerade dieses Forum hier entdeckt, eine gute Sache!
Ich habe eine Teilaufgabe die von mir verlangt, dass ich einen "besonders Effizienten" Algorithmus zur berechnung von x^n angebe. x ist reel und n eine natürliche Zahl.
Ein Hinweis auf das Funktionsprinzip soll sein: x^9=x*x^4*x^4
(ich hab das Gefühl, dass man sich diesen Hinweis an die Backe kleben kann..., naja, beide Potenzen sind eben gleich sowie eine Restpotenz? Bisher weiß ich noch nicht viel damit anzufangen)
Die eigendliche Teilaufgabe ist:
Entwickelt einen rekursive Algorithmus in JAVA, der die Potenz x^n möglichst effizient berechnet, das heißt die Laufzeit soll c*log(n) für eine natürliche Zahl c sein. Der Algorithmus darf keine Schleife enthalten und auch nicht Math.power verwenden. Beweist seine Laufzeit, d.h. insbesondere findet ein passendes c.
Hinweis: Um die Laufzeit zu bestimmen, zählt ihr die Anzahl der rekursiven Aufrufe des Algorithmus.
Meine Gedanken dazu:
ich kriege ein x und ich kriege ein n, also könnte ich, den Algorithmus:
public double Rechne(double x, int n)throws IllegalArgumentEcxeption{
if(n<0) throw new IllegalArgumentException("falsches n");
int p=0;
p++;
x=x*x;
if(p<=n) return Rechne(x,p);
}
was haltet ihr davon? ist richtig?
|
|
