Algorithmus

Vorbedingung

Die vorgebene Zahl k soll eine Kubikwurzel aus den natürlichen Zahlen kleiner, gleich 100 besitzen

Der Algorithmus

Verbale Beschreibung UML Diagramm
  1. Merke Dir Ergebnis e mit dem Wert 1
  2. Bestimme einen Primfaktor f der Zahl k
  3. Multipliziere e mit f und merke das Ergebnis als e
  4. Teile die Zahl k dreimal durch den Primfaktor f.
  5. Merke dieses Ergebnis als k
  6. Wiederhole Algorithmus ab Schritt 2 wenn k größer als 1 ist.
  7. Die Lösung des Problems ist e
 UML Flussdiagramm

 

Wir gehen davon aus, dass Merken, Dividieren, Multiplizieren elementare Anweisungen sind die nicht weiter verfeinert werden müssen.

Der Algorithmus wird immer terminieren, da die Division durch den letzten Primfaktor eins ergeben wird.

Das Teilproblem Primfaktor von k bestimmen ist aber kein elementares Problem. Zur Lösung dieses Teilproblems wird eine neue Lösungsidee und ein neuer Algorithmus benötigt.

Teilalgorithmus Primfaktor einer Zahl k

Verbale Beschreibung UML Diagramm
  1. Setze f auf 1
  2. Erhöhe f um 1
  3. Ist k geteilt durch f (Ganzzahldivision) mal f = k ?
    1. Wenn ja: Gib f aus
    2. Wenn nein: Ist f kleiner als k ?
      1. Wenn ja: Springe zurück zum Erhöhen
      2. Wenn nein: Gib 1 aus (kein "echter" Primfaktor gefunden

Wie kann man diesen Algorithmus schneller machen?

 

Flussdiagramm Primfaktor