# Fibonacci Algorithmus



## Guest (8. Nov 2008)

Hi zusammen,

ich habe die Aufgabe einen Algorithmus zu implementieren, der die Fibonacci-Zahl berechnet.
Dabei lautet die Aufgabenstellung:

Sei F(n) die n-te Fibonacci-Zahl. Zur konkreten Berechnung von F(n) zu
einem bekannten n gibt es zwei Algorithmen:
(Algorithmus A)
Man f¨uhrt fibonacci(n) durch. Die Programmroutine fibonacci(k)
bekommt als Eingabevariable k und liefert F(k) zur¨uck. Ihr Ablauf:
• Wenn k = 0, dann F(k) := 0
• Wenn k = 1, dann F(k) := 1
• Wenn k /2 {0, 1}, dann:
– F¨uhre fibonacci(k-1) durch; erhalte F(k − 1)
– F¨uhre fibonacci(k-2) durch; erhalte F(k − 2)
– Berechne F(k) = F(k − 1) + F(k − 2)
• Liefere den Wert F(k) zur¨uck.
(Algorithmus B)
1. Starte mit F(0) = 0, F(1) = 1, k = 0
2. Setze G(k) = (F(k + 1), F(k))
3. Speichere G(k)
4. Berechne F(k + 2) als Summe der beiden Komponenten von G(k)
5. Erh¨ohe k um 1
6. Abbruch für k + 1 = n, sonst zurück zu Schritt 2
(i) Berechne die Anzahl der benötigten Additionen für beide Algorithmen
am Beispiel n = 6.

Meine Implementierung:

```
public int algoA(int n) {
		if (n == 0)
		{
			return 0;
		}
		else if (n == 1)
		{
			return 1;
		}
		else {
			counter++;
			return algoA(n - 1) + algoA(n - 2);
		}
	}

	public int algoB(int n) {
		int k = 0;
		int fK = 0;
		int[] gK = new int[2];
		do {
			gK[0]= k + 1;
			gK[1]=k;
			counter++;
			fK = gK[0] + gK[1];
			k++;
		}
		while (k + 1 < n);
		return fK;
	}
```

Allerdings erhalte ich mit algoA(6) als Ergebnis 8 und mit algoB(6) als Ergebnis 9.
Meine Frage daher: Sind die beiden Algorithmen so korrekt nach der Aufgabenstellung programmiert? Mich verwundert das unterschiedliche Ergebnis von AlgoA und B.


----------



## Landei (8. Nov 2008)

Du musst bei algoB die Werte in deinem Feld "weiterrücken", nicht einfach mit dem Zähler k belegen, also so:
1) [0, 1]
2) [1, 0+1] = [1, 1]
3) [1, 1+1] = [1, 2]
4) [2, 1+3] = [2, 3]
5) [3, 2+3] = [3, 5]
6) [5, 3+5] = [5, 8] <- 8 ist die 6. Fibo-Zahl
...

Aus'm Kopp - keine Gewähr

```
public int algoB(int n) {
  if (n < 2) return n;
  int[] gK = new int[]{0, 1}; 
  for(int k = 2; k <= n; k++) {
     int fK = gK[0] + gK[1]; 
     gK[0] = gK[1];
     gK[1] = fK; 
  }
  return gK[1];
}
```


----------



## Guest (8. Nov 2008)

Vielen Dank für die Antwort. Funktioniert so.


----------



## Unikate (1. Dez 2009)

```
public class Fibonacci {

	public static void main (String[]args){
		
		int x=1;
		int y=1;
		int folge=ergebnis(x,y);
	
		System.out.println(folge);
	}
	
	public static int ergebnis(int x, int y){
		int z;
		
		if (x+y == 1597)
			return x=610;
		else {
			z = x + y;
			System.out.println(x + "," + y);
			return z + ergebnis(x + y,y + z);
		}
	}
		
}
```

Ergebnisse in der Console:
1,1
2,3
5,8
13,21
34,55
89,144
233,377
1596


Ich habe den Algo so gelöst.
Wie kann ich denn die ausgegebenen Zahlen nebeneinander schreiben?
Und hat jemand eine elegentarer lösung für die abbruchbedingung?

gruß+danke
kate


----------



## SlaterB (1. Dez 2009)

System.out.print statt  System.out.println

-----

return x=610;

welchen Sinn hat es hier, x noch schnell einen Wert zuzuweisen?

-----

die Abbruchbedingung ist n, die Stufe, 6 oder so, übergib doch n mit als Parameter

was ist denn


----------



## Unikate (1. Dez 2009)

danke für den print tip! kannte ich noch nicht. hab programmieren erst seit 2 monaten.
ich wusste nicht wie ich die abbruchbedingung definieren sollte, da der algo ja unendlich sein kann.
hab ich einfach einen stoppwert gewählt^^
haben heut erst rekursion gelernt. deswegen bin ich mit der abbruchbedingung noch nicht so fit 
was meinst du mit "abbruchbedingung stufe 6"?

gruß


----------



## SlaterB (1. Dez 2009)

du prüfst doch ob x + y irgendwas ist, == 1597, und nun sollst was anderes prüfen, == 6, recht ähnlich

aber x + y sind nicht an dieser Stelle 6 sondern was anderes, du musst mehr Information übergeben,
es ist ja erlaubt, beliebig viele Parameter zu übergeben, also auch einen der an dieser Stelle 6 ist,


----------



## Unikate (1. Dez 2009)

genau, ich will dass er bei einer bestimmten algo zahl (z.b. 610) die ganze sache einfach abbricht.
also wenn x+y==610, dann brich ab. und dann muss ich x 6 zuweisen??
sorry dass ich es nich direkt raffe


----------



## SlaterB (1. Dez 2009)

1. 1,1
2. 2,3
3. 5,8
4. 13,21
5. 34,55
6. 89,144
7. 233,377

ob nun 6 oder 7 ist ja egal, jede Ausgabe ist eine Stufe, einfach einen zusätzlichen Parameter,
mit x und y hat das absolut nix zu tun

 public static int ergebnis(int x, int y, int n){


----------



## Unikate (1. Dez 2009)

```
public static int ergebnis(int x, int y, int n){
		int z;
		
		if (n == 10)
			return n;
		else {
			z = x + y;
			System.out.print(x + "," + y + ",");
			return z + ergebnis(x + y,y + z, n+1);
		}
	}
		
}
```


----------



## Unikate (1. Dez 2009)

ist das immer so das prinzip, dass man in einer rekursion "stufen" hat und sie mit n hochzählt?
ne oder?nur wenn ich was aufzähle?
weil wir auch eine aufgabe hatte, in der wir die quersumme berechnen mussten.
da war die abbruchbedingung :

if (x<=9)
return x;

=> also wenn x kleiner gleich 9, so gebe direkt x aus und wenn nicht mache es solange bis x<=0 wird!


----------



## SlaterB (1. Dez 2009)

Rekursion brauch man hier gar nicht, ne Schleife ginge auch,
und return n; ist ganz schlecht, n ist nur für den Abbruch zuständig, doch nicht plötzlich ein Wert


----------



## Unikate (1. Dez 2009)

aaaaaaaa verwirrung. ja wir müssen das rekusriv schreiben. als übung halt.
also muss die abbruchbedingung dann immer einen wert annehmen. hmmmmmmmm irgendeinen beliebigen oder der sich aus den zahlen ableiten lässt? zielloooooooos!


----------



## Unikate (1. Dez 2009)

```
public static int ergebnis(int x, int y, int n){
		int z;
		
		if (n == 12)			//jedes n ist eine stelle z.b. 5 und 8
			return x = -17711;
		else {
			z = x + y;
			System.out.print(x + "," + y + ",");
			return z + ergebnis(x + y,y + z, n+1);
		}
	}
```

Habe es nun so gelöst.Ergebnis:

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28656

problem ist nur, dass wenn man die abbruchbedingung ändert, müsste man den x wert neu ausrechnen.
hab ihn durch den debugger einfach berechnet!


----------



## SlaterB (1. Dez 2009)

was genau bei dieser Rekursion rauskommen soll, sehe ich kaum durch,
aber du solltest auf keinen Fall irgendwelche Werte manuell berechnen, gib das aktuelle x, y oder z zurück, irgendwas davon muss doch gesucht sein,
wenn du einen dieser Werte wieder abziehst, dann kommt das x, y oder z des vorherigen Durchgangs raus, das bedeutet dass du damals schon hättest abbrechen müssen oder ähnliches


```
public class Test {
	public static void main(String[] args) {

		int x = 0;
		int y = 1;
		int folge = ergebnis(x, y, 1);

		System.out.println("\n" + folge);
	}

	public static int ergebnis(int x, int y, int n) {
		System.out.println(x + "," + y + ",");
		if (n == 11) {
			return x;
		}
		int z = x + y;
		return z + ergebnis(z, y + z, n + 1);
	}

}
```


----------



## partsch (1. Dez 2009)

Falls du noch eine Lösung suchst
die rekursive hatte ich mal zur Hausübung ist deiner Angabe sehr ähnlich


```
import java.util.Scanner;
public class Fibonacci {
	
	
	public static void main(String...args){
		countFibo();
	}
	
	public static void countFibo(){
		Scanner sc = new Scanner(System.in);
		System.out.print("Bitte geben sie an bis wohin die Fibonaccizahlen aufgelistet werden sollen: ");
		int toCount = sc.nextInt();
		System.out.println("");
		nextFibo(0, 1, toCount);
	}
	
	private static int nextFibo(int numb_1, int numb_2, int n){
		if(numb_1>numb_2){
			numb_2 ^= (numb_1^=numb_2);
			numb_1 ^= numb_2;
		}
		System.out.print(numb_1+", ");
		if(numb_2 < n){
			return nextFibo(numb_2, (numb_1+numb_2), n);
		}
                if(numb_2<= n)
		        System.out.print(numb_2);
		return n;
	}
}
```


----------



## Unikate (2. Dez 2009)

wenn ich als abbruchbedingung definiere:

if (n == 12)	
return x;

Ergebnis:
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,*75024
*

:-/

guten mooorgen


----------



## SlaterB (2. Dez 2009)

bei deinem Programm vielleicht, nicht bei meinem,
aber selbst 75024 ist nicht schlecht, ist irgendeine Zahl aus der Fibonacci-Reihe, man muss nur alle Parameter und n so wählen, dass man zufrieden ist,

das merkwürdige Aufaddieren beim return kann man sich auch sparen:
return  ergebnis(z, y + z, n + 1);
schon siehts wieder etwas anders aus, Ergebnis ist immer noch eine der Zahlen aus der Reihe, aber eine andere kleinere

was die Methode ausrechnen sollte/ derzeit tut kann ich wie gesagt eh nicht nachvollziehen,
da aber immer nur x + y addiert wird, kommt sicherlich überall was Fibonacci-mäßiges raus


----------



## ARadauer (2. Dez 2009)

Unikate hat gesagt.:


> ```
> if (x+y == 1597)
> return x=610;
> ```


hab mir jetzt nicht alles angesehen... aber was soll das sein? 


```
public static int fibu(int f){
      if(f<2)
         return f;      
      return fibu(f-2)+fibu(f-2);
   }
```

Fibunacci... mehr ist das nicht...

Natürlich ist der Algo praktisch nicht anzuwenden da man extrem lange Laufzeiten hat... 
besser ist, wenn man das Ergebnis chached...


```
public static HashMap<Integer, Integer> fibuNumbers = new HashMap<Integer, Integer>();
   public static int fastFibu(int f){
      if(f<2){
         return f;
      }else{
         if(fibuNumbers.containsKey(f)){
            return fibuNumbers.get(f);
         }else{
            int newF = fastFibu(f-1)+fastFibu(f-2);
            fibuNumbers.put(f, newF);
            return newF;
         }
      }
   }
```


----------



## SlaterB (2. Dez 2009)

ARadauer hat gesagt.:


> ```
> public static int fibu(int f){
> if(f<2)
> return f;
> ...


so kurz, und doch falsch 

fibu(5) = 4


----------



## lumo (2. Dez 2009)

hab das mit fibonacci etwas anderst gelöst.
nach etwas testen ists mir zu nervig geworden, dass das immer so lange dauert, ein paar fibs zu berechnen... hab darum eine liste eingeführ und siehe da... es rauscht nur so dahin. (in null komma nix)

wusstet ihr dass die 200erste fib zahl 3721511182311577122 ist? 

als kleines zuckerl hab ich noch die zeckendorf-zerlegung dazugemacht (also zerlegung einer zahl in fibonacci-zahlen)


```
import java.util.LinkedList;
import java.util.List;

public class Zeckendorf {
	List<Long> zeck = new LinkedList<Long>();
	List<Long> fibs = new LinkedList<Long>();

	public Zeckendorf() {
		fibs.add(1L); // fib(0)
		fibs.add(1L); // fib(1)
	}

	public void zeck(Long n) {
		int i = new Integer(Long.toString(n));
		fibonacci(i);
		Long z = n;
		while (z > 0) {
			Long small = getSmaller(z);
			zeck.add(0, small);
			z = z - small;
		}
	}

	public void printLongZeck() {
		for (int i = zeck.size() - 1; i >= 0; i--) {
			if (i == zeck.size() - 1) {
				System.out.print("[" + zeck.get(i) + ", ");
			} else if (i == 0) {
				System.out.print(zeck.get(i) + "]");
			} else {
				System.out.print(zeck.get(i) + ", ");
			}
		}
		System.out.println();
	}

	public Long getSmaller(Long n) {
		int i = 1;
		while (fibs.get(i) < n) {
			i++;
		}
		return fibs.get(i - 1);
	}

	public static void main(String[] args) {

		Zeckendorf z = new Zeckendorf();
		long start = System.currentTimeMillis();
		System.out.println("the 200th Fibonacci number is: "
				+ z.fibonacci(200));
		long stopp = System.currentTimeMillis();
		System.out.println(String.format(
				"calculating 200th Fibonacci took %dms", stopp - start));
		start = System.currentTimeMillis();
		Long num = 1662500L;
		z.zeck(num);
		stopp = System.currentTimeMillis();
		System.out.println(String.format(
				"calculating Zeckendorf(%d) took %dms", num, stopp - start));
		System.out.print("Zeckendorf = ");
		z.printLongZeck();
	}

	public Long fibonacci(int n) {
		// {0,1} size = 2 - list at start
		if (n > fibs.size() - 1) {
			Long newFib = 0L;
			while (n >= fibs.size()) {
				newFib = fibs.get(fibs.size() - 1) + fibs.get(fibs.size() - 2);
				fibs.add(newFib);
			}
			return newFib;
		} else {
			if (n >= 0) {
				// the fib is already in the list
				return fibs.get(n);
			} else {
				return 0L;
			}
		}
	}
}
```

falls jemand noch verbesserungsvorschläge hat... ich bin dafür offen

BTW: bis jetzt gibts ne einschränkung auf int (als index der liste... -> ist die höchste int zahl die höchste fibonacci zahl, die mein algorithmus errechnet.) und für zeckendorf bedeutet das die zahl Long num = 1662500L; wie im codebeispiel gewählt


----------



## Unikate (2. Dez 2009)

ist das nicht ein bisschen zu komplex?programmieren hat doch zum ziel, so wenig wie möglich zeilen niederzuschreiben oder nicht?


----------



## lumo (2. Dez 2009)

ne, eigentlich nicht.
eigentlich ist das ziel (zumindest meines) dass die programme möglichst schnell laufen. (und speicherfreundlich sind)
note: rekursion frisst meist mehr speicher als iterative funktionen


----------

