Programm schmeißt eine Exception-warum?

[Eiche89]

Diese Aufgabe möchte ich programmieren.

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

Hierzu habe ich folgenden Code erstellt.

[JAVA=42]public class Problem14 {

public static int folge2(int n){
int[]f=new int[n];

int i=1;
for(int n1=1; n1<=n; n1++){
int a=n1;
while(a!=1){
if(a%2==0){
a/=2;
i++;
}
else{
a=3*a+1;
i++;
}
if(a<n1){
i+=f[a-1]-1;
a=1;
}
}
f[n1-1]=i;
i=1;

}
int max=0;
int index=0;
for(int j=0; j<n; j++){
if(f[j]>max){
max=f[j];
index=j+1;
}
}
System.out.println("Die Zahl "+index+" produziert die laengste Kette von "+max);
return max;
}
public static void main(String[] args) {
long s=System.currentTimeMillis();
folge2(100000);
long f=System.currentTimeMillis();
long d=f-s;
System.out.println("Dauer: "+d);
}
}[/code]

Das Problem besteht darin dass in der Zeile 20, nämlich

i+=f[a-1]-1;

eine outofbound-Exception kommt und ich nicht weiß wieso. Das passiert übrigens nicht, wenn ich statt 1 Million nur die Zahlen bis 100000 einbeziehe.

Es würde mich echt sehr freuen, wenn ihr mir helfen könntet.

 

[Volvagia]

Out of Bounds bedeutet so viel wie außerhalb der Grenze -> Das Array ist zu klein dimensioniert.

 

[Eiche89]

Danke schonmal aber ich glaube nicht, dass das das Problem ist.

hier mal noch die Fehlermeldung:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1812855949
at Problem14.folge2(Problem14.java:20)
at Problem14.main(Problem14.java:41)

 

[XHelp]

Dann solltest du debugausgaben einbauen um rauszufinden wieso das passiert. Da ja natürlich die Zeilennummer nicht stimmen brigt uns deine Zeilenangabe nicht viel

 

[Volvagia]

Ok, anderstrum. Auf ein negatives Feld kann er natürlich nicht zugreifen, da sie automatisch bei 0 beginnen.

 

[waaarun]

Warum nicht rekursiv dieses Problem angehen?

Wird eine ungerade Zahl, die als int vorhanden ist, mit 3 multipliziert, so kann es zu einem Integer-Overflow kommen. -> AIOOBE

public static void met(int i, int j) {
    if (i == 1) {
        System.out.println(j);
    }

    if (i % 2 == 0) {
        met(i / 2    , j + 1);
    } else {
        met(3 * i + 1, j + 1); // Achtung
    }
}

j ist der Zähler. Muss dann noch entsprechend angepasst werden.

 

[Dekker]

Probiers mal mit long aus. Ich habe das gefühl das bei einem genügend großen Wert für a bei ungleicher größe etwas > integer.maxValue rauskommt. Da dann der Datenbereich zu klein ist und in Java alle Datentypen signed sind wird der Wert dann negativ.

Edit: Mist zu langsam.

 

[Eiche89]

@ waarun:

Rekursives angehen ist gut, habe ich auch erst gemacht, aber die Laufzeit ist leider viel zu lang (nach einer Stunde war noch nix da). Deshalb wollte ich versuchen, dass die Folge nicht für jede Zahl neu berechnet werden muss, sondern dass ich auf schon berechnetes im array zurückgreife.

@ Volvagia:

Du hast recht, ein negativer Index bei nem Array kann natürlich nicht klappen. Jetzt ist nur noch die Frage warum der negative Index überhaupt kommt.

Danke schonmal an euch

 

[Dekker]

Habe ich doch geschrieben...

Der größte mit int darstellbare positive Wert ist (2^31)-1. Dies kommt daher das alle Datentypen in Java signed sind. Wenn du nun eine Zahl hast die ungerade ist, kann es bei einem a das groß genug ist dazu kommen, dass a * 3 +1 > (2^31)-1 ist und damit das Ergebnis negativ wird.

Also änderst du jetzt alle ints durch long und es sollte laufen...

 

[Eiche89]

@ Dekker:

Sorry, deine Antwort kam nach meinem letzten Post.
Das Problem ist dass mein Compiler muckt wenn ich einen Array mit long-Werten indiziere.

 

[nrg]

du greifst einfach falsch auf den arrayindex zu. ich weiß auch nicht, was du da alles machst aber du brauchst doch nur eine schleife, die solange läuft, wie n != 1 (sowas macht man normal nicht, weil das natürlich in endlosschleifen enden kann aber hier ist das ja ein anderes thema) und in dieser schleife prüfen, ob n gerade ist oder nicht. wenn ja durch 2 teilen, ansonsten mal 3 + 1.

Hier mal ein kleines Beispiel:

public class CollatzProblem {

		public static void main(String[] args) {
			int max = 1, maxCount = 1;
			for (int i = 2; i <= 1000000; i++) {
				int curCount = getSequenceCount(i);
				if (curCount > maxCount) {
					maxCount = curCount;
					max = i;
				}
			}
			System.out.println("The longest chain with length " + maxCount + " produces " + max);
		}
		
		public static int getSequenceCount(long n) {
			int count = 0;
			while (n != 1) {
				n = n % 2 == 0 ? n / 2 : 3 * n + 1;
				count++;
			}
			return count;
		}
}

