hallo,
ich muss für die schule ein programm schreiben hab aber kein plan wie ich das machen soll......wir sollen rekursiv eine fibonacci folge erstellen. Nun ich habe schon ein paar lösungsansätze gefunden im e-net hab aber kein plan was ich damit anfangen soll. wäre cool wenn einer von euch nen proggi zu verfügung hätte....

schon ma im vorraus vielen dank

--------------
draco.ophelia

[peschmae]

Wie rechnet man die denn aus?

MfG Peschmä

naja das ist da problem ich hab keine ahnung

[lost-prophet]

fibonacci folge also rekursiv?

also die fibonacci folge sieht wiefolgt aus, wenn ich mich nicht irre:

1, 1, 2, 3, 5, 8, 13, 21, ...

Das Bildungsgesetz lautet wie folg:

fib(n) = fib(n-1) + fib(n-2) mit fib(1) = fib(2) = 1

die zahl bildet sich also aus der addition der beiden vorgänger. Zudem muss man wissen, dass die beiden ersten elemente 1 sind.


damit ergibt sich die relativ einfache rekursive funktion:

 public static long fib(int a){
  if (a==1||a==2) return 1;
  else return fib(a-1)+fib(a-2);
}

was aber das wichtigeste dabei ist, dass du verstehst, wie eine rekursive funktion funktioniert und fibonacci ist nunmal eines der einfachsten beispiele

grüße

lost-prophet

[Ben]

*pfeif*
--> http://wikisource.org/wiki/Fibonacci_sequence#Java

[Sym]

Wobei eine solche Rekursion ja nicht gerade das gelbe vom Ei ist - auf die Geschwindigkeit bezogen.

[nove]

Ein Kumpel von mir hat so was mal geschrieben und hat seinen SOPRA Tutor ziehmlich blöd dastehen lassen, was die Geschwindigkeit betrifft. Mein Kumpel fasselte was von Cachen der Ergebnisse. Wie oder Was keine Ahnung ich werd mal nachhacken falls ich Ihn die nächste Zeit sehe.

[pago]

// Unser cache
private static List fibos = new ArrayList();
public static long fib(int a) {
	// Sonderfälle (cache nicht nötig)
	if(a <= 2) { // a < 3
		return 1;
	}
	// Cache auslesen
	Long cachedFibo = (Long)fibos.get(a);
	// Cache existiert, gib dessen Wert zurück
	if(cachedFibo != null) {
		return cachedFibo.longValue();
	}
	// Kein Cache, fibo berechnen, cachen, zurückgeben
	long temp = fib(a-1)+fib(a-2);
	fibos.set(a, new Long(temp));
	return temp;
}

Sowas?
Ist jetzt natürlich nur oberflächlich implementiert und könnte noch optimiert werden, aber ist ja auch nur ein Beispiel (und ungetestet).