Die Potenzen einer Zahl berechnen

JavaScript hat eine eingebaute pow-Funktion, die die Potenz einer Zahl berechnen kann. Trotzdem können wir eine ähnlich-effiziente Funktion schreiben, die rekursiv arbeitet. Die einzige Einschränkung dabei ist, dass der Exponent ganzzahlig sein muss.

Angenommen, du willst $x ^ n$x, start superscript, n, end superscript berechnen, wobei $x$x eine reelle Zahl und $n$n eine ganze Zahl ist. Es ist einfach, wenn $n$n 0 ist, da $x ^ 0 = 1$x, start superscript, 0, end superscript, equals, 1 für beliebige $x$x ist. Das ist ein guter Basisfall.

Mal sehen was passiert, wenn $n$n positiv ist. Wir erinnern uns daran, dass die Multiplikatoren von Potenzen von $x$x, durch die Addition der Exponenten erreicht wird: $x ^ a \cdot x ^ b = x ^ {a + b}$x, start superscript, a, end superscript, dot, x, start superscript, b, end superscript, equals, x, start superscript, a, plus, b, end superscript. Das gilt für jede Basis $x$x und jeden Exponenten $a$a und $b$b. Wenn also $n$n positiv und gerade ist, dann gilt $x ^ n = x ^ {n / 2} \cdot x ^ {n / 2}$x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript. Wenn du $y = x ^ {n / 2}$y, equals, x, start superscript, n, slash, 2, end superscript rekursiv berechnen willst, dann könntest du $x ^ n$x, start superscript, n, end superscript als $y \cdot y$y, dot, y berechnen. Aber was ist, wenn $n$n positiv und ungerade ist? Dann ist $x ^ n = x ^ {n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x, wobei $n-1$n, minus, 1 entweder 0 oder positiv und gerade ist. Wir haben aber gerade gesehen, wie man die Potenzen von $x$x berechnen kann, wenn der Exponent entweder 0 oder positiv und gerade ist. Daher kannst du $x ^ {n-1}$x, start superscript, n, minus, 1, end superscript rekursiv berechnen und dann dieses Ergebnis verwenden, um $x ^ n = x ^ {n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x zu berechnen.

Was passiert, wenn $n$n negativ ist? Dann gilt: $x ^ n = 1 / x ^ {- n}$x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript. Der Exponent $-n$minus, n ist positiv, da es die Negation einer positiven Zahl ist. So kannst du $x ^ {- n}$x, start superscript, minus, n, end superscript rekursiv berechnen und den Kehrwert bilden.

Setzen wir diese Beobachtungen zusammen, erhalten wir den folgenden rekursiven Algorithmus für die Berechnung von $x ^ n$x, start superscript, n, end superscript:

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.