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?
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Naja: 25.01.2011 23:59.
und zur Laufzeit:
Ich denke ,dass man hier die "Ablaufdauer" des Algortihmus berechnen muss..also wie lange das Programm braucht , um das Ergebnis zu liefern.
System.currentTimeMillis() das gibt die Aktielle zeit wieder. So könnte man Start und Endzeit bestimmen.
27.01.2011 19:43
stiba unregistriert
code:
1:
2:
3:
4:
function pow(x,n)
{
return n==0?1:n==1?x:n==2?x*x:(n%2==0)?pow(pow(x,n/2),2):x*pow(pow(x,(n-1)/2),2);
}
@aal Die laufzeit eines algorithmus hat nicht auch nur das geringest mit der Ausführungsdauer zu tun! Es geht um die rechenschritte die der algorithmus braucht!
@naja deine Idee war zwar rekursiv, aber weit weg von einer effizienten!
Aber ist ja auch eh schon lang her, und die Klausur bestimmt bereits in der Hose? ;-)
Dein Algo hatte die laufzeit O(n)
