If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

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 xn berechnen, wobei x eine reelle Zahl und n eine ganze Zahl ist. Es ist einfach, wenn n 0 ist, da x0=1 für beliebige x ist. Das ist ein guter Basisfall.
Mal sehen was passiert, wenn n positiv ist. Wir erinnern uns daran, dass die Multiplikatoren von Potenzen von x, durch die Addition der Exponenten erreicht wird: xaxb=xa+b. Das gilt für jede Basis x und jeden Exponenten a und b. Wenn also n positiv und gerade ist, dann gilt xn=xn/2xn/2. Wenn du y=xn/2 rekursiv berechnen willst, dann könntest du xn als yy berechnen. Aber was ist, wenn n positiv und ungerade ist? Dann ist xn=xn1x, wobei n1 entweder 0 oder positiv und gerade ist. Wir haben aber gerade gesehen, wie man die Potenzen von x berechnen kann, wenn der Exponent entweder 0 oder positiv und gerade ist. Daher kannst du xn1 rekursiv berechnen und dann dieses Ergebnis verwenden, um xn=xn1x zu berechnen.
Was passiert, wenn n negativ ist? Dann gilt: xn=1/xn. Der Exponent n ist positiv, da es die Negation einer positiven Zahl ist. So kannst du xn rekursiv berechnen und den Kehrwert bilden.
Setzen wir diese Beobachtungen zusammen, erhalten wir den folgenden rekursiven Algorithmus für die Berechnung von xn:
  • Der Basisfall tritt ein, wenn n=0 und x0=1.
  • Wenn n positiv und gerade ist, berechne rekursiv y=xn/2 und dann ist xn=yy. Beachte, dass du in diesem Fall nur einen rekursiven Anruf ausführst, indem du xn/2 nur einmal berechnest, und anschließend das Ergebnis dieses rekursiven Anrufs mit sich selbst multiplizierst.
  • Wenn n positiv und ungerade ist, berechne rekursiv xn1, so dass der Exponent entweder 0 oder positiv und gerade ist. Dann ist xn=xn1x.
  • Wenn n negativ ist, berechne rekursiv xn, so dass der Exponent positiv wird. Dann ist xn=1/xn.

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.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.