Fibonacci Zahlen dynamische Programmierung

baker333

Bekanntes Mitglied
Servus,

ich habe ein Verständnisproblem bei der dynamischen Programmierung der Fibonacci Folge. Hier mein Code aus dem Skript:

Java:
private long [] berechneteFiboWerte;

//Fibonacci Zahlen mittels dynamischer Programmierung
    public long fibDynProg (int n) {
        if (n < 0 ) {
            throw new IllegalArgumentException();   
        }
    
        //erstellt ein neues Array für bereits berechnete Werte
        berechneteFiboWerte = new long[n +1];
        //ruft die Methode,die unten implementiert wird auf
        fibRekursivDyn(n);
        
        //gibt den uns interessierenden Wert aus
        return berechneteFiboWerte[n];
    
    }
    
    private long fibRekursivDyn(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        
        if(berechneteFiboWerte[n] != 0) {
            
            return berechneteFiboWerte[n];
        }
            return berechneteFiboWerte[n] =
                    fibRekursivDyn(n-1) + fibRekursivDyn (n-2);
        }

Ich verstehe, dass ich ein Array erstelle und dort die Werte speichere. Aber ich verstehe die erste "return" Anweisung in der Methode fibRekursivDyn nicht. Wenn der Wert an der Stelle n ungleich 0 ist warum gebe ich ihn zurück? Irgendwie stehe ich auf dem Schlauch :p Ist das einfach die Befüllung des Arrays?

Danke
 

baker333

Bekanntes Mitglied
Im Skript scheint ein Fehler zu sein:

