---

Geschrieben von Naja am 25.01.2011 um 23:59:

  rekrusives potenzieren

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?

---

Geschrieben von Naja am 26.01.2011 um 00:00:

  RE: rekrusives potenzieren

ich weiß nicht wie ich jetzt die laufzeit berechnen sollte, mit welcher schleifen invariante? oder doch ohne induktion? mich verwirrt das "rekursive"

---

Geschrieben von aal am 27.01.2011 um 19:43:

 

Hast du denn dein Beispiel getestet?

Ich habs etwas ausführlicher geschreiben( fürs beispiel 3^10):

public class ggg
{
int n=10;
int x=3;
int p=0;
int erg;

public void Rechne(){
if(n<0)
System.out.println("falsches n");
p++;
if(p==1)
{
erg=x;
}
else
{
erg*=x;

}

if(p<n)
{
Rechne();
}
else
System.out.println("Ergebnis:"+erg );

}



}

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.

---

Geschrieben von stiba am 22.05.2011 um 23:06:

 

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); }

---

Geschrieben von stiba am 24.05.2011 um 17:40:

  oder noch ein bisschen schöner...

code: 1: 2: 3: 4: 5: 6: pow(Integer x,Integer n) { return n==0?1:n==1?x:n==2?x*x:pow(pow(x,(n-n%2)/2),2)*(n%2==0?1:x); }

Laufzeit:O(log(n))

@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)


puuhh was hab ich grad ne langeweile ;-)