Lösungsidee 1: "Educated Guess"

Man kennt ja so einige Kubikwurzeln...

• Kubikwurzel von 1 : 1
• Kubikwurzel von 8 : 2
• Kubikwurzel von 27 : 3
• Kubikwurzel von 64 : 4
• Kubikwurzel von 125 : 5
• Kubikwurzel von 1000: 10

Lösungsidee 2: Taschenrechner mit Möglichkeit zur dritten Wurzel ziehen benutzen

Zum Kopfrechnen wenig geeignet...

Lösungsidee 3: Taschenrechner mit Potenzfunktion nutzen

Kubikwurzel x = x^1/3

Zum Kopfrechnen auch weniger geeignet

Lösungsidee 4: Primzahlzerlegung!

8 = 2 * 2 * 2. Die Kubikwurzel von 8 ist 2!

Was tun bei größeren Zahlen?

Beispiel: 216 = 2 * 2 * 2 * 3 * 3 * 3

Lösung: 6 = 2 * 3

Vorgehen

Merke Dir jeden Primfaktor der dreimal vorkommt. Die Lösung ist das Produkt der Primfaktoren die 3 mal vorkommen.

Dieses Verfahren ist prinzipiell im Kopf zu meistern. Divisionen durch kleine Zahlen sind nicht so schwer.

Vorbedingung

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

Der Algorithmus

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

 

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
Setze f auf 1 Erhöhe f um 1 Ist k geteilt durch f (Ganzzahldivision) mal f = k ? Wenn ja: Gib f aus Wenn nein: Ist f kleiner als k ? Wenn ja: Springe zurück zum Erhöhen Wenn nein: Gib 1 aus (kein "echter" Primfaktor gefunden Wie kann man diesen Algorithmus schneller machen?

 Implementierung in Java

/**
* Berechnet die Kubikwurzel einer positiven Zahl
*
* @param k Zahl von der die Kubikwurzel berechnet werden soll.
* @return Ergebnis die Kubikwurzel
*/

public static int kubikwurzelVon(int k) {
   int ergebnis=1;
   do {
      int f = primfaktor(k);
      ergebnis = ergebnis*f;
      k = k / (f*f*f);
   } while (k>1);
   return ergebnis;
}

/**
* Diese Methode berechnet einen Primfaktor des Werts k
* Es wird 1 zurückgegeben wenn es keine anderen Primfaktoren
* gibt
* @param k Die Zahl von der ein Primfaktor berechnet wird
* @return f ein Primfaktor der Zahl oder 1 falls keiner existiert
*/
public static int primfaktor(int k) {
   int f = 1;
   do { 
      f++;
   } while ((k/f*f!=k)&&(f<k));
 
   if (f==k) f=1;
   return f;
}

Der Algorithmus zum Bestimmen eines Primfaktors ist sehr naiv...