achte darauf, dass du für die berechnung keinen int nimmst. sonst wirst du afaik probleme bekommen.

 

[Dekker]

Was speicherst du den in F eigentlich? Die Zahl der Hops? Wäre es nicht einfach das in eine Variable zu schreiben und zu updaten wenn eine Zahl mehr Iterationen gebraucht hat anstatt immer noch mehr zu speichern und dann das maximum zu bestimmen?

Edit: Ja so wies nrg gemacht hat meinte ich das.

 

[waaarun]

Er will aber auf schon vorhanden Zwischenergebnisse zurückgreifen, und hier bietet es sich an, das ganze rekursiv zu formulieren. Oben fehlt übrigens das return in dem ersten if. Lest doch mal die Beiträge, bevor etwas gepostet wird

Es muss übrigens immer geprüft werden, ob kein Overflow stattfindet, weil nicht bewiesen ist, das für irgendeine Zahl <= 1 mil. keine Zahl >= 2^31 wird...

 

[nrg]

Es muss übrigens immer geprüft werden, ob kein Overflow stattfindet, weil nicht bewiesen ist, das für irgendeine Zahl <= 1 mil. keine Zahl >= 2^31 wird...

oder einfach long nehmen (edit: probiers doch einfach. bei meiner lösung mit int wäre das bei 113383 die endlosschleife und bei deiner der stackoverflow)

 

[Eiche89]

Das mit der Long-Kovertierung hat jetzt geglaubt. Danke an alle für die flotte Hilfe.

 

[waaarun]

Und, wenn ich long nehme, wäre das etwas anderes, als blind drauf zu vertrauen, dass es dann keinen Overflow gibt? Mein rekursiver Ansatz sieht jetzt übrigens so aus:

    public static int count(int i, HashMap<Integer, Integer> hm) {
        if (hm.containsKey(i)) {
            return hm.get(i);
        }

        int j;
        if (i % 2 == 0) {
            j = count(i / 2, hm) + 1;
        } else {
            j = count(3 * i + 1, hm) + 1;
        }
        hm.put(i, j);

        return j;
    }

    public static void main(String[] args) {
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        hm.put(1, 1);

        for (int i = 1; i < 21; i++) {
            System.out.println(i + ": " + count(i, hm));
        }
    }

 

[Dekker]

Und, wenn ich long nehme, wäre das etwas anderes, als blind drauf zu vertrauen, dass es dann keinen Overflow gibt? Mein rekursiver Ansatz sieht jetzt übrigens so aus:

    public static int count(int i, HashMap<Integer, Integer> hm) {
        if (hm.containsKey(i)) {
            return hm.get(i);
        }

        int j;
        if (i % 2 == 0) {
            j = count(i / 2, hm) + 1;
        } else {
            j = count(3 * i + 1, hm) + 1;
        }
        hm.put(i, j);

        return j;
    }

    public static void main(String[] args) {
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        hm.put(1, 1);

        for (int i = 1; i < 21; i++) {
            System.out.println(i + ": " + count(i, hm));
        }
    }

Na dann lass es jetzt mal mit größeren Zahlen als 21 laufen....

 

[nrg]

ja ob rekursiv oder iterativ ist ja egal. wollte damit eigentlich nur an einem beispiel zeigen, dass der TO da etwas am ziel vorbeigeschossen ist

edit: achso. i ist ja nach wie vor ein int. na dann lass es doch mal mit der zahl 113383 laufen

 

[waaarun]

Na dann lass es jetzt mal mit größeren Zahlen als 21 laufen....

Die einzig vernünftige Lösung wäre BigInteger, wenn bis zur gewünschten Zahl noch niemand vorher getestet hat

Und es ich nicht so einfach, so etwas iterativ zu formulieren, wenn auf bereits berechnete Ergebnisse zurückgegriffen werden soll...

 

[nrg]

Die einzig vernünftige Lösung wäre BigInteger, wenn bis zur gewünschten Zahl noch niemand vorher getestet hat

zum dritten mal. long reicht (rumindest bis 1mio) aus...

 

[waaarun]

Konnte nun auch mal testen, hier nochmal mit long und debug ausgabe:

public class Main {

    public static int count(long i, HashMap<Long, Integer> hm) {
        System.out.print(i + " ");

        if (hm.containsKey(i)) {
            return hm.get(i);
        }

        int j;
        if (i % 2 == 0) {
            j = count(i / 2, hm) + 1;
        } else {
            j = count(3 * i + 1, hm) + 1;
        }
        hm.put(i, j);

        return j;
    }

    public static void main(String[] args) {
        HashMap<Long, Integer> hm = new HashMap<Long, Integer>();
        hm.put(1L, 1);

        for (int i = 1; i < 21; i++) {
            System.out.println(" - " + i + ": " + count(i, hm));
        }

    }
}

Jetzt sieht man relativ schnell, dass auch für kleinere Werte viele der "Zwischenwerte" größer als der Ausgangswert werden können.
Aber, solange man es noch nicht ausprobiert hat, kann man auch nicht mit Sicherheit sagen, für welche Werte der Wertebereich des longs noch ausreichen wird und für welche nicht mehr. Wenn man Pech hat, gibt es einen Overflow, der nicht bemerkt wird, weil das Resultat immer noch ein positiver Wert ist.