Schnelles Potenzieren

Hallo Liebes Forum,

Ich habe folgende Aufgabe:
Die Berechnung der Potenzfunktion x^n kann für ganze Zahlen n≥0 durch eine Reduktion des Exponenten in folgender Form erfolgen:

x^n = {
1 für n = 0
(x*x)^n/2 für n grade und n > 1
x * x ^ n-1 sonst


1. Prüfen Sie an dem Zahlenbeispiel x = 2 und n = 13, ob die Berechnung der Potenz mit diesem Algorithmus korrekt ist.

2. Schreiben Sie eine rekursive Methode zur Berechnung der Potenz und ermitteln Sie die Anzahl der rekursiven Aufrufe in Abhängigkeit von der Größe des Exponenten n.
Zu erstens habe ich folgende Gedanken:

erster Durchlauf: 2 * (2 ^ 13 - 1) = 8192
zweiter Durchlauf: ((2 * 2)^ 12 / 2) = 4096
dritter Durchlauf: ((2 * 2) ^ 6 / 2) = 64
vierter Durchlauf: 2 * (2 ^ 3 - 1) = 8
fünfter Durlauf: ((2 * 2) ^ 2 / 2) = 4
sechster Durchlauf: 2 * (2 ^ 1 - 1) = 2
siebenter Durchlauf : n = 0 return 1;
Zu 2. habe folgenden Code:


Java:
public static double fastPotRek(double x, int n){
        // TODO: recursive variation
        if (n == 0) return 1;
        else if (n % 2 == 0 && n > 1) return fastPotRek(x*x,n/2);
        else return fastPotRek(x*x,n-1);
    }
Die Aufrufe lasse ich mit einer public static int innerhalb der Klasse zählen, da kommt Momentan auch 7 raus wie in meiner Aufzählung also läuft das immerhin :D

Jetzt ist meine Frage wo ist mein Denkfehler?
 
Und.... du kannst dir noch zunutzemachen:
2^x=1<<x;
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben