iterativ

Question

Ein Freund hat mich herausgefordert, ein Programm zu schreiben, die (int a, int n, int k) drei ganze Zahlen erhält und berechnet effizient wie möglich, a^n mod k

ich kam mit dieser Lösung

public static int rec(int a,int n,int k) //calc a^n mod k 
    { 
     if(n == 1) 
      return a % k; 
     int exp1 = rec(a, n/2, k), exp2 = exp1; 
     if(n % 2 == 1) 
      exp2 = rec(a, n/2 + 1, k); 

     return (exp1 * exp2) % k; 
    } 

Es ist eine unglaublich einfache rekursive Lösung, abhängig von der Tatsache, dass a^(b+c) mod d = (a^b mod d * a^c mod d) mod d, und in logarithmischer Zeit läuft. Zumindest theoretisch.

In der Praxis, als wir unsere Lösung maßen, war seine lineare Zeitlösung besser als meine Lösung. Ich vermute, dass ich eher Rekursionen als Schleifen verwende. Ist das sinnvoll? Wenn ja - wie kann ich diesen Code in ein iteratives Programm umwandeln?

Answer 1

Macht das Sinn?

Ja. Wie Boris The Spider herausstellte, gibt es in Java keine Tail-Optimierung.

Wie kann ich diesen Code in ein iteratives Programm umwandeln?

Lassen Sie mich eine iterative Lösung copy-paste Potenz einer Zahl von here

int pow(int x, int n) { 
int res = 1; 
while(n > 0) { 
    if(n % 2 == 1) { 
     res = res * x; 
    } 
    x = x * x; 
    n = n/2; 
} 
return res; 
} 

Haftungsausschluss zu berechnen: Obwohl der obige Code mir sieht ok, ich habe es persönlich nicht getestet.