Fibonacci-numbers

[attex]

Moin Leute,

ich hab mal im Internet ne kleine Aufgabe gelesen und komm mal wieder nicht weiter.

aufgabe:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

public class main2 {
public static void main(String [] args){
	int[] array1 = new int[1000000];
	int i=0;
	int sum=0;
	array1[1]=1;
	array1[2]=2;
	for(i=2; i<33; i++  ){
		array1[i+1]=array1[i]+array1[i-1];
		System.out.println(array1[i]);
		
	}
	for(i=0; i<33; i++){
		sum += array1[i];
		
	}
	System.out.println("summe:"+sum);
}
}

Mein array1 gibt schon die richtigen zahlen aus:
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
summe:9227463 (plus 1, da ich oben mit i=2 anfange)

aber wenn ich auf der Plattform die Lösung eingebe sagt er dass ich die falsche Lösung habe,
habe ich die Aufgabe richtig gemacht? oder ist nur ein leichtsinnsfehler drin?

Danke

 

[Joose]

Du hast die Aufgabenstellung nicht richtig gelesen.
Suche alle Fibonacci Zahlen bis 4 Millionen und addiere dann die ...... Zahlen. Für die "....." gehört ein Attribut eingesetzt

EDIT: Bei so einer Fragestellung wäre es auch hilfreich vielleicht auf die entsprechende Webseite zu linken.

 

[stg]

Du sollst alle geraden Fibonacci-Zahlen aufaddieren. Also 2+8+34+...

Am Ende muss diese Summe natürlich selbst auch wieder gerade sein.

Diese Summe kannst du übrigens auch in konstanter Zeit ausrechnen, aber das wird nicht gefordert sein.

 

[njans]

Die Summe der ersten n geraden Fibonacci-Zahlen kannst du übrigens auch in konstanter Zeit ausrechnen.

Das bezweifle ich einfach mal. Du meinst vermutlich "linearer Zeit".

 

[stg]

Das bezweifle ich einfach mal. Du meinst vermutlich "linearer Zeit".

Nein, ich meine tatsächlich in konstanter Zeit.

Ich habe meinen Post, nachdem ich kurz darüber nachgedacht habe, noch editiert und die Aussage verschärft. Es ist sogar möglich die Summe der ersten gerade Fibonacci-Zahlen, die kleiner sind als eine vorgegebene Zahl X, in konstanter Zeit zu bestimmen.
Grundkentnisse in Analysis sind aber Vorraussetzung.

 

[attex]

danke habs geblickt und war dann auch richtig )

 

[stg]

@njans:
Nagut, so "wirklich" in konstanter Zeit wird wohl doch etwas schwierig. Ich hab in meinen ersten Überlegung angenommen, dass alle mathematischen Operation in konstanter Zeit ausgeführt werden können. Die Funktionen aus java.math besitzen zwar eine ziemlich gute Konvergenzgeschwindigkeit, aber wirklich konstante Rechenzeit ist das ja nicht. Die einzelnen Fibonacci-Zahlen muss man jedoch nicht berechnen, um die gefragte Summe zu berechnen, sondern es geht auch explizit. Ich meinte das in etwa so:

public class Fibo {
    private static final double sqrt5 = Math.sqrt(5.0);
    private static final double log5 = Math.log(5.0);
    private static final double div = Math.log(0.5+0.5*Math.sqrt(5));
    
    public static void main(String ... args) {
        System.out.println(System.currentTimeMillis());
        System.out.println(Fibo.sumUpEvenFibonacciNumbers(4000000l));  
        System.out.println(System.currentTimeMillis());
        System.out.println(Fibo.sumUpEvenFibonacciNumbers(2000000000l));
        System.out.println(System.currentTimeMillis());
        System.out.println(Fibo.sumUpEvenFibonacciNumbers(4000000000000l));
        System.out.println(System.currentTimeMillis());  
    }
    
    private static long fibonacciNumbersInRange(long maxValue) {
        return (long) Math.floor((Math.log(maxValue+0.5)+0.5*Fibo.log5)/Fibo.div);            
    }
    
    private static long evenFibonacciNumbersInRange(long maxValue) {
            return Fibo.fibonacciNumbersInRange(maxValue)/3+1;
    }
    
    private static long sumUpEvenFibonacciNumbers(long maxValue) {
        return Fibo.sumUpFirstEvenFibonacciNumbers(Fibo.evenFibonacciNumbersInRange(maxValue));
    }
    
    private static long sumUpFirstEvenFibonacciNumbers(long count) {
        return (long) Math.floor(Math.pow(2+Fibo.sqrt5,count) / (5+Fibo.sqrt5));
    }
}

run:
// 1410884048599 // System.currentTimeMillis()
4613732
// 1410884048599 // System.currentTimeMillis()
1485607536
// 1410884048599 // System.currentTimeMillis()
2026369768940
// 1410884048599 // System.currentTimeMillis()
BUILD SUCCESSFUL (total time: 0 seconds)

Eventuelle Überläufe und Rundungsfehler mal außer Acht gelassen, mir gings nur um die Idee..
Die Laufzeit ist jedenfalls praktisch nahezu konstant.

 

[JavaMeister]

Möglicherweise vergeht bei der Rechnung nicht viel Zeit, dennoch ist das keine konstante Laufzeit (O(1)). Dafür müsstest du für beliebige n O(1) hinbekommen.

Aber das ist hier nicht möglich und das zeigst du auch mit deiner Rekursion. Diese verläuft dann, ohne es genauer gerechnet zu haben, mit O(log n) oder O (n log n) aber das ist ja alles andere als O(1).

Daher die irritation.

 

[stg]

Möglicherweise vergeht bei der Rechnung nicht viel Zeit, dennoch ist das keine konstante Laufzeit (O(1)). Dafür müsstest du für beliebige n O(1) hinbekommen.

Aber das ist hier nicht möglich und das zeigst du auch mit deiner Rekursion. Diese verläuft dann, ohne es genauer gerechnet zu haben, mit O(log n) oder O (n log n) aber das ist ja alles andere als O(1).

Daher die irritation.

Da ist nirgends ein rekursiver Aufruf. Das einzige, was nicht wirklich in konstanter Zeit (aber mit sehr schneller Konvergenzgeschwindigkeit) läuft, ist die Auswertung von Math.pow und Math.log.

 

[JavaMeister]

----