Hallo,
ich habe folgendes Problem:
Aufgabenstellung ist ein Programm zu schreiben, welches für ein gegebenes Intervall (welches bei mir über die Konsole abgefragt wird) von natürlichen Zahlen die sogenannte Collatz-Sequenz zu berechnen.
Kurzerklärung: Ist eine Zahl ungerade, so wird sie mit 3 multipliziert und 1 addiert, ist sie gerade, wird sie durch 2 geteilt. Das macht man solange, bis man irgendwann bei der Zahl 1 landet, dann ist die Sequenz fertig berechnet.
Das ganze soll wie gesagt für ein Zahlenintervall berechnet werden (also z.B. 5-10, dann berechnet das Programm die Anzahl der Durchläufe (Sequenz) für die Zahl 5 (das sind 5 Durchläufe), für die Zahl 6 (8 Durchläufe), usw. bis einschl. Zahl 10).
Ansich funktioniert das auch schon alles, ich versuche gerade allerdings das ganze ein wenig zu optimieren.
Dazu habe ich eine Besonderheit des Ganzen beachtet, weswegen im folgenden Code bei einem switch-case kein "break" kommt: Ist eine Zahl ungerade, und man multipliziert sie mit 3 und addiert 1, dann ist sie danch immer gerade!
Durch diese Besonderheit kann man sich bei jedem Schleifendurchlauf die Überprüfung auf gerade/ungerade einmal sparen, wenn die Zahl ungerade war, da sie danch immer gerade ist, und kann folglich die Zahl danach direkt durch 2 teilen, bevor man erneut auf gerade/ungerade prüft.
Der nächste Optimierungspunkt ist nun das eigentliche Problem:
Vor allem bei größeren Intervall stößt man immer wieder auf Zwischenergebnisse in der Berechnung, für die man schon die Anzahl der Durchläufe berechnet hat. Also könnte man die Berechnung im Falle einer Übereinstimmung (das momentane Zwischenergebnis ist noch nicht bei 1 angelangt, aber wurde bereits berechnet) die weitere Berechnung der Sequenze abbrechen, den momentanen Counter zu dem bereits berechneten Counter für die jeweilige Zahl addieren, und direkt mit der nächsten Zahl im Intervall fortfahren.
Ein Beispiel hierfür:
Die Zahl 5 durchläuft folgende Sequenz:
5 -> 16 -> 8 -> 4 -> 2 -> 1 => 5 Schritte bis man zur 1 gelangt.
Die Zahl 6 durchläuft folgende Sequenz:
6 -> 3 -> 10 -> 5 (******) Für die Zahl 5 wissen wir nun schon, dass wir 5 Schritte brauchen.
Wie kann ich das nun abfragen, und die 3 Schritte von der 6 bis zur 5 zur Anzahl der Schritte von der 5 bis zur 1 addieren?
Hier das komplette Programm, sorry für die vielen Kommentarzeilen, aber das ist in der Aufgabenstellung so erwünscht:
Wie ihr seht, habe ich es versucht, über ein if-Statement mit Arrays.binarySearch abzufragen, aber das ganze funktioniert nicht. Je nach Intervallgröße läuft das Programm oder ich bekomme einen "ArrayOutOfBounds"-Exception Error. Die Ergebnisse sind aber sowieso immer völlig falsch. Habe nun schon alles mögliche rumprobiert, auch ohne binarySearch, mit einer for-Schleife und if-Statement, aber ich komme einfach nicht drauf.
Sorry für die Textwand, und ich hoffe jemand versteht das Problem und kann mir weiterhelfen!
LG
ich habe folgendes Problem:
Aufgabenstellung ist ein Programm zu schreiben, welches für ein gegebenes Intervall (welches bei mir über die Konsole abgefragt wird) von natürlichen Zahlen die sogenannte Collatz-Sequenz zu berechnen.
Kurzerklärung: Ist eine Zahl ungerade, so wird sie mit 3 multipliziert und 1 addiert, ist sie gerade, wird sie durch 2 geteilt. Das macht man solange, bis man irgendwann bei der Zahl 1 landet, dann ist die Sequenz fertig berechnet.
Das ganze soll wie gesagt für ein Zahlenintervall berechnet werden (also z.B. 5-10, dann berechnet das Programm die Anzahl der Durchläufe (Sequenz) für die Zahl 5 (das sind 5 Durchläufe), für die Zahl 6 (8 Durchläufe), usw. bis einschl. Zahl 10).
Ansich funktioniert das auch schon alles, ich versuche gerade allerdings das ganze ein wenig zu optimieren.
Dazu habe ich eine Besonderheit des Ganzen beachtet, weswegen im folgenden Code bei einem switch-case kein "break" kommt: Ist eine Zahl ungerade, und man multipliziert sie mit 3 und addiert 1, dann ist sie danch immer gerade!
Durch diese Besonderheit kann man sich bei jedem Schleifendurchlauf die Überprüfung auf gerade/ungerade einmal sparen, wenn die Zahl ungerade war, da sie danch immer gerade ist, und kann folglich die Zahl danach direkt durch 2 teilen, bevor man erneut auf gerade/ungerade prüft.
Der nächste Optimierungspunkt ist nun das eigentliche Problem:
Vor allem bei größeren Intervall stößt man immer wieder auf Zwischenergebnisse in der Berechnung, für die man schon die Anzahl der Durchläufe berechnet hat. Also könnte man die Berechnung im Falle einer Übereinstimmung (das momentane Zwischenergebnis ist noch nicht bei 1 angelangt, aber wurde bereits berechnet) die weitere Berechnung der Sequenze abbrechen, den momentanen Counter zu dem bereits berechneten Counter für die jeweilige Zahl addieren, und direkt mit der nächsten Zahl im Intervall fortfahren.
Ein Beispiel hierfür:
Die Zahl 5 durchläuft folgende Sequenz:
5 -> 16 -> 8 -> 4 -> 2 -> 1 => 5 Schritte bis man zur 1 gelangt.
Die Zahl 6 durchläuft folgende Sequenz:
6 -> 3 -> 10 -> 5 (******) Für die Zahl 5 wissen wir nun schon, dass wir 5 Schritte brauchen.
Wie kann ich das nun abfragen, und die 3 Schritte von der 6 bis zur 5 zur Anzahl der Schritte von der 5 bis zur 1 addieren?
Hier das komplette Programm, sorry für die vielen Kommentarzeilen, aber das ist in der Aufgabenstellung so erwünscht:
Java:
import java.io.*; // -- Java-Paket für Ein-/Ausgabe
import java.util.*;
class Input // -- Klasse für Eingabe der Zahlen für das Intervall
{
// -- Variablendeklaration
static int lowNum;
static int highNum;
BufferedReader in = new BufferedReader(new InputStreamReader( System.in ) ); // -- InputStreamReader 'in' zum Einlesen der Konsoleneingabe
int setLowNum() // -- Methode getLowNum - Festlegen der unteren Intervallgrenze
{
try {
System.out.println("Bitte untere Intervallgrenze eingeben: ");
lowNum = Integer.parseInt(in.readLine()); // -- String 'in' in Integer umwandeln und als 'lowNum' ablegen
} catch( IOException ex ) {
System.out.println( ex.getMessage() );
}
return lowNum;
}
int setHighNum() // -- Methode getHighNum() - Festlegen der oberen Intervallgrenze
{
try {
System.out.println("Bitte obere Intervallgrenze eingeben: ");
highNum = Integer.parseInt(in.readLine()); // -- String 'in' in Integer umwandeln und als 'highNum' ablegen
} catch( IOException ex ) {
System.out.println( ex.getMessage() );
}
if(highNum-lowNum < 0) // -- Überprüfung ob Intervallgrenzen gültig sind ('highNum' muss größer oder gleich 'lowNum' sein)
{
System.out.println("FEHLER: Die Zahl ist zu niedrig! Die obere Intervallgrenze muss größer sein, als die untere Intervallgrenze!");
setHighNum();
}
return highNum;
}
}
class Collatz
{
public static void main(String[] args) {
// -- Methoden aus Klasse 'Input' initiieren und aufrufen
Input lowNum = new Input();
lowNum.setLowNum();
Input highNum = new Input();
highNum.setHighNum();
// -- Ausgabe Intervallbereich
System.out.println("Folgender Intervall für die Berechnung der Collatz-Sequenzen wurde festgelegt: [" +Input.lowNum +"," +Input.highNum +"]");
System.out.println("Berechnung der Collatz-Sequenzen...");
System.out.println();
long timeStamp1 = System.currentTimeMillis();
// -- Aufruf der Methode 'calculateCollatz()'
calculateCollatz();
long timeStamp2 = System.currentTimeMillis();
System.out.println();
System.out.println("Benötigte Zeit für die Berechnung: " +(timeStamp2-timeStamp1) +"ms");
}
public static void calculateCollatz() // -- Methode 'calculateCollatz' zur Berechnung der Collatz-Sequenzen für das festgelegte Intervall
{
int anzahl = Input.highNum-Input.lowNum+1; // Anzahl Zahlen (Größe) des Intervalls
int zahl[] = new int[anzahl]; // Deklaration und Initialisierung des Arrays 'zahl' mit der Größe 'anzahl'
for(int i=0; i<zahl.length; i++)
{
zahl[i] = Input.lowNum++; // Array 'zahl' mit den Zahlen des Intervalls via for-Schleife befüllen
}
int counter[] = new int[zahl.length]; // Deklaration und Initialisierung des Arrays 'counter' mit der Länge des 'zahl' Arrays
for(int i=0; i<zahl.length; i++) // counter -> Anzahl Durchläufe für die Collatz-Sequenzen für jede Zahl des Intervalls
{
int zwischenergebnis = zahl[i]; // zwischenergebnis = jeweilige Zahl des Intervalls (anfangs 1. Zahl des Intervalls)
while(zwischenergebnis > 1) // Schleife zur Berechnung der Collatz-Sequenzen für die Zahl 'zahl[i]'
{
// -- Modulo-Operation (result = Prüfvariable -> zahl[i] gerade/ungerade)
int result = 0;
result = zwischenergebnis%2;
switch(result)
{
case 1: // -- zahl[i] ist ungerade
zwischenergebnis = (zwischenergebnis * 3) +1;
counter[i] += 1; // Zähler 'counter' nach jedem Durchlauf um 1 hochzählen
case 0: // -- zahl[i] ist gerade
zwischenergebnis = zwischenergebnis / 2;
counter[i] += 1; // Zähler 'counter' nach jedem Durchlauf um 1 hochzählen
break;
}
if(Arrays.binarySearch(zahl, zwischenergebnis) > 0);
{
counter[i] = counter[zwischenergebnis] + counter[i];
zwischenergebnis = 1;
}
}
}
for(int i=0; i<zahl.length; i++)
{
// -- Ausgabe der Ergebnisse
System.out.println("Anzahl Durchläufe für die Zahl " +zahl[i] + ": " +counter[i]);
}
}
}Wie ihr seht, habe ich es versucht, über ein if-Statement mit Arrays.binarySearch abzufragen, aber das ganze funktioniert nicht. Je nach Intervallgröße läuft das Programm oder ich bekomme einen "ArrayOutOfBounds"-Exception Error. Die Ergebnisse sind aber sowieso immer völlig falsch. Habe nun schon alles mögliche rumprobiert, auch ohne binarySearch, mit einer for-Schleife und if-Statement, aber ich komme einfach nicht drauf.
Sorry für die Textwand, und ich hoffe jemand versteht das Problem und kann mir weiterhelfen!
LG
