Standard-Algorithmen	Bauernmultiplikation quadratische Gleichung Eratosthenes ggt Bachet Heron Potenz Primfaktorzerlegung Halbierung Newton pi-Bestimmung Sortieren Backtracking Pfad: Startseite / Fächer / Informatik / Algorithmus / Standard-Algorithmen / Potenz
Autor: mk 11.09.2008 11:16:19 4262	schnelles Potenzieren

Folgender Algorithmus in Pascal-Notation (D.Herrmann, Algorithmen Arbeitsbuch, S. 31) liefert die Potenz a^b für reelles a>0 und natürliche Zahlen b:

x := a; y := b; z := 1;
while y > 0 do
begin
  if odd(y) then z := z*x;
  y := y div 2;
  x := x*x;
end;

Aufgaben

• Implementiere und teste den Algorithmus.
• Finde Vorbedingung, Schleifeninvariante (Vorschlag {z*x^y = a^b}) und Nachbedingung und führe einen formalen Korrektheitsbeweis.
• Zeichne ein Struktogramm mit Zusicherungen.
• Implementiere den 'naiven' Potenzierungsalgorithmus (for-Schleife) und vergleiche die beiden Algorithmen durch Zeitmessungen ( Delphi, Python). Dokumentiere deine Tests.

Lösung in Delphi

potenz.zip

lokal