int zahl = 12;
for (int i = 2; i <= zahl; i++) { (1)
while (zahl % i == 0) { (2)
System.out.println(i); (3)
zahl = zahl / i; (4)
}
}
Schreibe das Programm Faktorisierung, das alle Primfaktoren einer Zahl ausgibt. Im Unterschied zum Programm Teiler bei den Aufgaben zur FOR-Schleife sollen mehrfach vorkommende Teiler auch mehrfach ausgegeben werden. Die Faktoren ergeben miteinander multipliziert wieder die Zahl selbst.
Beispiel der Ausgaben der Programme:
| Zahl | Teiler | Faktorisierung |
|---|---|---|
12 |
1,2,3,4,6,12 |
2,2,3 |
16 |
1,2,4,8,16 |
2,2,2,2 |
60 |
1,2,3,4,5,6,10,12,15,20,30,60 |
2,2,3,5 |
Schreibe das Programm Kürzen, das einen Bruch, der über einen Zähler und einen Nenner definiert ist, gekürzt ausgibt. Lösung
int zahl = 12;
for (int i = 2; i <= zahl; i++) { (1)
while (zahl % i == 0) { (2)
System.out.println(i); (3)
zahl = zahl / i; (4)
}
}
| 1 | i durchläuft alle Werte von 2 bis zum aktuellen Wert von zahl. Beachte, dass in diesem Programm der Wert von zahl in der Schleife geändert wird, so dass die obere Grenze der Schleife sich ändern kann! |
| 2 | Solange die aktuelle Zahl zahl durch das aktuelle i teilbar ist … |
| 3 | … gib das zugehörige i aus (es ist dann automatisch ein Primfaktor) und … |
| 4 | … speichere in zahl das Ergebnis von zahl/i |
Zur Verdeutlichung der Funktionsweise des Programms sei hier der Ablauf am Beispiel der Zahl 12 gezeigt, indem die Inhalte der Variablen im laufenden Programm dargestellt werden:
|
|
|
Neuer Wert von |
12 |
2 |
true |
6 |
6 |
2 |
true |
3 |
3 |
2 |
false |
3 |
3 |
3 |
true |
1 |
1 |
3 |
false |
1 |
Ausgeben werden die Werte, für die zahl%i==0 erfüllt ist, hier also 2, 2 und 3.
Am Ende, wenn die while-Schleife verlassen wird, ist das i größer als zahl, so dass auch die for-Schleife beendet wird und das Programm zu einem Ende kommt.
int zaehler = 12;
int nenner = 60;
int[] faktorenZaehler = new int[0]; (1)
int[] faktorenNenner = new int[0];
int zahl = zaehler; (2)
for (int i = 2; i <= zahl; i++) {
while (zahl % i == 0) {
int[] faktorenFeld = new int[faktorenZaehler.length + 1]; (3)
for (int j = 0; j < faktorenZaehler.length; j++) {
faktorenFeld[j] = faktorenZaehler[j]; (4)
}
faktorenFeld[faktorenZaehler.length] = i; (5)
faktorenZaehler = faktorenFeld; (6)
zahl = zahl / i;
}
}
zahl = nenner; (7)
for (int i = 2; i <= zahl; i++) {
while (zahl % i == 0) {
int[] faktorenFeld = new int[faktorenNenner.length + 1];
for (int j = 0; j < faktorenNenner.length; j++) {
faktorenFeld[j] = faktorenNenner[j];
}
faktorenFeld[faktorenNenner.length] = i;
faktorenNenner = faktorenFeld;
zahl = zahl / i;
}
}
for (int i=0;i<faktorenZaehler.length;i++){
for (int j=0;j<faktorenNenner.length;j++){
if (faktorenZaehler[i]==faktorenNenner[j]){ (8)
faktorenZaehler[i]=1; (9)
faktorenNenner[j]=1;
j=faktorenNenner.length; (10)
}
}
}
int zaehlerGekürzt=1;
for (int i=0;i<faktorenZaehler.length;i++){
zaehlerGekürzt*=faktorenZaehler[i]; (11)
}
int nennerGekürzt=1;
for (int i=0;i<faktorenNenner.length;i++){
nennerGekürzt*=faktorenNenner[i];
}
System.out.println("Der Bruch "+zaehler+"/"+nenner+" ist gekürzt "+zaehlerGekürzt+"/"+nennerGekürzt);
Die Lösung dieses Programms ist sehr umfangreich und die Lösung ist nicht ganz einfach. Wir werden in Kürze Möglichkeiten kennenlernen, dieses Programm kompakter und übersichtlicher zu schreiben.
Betrachten wir nun aber die angegebene Lösung:
| 1 | Hier wird eine Feldvariable der Länge 0 erzeugt, also ohne einen einzigen freien Platz. Das mag etwas ungewöhnlich erscheinen, wird aber im Lauf des Programms angepasst. |
| 2 | Für den folgenden Abschnitt wird in zahl der Zähler des Bruchs gespeichert. Im Prinzip wird im Folgenden wie im Programm Faktorisierung vorgegangen, nur dass hier die Teiler nicht ausgegeben sondern gespeichert werden. |
| 3 | Eine Feldvariable namens faktorenFeld wird eingeführt, die einen Eintrag mehr hat als faktorenZaehler. Im ersten Durchlauf wird faktorenFeld also 0+1=1 freien Eintrag haben. |
| 4 | Nun werden alle Inhalte von faktorenZaehler nach faktorenFeld kopiert. Der letzte Platz von faktorenFeld ist danach noch frei, da es ja einen Eintrag mehr enthält als faktorenZaehler. |
| 5 | Der letzte Platz von faktorenFeld wird mit dem neuen Primfaktor belegt. |
| 6 | faktorenZaehler wird mit faktorenFeld nun gleichgesetzt, enthält jetzt also einen Primfaktor mehr als davor. |
| 7 | Für den Nenner passiert genau das Gleiche wie für den Zähler. |
| 8 | In diesem Abschnitt werden Stück für Stück die Primfaktoren verglichen. |
| 9 | Stößt man auf einen Primfaktor, der in beiden Primfaktormengen (die vom Zähler und die vom Nenner) vorkommt, so wird dieser Primfaktor in beiden Primfaktormengen auf 1 gesetzt. |
| 10 | Nachdem ein solcher gemeinsamer Primfaktor gefunden wurde, wird zum nächsten Primfaktor des Zählers übergegangen. Das j=faktorenNenner.length; sorgt dafür, dass vorerst keine weiteren Einträge von faktorenNenner auf 1 gesetzt werden, da die Schleife für j dadurch nicht weiter durchlaufen wird, sondern erst wieder für das nächste i. |
| 11 | Multipliziere nun alle Primfaktoren miteinander. Da die in beiden Primfaktorenmengen vorkommenden Primfaktoren jeweils auf 1 gesetzt wurden, erhält man nur das Produkt der noch übrigen Primfaktoren. |