Schnelles Potenzieren

Diskutiere Schnelles Potenzieren im Java Basics - Anfänger-Themen Bereich.
B

BlueLizard

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?
 
A

abc66

Und.... du kannst dir noch zunutzemachen:
2^x=1<<x;
 
B

BlueLizard

Du hast noch Math.pow(...,n/2); o. Ä. vergessen. ;)
Naja ich vermute mal es geht darum es nicht mit Math.pow zu lösen, sonst wäre die Aufgabe ja hinfällig, ich könnte genauso gut dann auch einfach Math.pow(x,n) angeben und wäre fertig.

Der Bitshift basiert doch auch darauf Math.pow zu ersetzen, aber das ist ja alles nicht sinn der Sache.
 
Thema: 

Schnelles Potenzieren

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben