Fibonacci-Linear und Rekursiv

[medicus]

Hallo Leute.Ich hab grad angefangen mit Java und hab als Übungsaufgabe folgendes Problem bekommen.
Vielleicht könnt ihr mir ja helfen und weil ich echt überfordet bin

Aufgabe:
Implementieren Sie eine rekursive Methode, die die n-te Fibonacci-Zahl in linearer Zeit berechnet.
Gestalten Sie die Rekursion so, dass zusätzlich zu anderen Parametern die beiden
letzten Fibonacci-Zahlen als Parameter übergeben werden. Wertzuweisungen sollen in der
rekursiven Methode nicht verwendet werden. Testen Sie die Methode mit einer Anwendung.
Diese Anwendung muss eine ausführbare Klasse sein, d.h. eine Methode
public static void main (String[] args)
enthalten.


Lösungsvorschläge?

Im internet bin ich auf folgender Lösung gestoßen:


Rekursive Fakultät

int factorial(int n) {
if(n<=1) return 1;
return n*factorial(n-1);
}

Endrekursion mittels Hilfsfunktion

int g_factorial(int n, int fac) {
if (n<=1) return fac;
return g_factorial(n-1, fac*n);
} int factorial(int n) {
return g_factorial(n, 1);
}

Durch Einführen der Hilfsfunktion g_factorial wird
die nachträgliche Multiplikation vermeiden.
=> Die Rekursion ist nun endrekursiv.



Vielen lieben Dank für eure Hilfe

Anna

 

[Marco13]

Hmja ... die endrekursive Darstellung der Fakultät und ein linearer Fibinacci haben IMHO erstmal nicht so viel miteinander zu tun... Du kennst vermutlich die Definition der Fibonacci-Zahlen, und hast vermutlich auch schon eine rekursive Implementierung ergooglet... Hast du eine Idee, was du jetzt machen musst?

 

[Landei]

Eine naive rekursive Implementierung von Fibonacci-Zahlen hat eine grottenschlechte Performance, der Trick ist, in der einen oder anderen Form zwei benachbarte Fibonacci-Zahlen mitzuschleifen, etwa so:

public int fibo(int n) {
   fiboHelper(0, 1, n);
}

public int fiboHelper(int a, int b, int n) {
  return n == 0 ? a : fiboHelper(b, a+b, n-1);
}

Es gibt noch wesentlich schnellere Versionen (z.B. basierend auf Formeln, die aus fibo(n) und fibo(n+1) die Werte fibo(2n) und fibo(2n+1) berechnen)

 

[medicus]

Hallöchen.Ich bins wieder

Ich hab eure Ratschläge beherzt-Danke <3

Ich weiß wie die Fibonacci Zahlen gebildet werden:

Bsb:

f(O)=0
f(1)=f(0)+f(1)=1
f(2)=f(0)+f(1)=1

...
f(n)=f(n-2)+f(n-1)



Leider kann ich die geforderte Aufgabe immer noch nicht lösen


Ich würd mich ganz dolllll freuen wenn ihr mir hilft

danke und kussis

anna

 

[Marco13]

Ich würd' mich ganz doll freuen, wenn du um Hilfe für eine Aufgabe bitten würdest, die schon gelöst ist

:joke:

 

[medicus]

Hi,

Ist die Aufgabe echt gelöst ???

Dies ist ja ein Forum für Anfänger so wie ich
ES tut mir leid wenn ich so dumm nachhake.Ich bin absolute Programmierenversagerin
Deswegen kann ich nicht sehen wie die Aufgabe gelöst sein soll?


Hilft mir bütte

LG
anna

 

[kay73]

Leider kann ich die geforderte Aufgabe immer noch nicht lösen

Der Quellcode dazu steht doch da obne.

Es gibt noch wesentlich schnellere Versionen (z.B. basierend auf Formeln, die aus fibo(n) und fibo(n+1) die Werte fibo(2n) und fibo(2n+1) berechnen)

Es geht auch in O(1) -> Da will aber der Dozent dann auch den Beweis sehen. ;-)

 

[medicus]

ALso erstmal danke an euch alle


Die Aufgabe lautete ja:
Implementieren Sie eine rekursive Methode, die die n-te Fibonacci-Zahl in linearer Zeit berechnet.
Gestalten Sie die Rekursion so, dass zusätzlich zu anderen Parametern die beiden
letzten Fibonacci-Zahlen als Parameter übergeben werden. Wertzuweisungen sollen in der
rekursiven Methode nicht verwendet werden. Testen Sie die Methode mit einer Anwendung.
Diese Anwendung muss eine ausführbare Klasse sein, d.h. eine Methode
public static void main (String[] args) enthalten.



Ich hab herausgefunden, dass linear und endrekusiv dasselbe meint.
In der Methode fiboHelper werden die beiden letzten Fibonacci zahlen übergeben
Ich habe mit einer Anwendung getestet und hab dazu a=1, b=2 und n=8 gewählt.
Zusätzlich hab ich den code so kommentiert wie ich versteh
Leider funktioniert das Programm immer noch nicht ;(

public class Fibijo {

public static void main (String[] args){

// Ich teste die Aufgabe mit folgenden drei Werten
	int n=8;
	int a=1;
	int b=2;

// Methode int Fibi wird dekleriert und bekommt int n übergeben	
public int Fibi(int n) {
//fiboHelper bekommt 0, 1, und n übergeben
   fiboHelper(0, 1, n);
}

// methode fiboHelper wird dekleriert und bekomm a, b und n übergeben
public int fiboHelper(int a, int b, int n) {
// Wenn n 0  ist , gibt die methode 0 zurück ansonsten wird (2,2+1,8-1) übergeben diesen Ausdruck versteh ich nicht ganz
return n == 0 ? a : fiboHelper(b, a+b, n-1);
}
}
}

Save me guys
anna

 

[kay73]

Ich hab herausgefunden, dass linear und endrekusiv dasselbe meint.

Erzähl das bloß nicht deinem Dozenten... Weisst Du auch genau, was man eigentlich von Dir will? Dass in der Aufgabe mit "linear" eine Laufzeit gemeint ist? Warum diese Rekursion lineare Laufzeit hat im Gegensatz zu sowas wie

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

?

public class Fibonacci {

	public int fibonacci(int n) {
		return fiboHelper(0, 1, n);
	}

	private int fiboHelper(int a, int b, int n) {
		return n == 0 ? a : fiboHelper(b, a + b, n - 1);
	}

	public static void main(String[] args) {

		final Fibonacci f = new Fibonacci();
		System.out.println(f.fibonacci(8));
	}
}

 

[medicus]

Hi Kay73.

Echt dickes Dankeschön für dein Hilfe <3

So wie es verstanden habe bedient man sich dann der O-Notation um die Laufzeitlänge herauszufinden. (Landauysmbole)

wobei:
O(n) bedeutet lineares Wachstum
Sei a element aus O(n), so wächst a ungefähr auf das Doppelte, wenn sich n verdoppelt.

bei dieser Rekursion ist dies ja nicht der fall
fib(n)=fib(n-1)+fib(n-2)

Beispiel:
f(1)=1
f(2)=1
f(3)=2
f(4)=3

Ich versuch mir das grad noch am Java-Code klar zu machen in dem ich die Laufzeit bestimme
Wie geh ich da am besten ran, wenn ich zu deinem Code die Laufzeit berechnen will


Ps: Danke.Hasst mir schon echt sehr viel weiter geholfen.So langsma wirds

LG
anna

 

[Landei]

Hier eine schnelle Implementierung, allerdings mit BigIntegern:

   //Geklaut von code.google.com/p/birpn
   private static BigInteger fib(BigInteger n) {
        if (n.signum() < 0) {
            throw new ArithmeticException("Argument must be non-negative.");
        }
        if(n.compareTo(BigInteger.ONE) <= 0) {
            return n;
        }
        BigInteger x = BigInteger.ONE;
        BigInteger y = BigInteger.ZERO;
        for(int k = n.bitLength() - 2; k >= 0; k--) {
            BigInteger xx = x.multiply(x);
            x = xx.add(x.multiply(y).shiftLeft(1));
            y = xx.add(y.multiply(y));
            if(n.testBit(k)) {
                BigInteger temp = x;
                x = x.add(y);
                y = temp;
            }
        }
        return x;
    }

 

[bygones]

Hier eine schnelle Implementierung, allerdings mit BigIntegern:

die TE hat noch nicht wirklich die O notation verstanden - meinst du der "perfomante" code hilft dann weiter ?

lieber helfen als sich mit noch performanteren code hier gegenseitig überbieten.

my 2 cents

 

[Landei]

Ich habe auch keine Ahnung, welches O mein Code hat (ich würde mal spontan auf O(n log(n)) tippen). Aber was soll verkehrt daran sein, unterschiedliche Implementierungen vorzustellen?

 

[Geeeee]

Sollte passen mit deiner Laufzeit.

Etwas ot:
Hab mich vor einem Monat ca. mal etwas mehr mit Fib und Java beschäftigt: Is doof mit BigInteger, da immer wieder neue Objekte rausgehauen werden. Ab ca. einer Million wird es sehr übel. Muss man sich Alternativen suchen, wenn man es richtig angehen will.
Mal ein wenig Lesestoff für effiziente Algorithmen:
Das Fibonacci number
basierend auf dem:
repeated squaring
(stelle gerade fest, dass bei mir die Links zur Zeit nicht funktionieren. Ist aber auch im GoogleCache nachzulesen)

 

[bygones]

Ich habe auch keine Ahnung, welches O mein Code hat (ich würde mal spontan auf O(n log(n)) tippen). Aber was soll verkehrt daran sein, unterschiedliche Implementierungen vorzustellen?

dass es meiner ansicht nach sinniger waere eine Loesung vorzustellen, die der/die TE versteht...