Java:
private long fibRekursivDyn(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

es müsste eigentlich return n heißen. Mit return 1 berechnet er quasi die Fibonacci Zahl n+1. Da frage ich mich natürlich warum?
 
K

kneitzel

Gast
Nein, da ist die Frage, wie Du die Fibonacci Folge definierst.

Üblich ist;
1, 1, 2, 3, 5, ....

Manchmal wird aber eine 0 vorangestellt [1]. Das ist aber eher unüblich und habe ich in der Praxis noch nicht gesehen.

Also für 0 und 1 wird 1 zurück gegeben. Dann immer die Summe der beiden Vorgänger. Und so die optionale 0 nicht erwartet wird, ist der Code so in meinen Augen korrekt.

Referenzen:
[1] https://de.wikipedia.org/wiki/Fibonacci-Folge
 

baker333

Bekanntes Mitglied
Nunja, ich hab es mal ausprobiert:

wenn ich es so berechne:

Java:
private long fibRekursivDyn(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

kriege ich die Fibonacci Zahl für n+1.

Java:
private long fibRekursivDyn(int n) {
        if (n == 0 || n == 1) {
            return n;
        }

kriege ich die Fibonacci Zahl für n.

Wenn ich die Definition der Fibonacci Zahl ändere:

Java:
private long fibRekursivDyn(int n) {
        if (n == 1 || n == 2) {
            
            berechneteFiboWerte[n] = 1;
            
            return 1;
        }

dann erhalte ich mit return 1 auch den richtigen Wert.
 

mihe7

Top Contributor
Nunja, ich hab es mal ausprobiert:
Im ersten Fall berechnest Du die Fibonacci-Zahl von n+1, weil Du für n==0 den Wert 1 zurückgibst. Der zweite Fall entspricht der Fibonacci-Folge mit 0 als ersten Wert (für n==0 gibst Du den Wert 0 zurück). Der dritte Fall entspricht der üblichen Fibonacci-Folge: für n==1 und n==2 gibst Du 1 zurück.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
jhCDtGVjcZGcfzug Fibonacci Zahlen rekursiv und iterativ Java Basics - Anfänger-Themen 21
S Fibonacci Zahlen rekursiv Java Basics - Anfänger-Themen 1
A Fibonacci Zahlen Java Basics - Anfänger-Themen 1
K Fibonacci Zahlen Java Basics - Anfänger-Themen 3
B Fibonacci Zahlen rekursiv Array Java Basics - Anfänger-Themen 12
J Fibonacci Zahlen berechnen Java Basics - Anfänger-Themen 3
C Fibonacci Zahlen Java Basics - Anfänger-Themen 7
J Ausgabe der fibonacci Zahlen Java Basics - Anfänger-Themen 4
0 Fibonacci Zahlen seeeehr schnell berechnen Java Basics - Anfänger-Themen 9
K Fibonacci Zahlen Java Basics - Anfänger-Themen 2
K Programmieren von den ersten 70 Fibonacci-Zahlen Java Basics - Anfänger-Themen 2
G Iterativer Algorithmus zur Berechnung der Fibonacci Zahlen Java Basics - Anfänger-Themen 1
P Fibonacci-Zahlen Java Basics - Anfänger-Themen 6
S Abwandlung der Fibonacci Folge Java Basics - Anfänger-Themen 3
T Fibonacci mit einer Hilfsmethode berechnen Java Basics - Anfänger-Themen 10
123456789sssssaaaa Which is the best way to Print Fibonacci Series in Java? Java Basics - Anfänger-Themen 3
J Fibonacci-Reihe Java Basics - Anfänger-Themen 12
G Fibonacci Zahlenreihe Fehler Java Basics - Anfänger-Themen 4
D Fibonacci overflow integer Java Basics - Anfänger-Themen 8
N Dynamisches Programmieren/Fibonacci Java Basics - Anfänger-Themen 1
V Fibonacci Folge Java Basics - Anfänger-Themen 4
M Methoden Fibonacci-Folge Java Basics - Anfänger-Themen 6
J Fibonacci -Folge rekursiv berechnen Java Basics - Anfänger-Themen 18
P Fibonacci -Verallgemeintert Java Basics - Anfänger-Themen 2
K Methoden Fibonacci in Array mit rekursiver Methoden Java Basics - Anfänger-Themen 19
M Fibonacci rekursiv mittels Cache Java Basics - Anfänger-Themen 17
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
M Fibonacci-Folge mit while-Schleife Java Basics - Anfänger-Themen 4
P fibonacci - do while Statement Logik Fehler Java Basics - Anfänger-Themen 5
A Fibonacci-numbers Java Basics - Anfänger-Themen 9
K Rekursion Fibonacci Java Basics - Anfänger-Themen 3
Z Fibonacci rekursiv meine Erklärung stimmt so? Java Basics - Anfänger-Themen 2
Z Fibonacci Array Erklärung Java Basics - Anfänger-Themen 5
A Gerade Terme der Fibonacci-Folge aufsummieren Java Basics - Anfänger-Themen 12
M Fibonacci, Fakultaet, GGT Java Basics - Anfänger-Themen 9
S Fibonacci Folge Java Basics - Anfänger-Themen 34
D Fibonacci Java Basics - Anfänger-Themen 11
M Fibonacci-Linear und Rekursiv Java Basics - Anfänger-Themen 14
W Fibonacci Zahlenberechnung Java Basics - Anfänger-Themen 9
X Fibonacci mit durchschnittlicher Zeit Java Basics - Anfänger-Themen 5
I Fibonacci-Folge , direkter Weg. Java Basics - Anfänger-Themen 5
G Fibonacci Algorithmus Java Basics - Anfänger-Themen 22
S Fibonacci Rückrechnung! Java Basics - Anfänger-Themen 5
G fibonacci was stimmt an meinem code nicht? Java Basics - Anfänger-Themen 2
S Fibonacci Zahlenvergeich Java Basics - Anfänger-Themen 6
onlyxlia Anzahl Random Zahlen mit Scanner abfragen und in Array speichern Java Basics - Anfänger-Themen 10
Ü Java Array - Buchstaben als Zahlen ausgeben Java Basics - Anfänger-Themen 22
P Aus Text Datei nur Zahlen übernehmen Java Basics - Anfänger-Themen 13
K Warum werden immer noch doppelte Zahlen ausgegeben ? Java Basics - Anfänger-Themen 13
M negative Zahlen bei Intervallen Java Basics - Anfänger-Themen 10
XWing Doppelte Zahlen im Array Java Basics - Anfänger-Themen 8
M 3 Zahlen miteinander vergleichen Java Basics - Anfänger-Themen 18
J Taschenrechner mit mehr als 2 Zahlen. Java Basics - Anfänger-Themen 18
O Zahlen aus einem char-array per char + Zeichen addieren Java Basics - Anfänger-Themen 2
B Alle Zahlen finden, die 3 bestimmte Ziffern enthalten? Java Basics - Anfänger-Themen 9
K Java gleicher Wert von Zahlen? Java Basics - Anfänger-Themen 5
I aus 2 random zahlen soll nur die ungerade summe der beiden genommen werden. Java Basics - Anfänger-Themen 13
J Operatoren Zahlen addieren Java Basics - Anfänger-Themen 13
B Threads Counter mit ungeraden Zahlen Java Basics - Anfänger-Themen 32
JavaBeginner22 Java 2 Zufalls zahlen generieren. Java Basics - Anfänger-Themen 11
X Wie kann man ein Regex erstellen, die 8-Bit-Binär-Zahlen darstellen. Java Basics - Anfänger-Themen 1
M Stream mit den ersten n natürlichen Zahlen Java Basics - Anfänger-Themen 4
D Größtes Palindrom Produkt aus zwei dreistelligen Zahlen Java Basics - Anfänger-Themen 60
T Methode, die prüft ob in einem Int-Array maximal 2 Zahlen enthalten sind, die größer als ihr Vorgänger sind Java Basics - Anfänger-Themen 5
sserio Befreundete Zahlen Java Basics - Anfänger-Themen 7
AhmadSlack Verzweigungen zahlen multiplizieren Java Basics - Anfänger-Themen 4
padde479 Array Multiplikation der ersten n Zahlen Java Basics - Anfänger-Themen 7
U Lotto-Zahlen App Java Basics - Anfänger-Themen 34
berserkerdq2 Wie würde man einen regulären Ausdruck in Java schreiben, der prüft, dass zwei bestimtme Zahlen nicht nebeneinadner sind? Java Basics - Anfänger-Themen 3
H Arrays: Größten Zahlen Unterschied herausfinden Java Basics - Anfänger-Themen 20
bluetrix Programmieren eines Bots für Zahlen-Brettspiel Java Basics - Anfänger-Themen 9
J Zahlen bis zu einem bestimmten Grenzwert ausgeben Java Basics - Anfänger-Themen 11
00111010101 Objektorientiertes Programmieren mit Vererbung (Zahlen in Array verschwinden) Java Basics - Anfänger-Themen 3
P Zweidimensionales Array als Tabelle mit befüllten Zahlen Java Basics - Anfänger-Themen 10
W Wie ziehe ich von einer bestimmten Zahl, Zahlen ab, bis mein Ergebnis null beträgt? Java Basics - Anfänger-Themen 10
emx-zee Erste Schritte NullPointerException, Array mit zufälligen Zahlen füllen Java Basics - Anfänger-Themen 2
W Bestimmte Zahlen bei Math.random ausschließen? Java Basics - Anfänger-Themen 31
K Erste Schritte "Taschenrechner" zeigt keine Komma Zahlen an. Java Basics - Anfänger-Themen 8
P Drei Zahlen eines Würfelspiels auswerten Java Basics - Anfänger-Themen 7
H Häufigkeit von Zahlen ermitteln Java Basics - Anfänger-Themen 23
sashady Zahlen rekursiv zerlegen und Ziffern addieren Java Basics - Anfänger-Themen 38
H Zahlen kürzen Java Basics - Anfänger-Themen 2
ansystin Teilerfremde Zahlen ausgeben + Zahlenausgabe speichern Java Basics - Anfänger-Themen 3
B Häufigkeit einzelner Zahlen in einem Array Java Basics - Anfänger-Themen 6
nevel Programm für die Summer der Zahlen 1- 1ß Java Basics - Anfänger-Themen 12
H Eingegebene Zahlen mit Array ausgeben Java Basics - Anfänger-Themen 18
I 12 Spalten von jeweils 30 Zahlen in Konsole ausgeben Java Basics - Anfänger-Themen 6
R Array mit Unter- und Obergrenze ganze Zahlen dazwischen erscheinen nicht Java Basics - Anfänger-Themen 1
OZAN86 For Schleife von 1-50 die Zahlen werden durch ein Komma getrennt Java Basics - Anfänger-Themen 10
Bademeister007 Operatoren Alle Zahlen einer ArrayList die durch 5 teilbar ist Java Basics - Anfänger-Themen 2
mhmt_03 dafür sorgen, dass im JTextfield nur zahlen eingebbar sind Java Basics - Anfänger-Themen 9
Ianatrix Zahlen von a bis b berechnen Java Basics - Anfänger-Themen 7
P Wie kann ich die Zahlen dieses Arrays dividieren? Java Basics - Anfänger-Themen 2
P Nutzer entscheiden lassen, wie viele Zahlen dieser in ein Array eingeben möchte. Java Basics - Anfänger-Themen 6
T Bestimmte Zahlen ausgeben mit einer whilfe Schleife Java Basics - Anfänger-Themen 21
H Alle Geraden zahlen bis 10 ausgeben Java Basics - Anfänger-Themen 11
java3690 Liste mit zufälligen zahlen füllen Java Basics - Anfänger-Themen 27
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
M Regex nur Zahlen und Punkt zulassen, Keine Eingabe(Leeres TextFeld) nicht zulassen Java Basics - Anfänger-Themen 6
L Mit Zahlen im String rechnen Java Basics - Anfänger-Themen 19

Ähnliche Java Themen

Neue Themen


Oben