Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

[C++] Wie die Fibonacci-Folge realisieren?

Werbeanzeige

Nimelrian

Alter Hase

Beiträge: 1 216

Beruf: Softwareentwickler (aktuell Web/Node); Freiberuflicher Google Proxy

  • Private Nachricht senden

31

17.04.2016, 11:32

Zitat von »cojo2015«

Und f gibt dann was zurück?

Zitat von »Nimelrian«

Die n-te Fib.-Zahl
Ich bin kein UserSideGoogleProxy. Und nein, dieses Forum ist kein UserSideGoogleProxyAbstractFactorySingleton.

cojo2015

Alter Hase

  • »cojo2015« ist der Autor dieses Themas

Beiträge: 516

Wohnort: bei mir zu Hause

Beruf: Schüler

  • Private Nachricht senden

32

17.04.2016, 11:48

Irgenwie stehe ich gerade voll auf dem Schlauch :dash: ?(

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/*
    [n=4]

    gerade Zahlen:
        f(2n+1) = f(n)^2 + f(n+1)^2
        f(9) = f(4)^2 + f(5)^2 = 9 + 25 = 34

    ungerade Zahlen:
        f(2n) = f(n+1)^2 - f(n-1)^2
        f(8) = f(5)^2 - f(3)^2 = 25-4 = 21
    */

    unsigned int n = 0;

    cout << "Zahl: ";
    cin >> n;

    cout << "1. Fibonacci-Zahl: " << (n*n)       + (n+1)*(n+1) << endl; // = 41
    cout << "2. Fibonacci-Zahl: " << (n+1)*(n+1) - (n-1)*(n-1) << endl; // = 16

Hab ich was falsch verstanden, weil nciht die Ergebnisse herauskommen, die herauskommen sollen?

marcgfx

Treue Seele

Beiträge: 236

  • Private Nachricht senden

33

17.04.2016, 20:47

für n=201
f(201) = f(100)^2 + f(101)^2

dann musst du f(100) und f(101) berechnen

f(101) = f(50)^2 + f(51)^2
f(51) = f(25)^2 + f(26)^2
f(25) = f(12)^2 + f(13)^2
f(13) = f(6)^2 + f(7)^2
f(7) = f(3)^2 + f(4)^2
f(3) = f(1)^2 + f(2)^2 = 1^2 + 1^2 = 2

ich bin jetzt immer nur eine zahl angegangen.

das kann wie du siehst mit rekursion gelöst werden. du kannst die rekursion abbrechen, sobald du das resultat einer der funktionen weisst. wenn du z.b. f(4) bereits berechnet hast, könntest du den wert einfach aus einer tabelle auslesen.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//pseudo javascript code, für c++ müsst ich zu viel nachschauen
var solved={}//du musst in solved key/value eintragen können

function fibonacci(n){
  if(!solved[n]){
    if(n%2==1){//ungerade zahl
      //wert für n berechnen und in die tabelle eintragen
      solved[n]=sqr(fibonacci(n/2))+sqr(fibonacci(n/2+1);
    }else{//gerade zahl
      ...
    }
  }
  return solved[n];
}
Devader DevLog - Devader spielen

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »marcgfx« (17.04.2016, 23:31)

BlackArtC#

Frischling

Beiträge: 32

  • Private Nachricht senden

34

18.04.2016, 22:29

Wie kann etwas das so einfach aussieht so kompliziert sein <.<

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »BlackArtC#« (18.04.2016, 22:35)

marcgfx

Treue Seele

Beiträge: 236

  • Private Nachricht senden

35

18.04.2016, 23:05

weil es darum geht die geschwindigkeit der berechnung zu optimieren :P
aber ganz ehrlich gesagt ist dies ein eher einfaches problem, mit etwas rekursion. mein pseudocode ist ja praktisch schon die lösung...
am einfachsten ist es, wenn man immer nur die 2 nachfolgenden zahlen im speicher hält. dürfte aber der langsamste weg sein um zu einem ergebnis zu kommen bei grossen zahlen.

vermutlich wäre es auch von hand einfacher so die fibonacci zahl an stelle 1000 zu berechnen ;)
Devader DevLog - Devader spielen

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

36

18.04.2016, 23:46

Zitat von »marcgfx«

weil es darum geht die geschwindigkeit der berechnung zu optimieren

Na dann wurde doch schon eine ordentliche Lösung genannt:
[C++] Wie die Fibonacci-Folge realisieren?
Damit kannst du in konstanter Zeit eine beliebige Zahl der Fibonacci Folge bestimmen. Das ist schneller als alle rekursiven oder iterativen Ansätze. Und selbst wenn du alle Fibonacci Zahlen von 1 bis n bestimmen willst wäre der iterative Ansatz schneller als der rekursive.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

marcgfx

Treue Seele

Beiträge: 236

  • Private Nachricht senden

37

19.04.2016, 01:27

Da hast du recht und evtl. hast du eine besser Antwort für BlackArtC#? Das war mein Erklärungsversuch.

Ich wollte auch nicht sagen, dass das die beste Lösung ist. Es ist bloss diejenige die von cojo2015 versucht wurde und den ich erklären kann. Der Ansatz ist besser als der iterative Ansatz, wenn es darum geht eine einzelne hohe Fibonacci Zahl zu berechnen. Wenn man sowieso alle berechnen muss, dann ist der iterative Ansatz der schnellste.

Die absolute Formel für die Lösung zu verwenden ist als Aufgabe nicht spannend. Ich kann auch die Formel nicht eklären.
Devader DevLog - Devader spielen

BlackArtC#

Frischling

Beiträge: 32

  • Private Nachricht senden

38

19.04.2016, 01:28

Also ich muss sagen ich hänge gerade.

Ich habe einiges Versucht, selbst die "Formel von Binet" will bei mir nicht das richtige Ergebnis liefern.
Also irgendwas ist mit diesen Zahlen nicht in Ordnung -.-

marcgfx

Treue Seele

Beiträge: 236

  • Private Nachricht senden

39

19.04.2016, 02:12

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

<html>
<head>

</head>
<body>
<script>
    //pseudo javascript code, für c++ müsst ich zu viel nachschauen
    var solved={0:0,1:1,2:1}//du musst in solved key/value eintragen können

    function sqr(x){
        return x*x;
    }

    function fibonacci(n,k){
        if(!k) k=0;
        k++;
        if(solved[n]===undefined){
            if(n%2==1){//ungerade zahl
                //wert für n berechnen und in die tabelle eintragen
                var p = ~~(n/2);
                //console.log(">".repeat(k)+n+' from '+(p)+' and '+(p-1))
                solved[n]=sqr(fibonacci(p+1,k))+sqr(fibonacci(p,k));
            }else{//gerade zahl
                var p = ~~(n/2);
                //console.log(">".repeat(k)+n+' from '+(p+1)+' and '+(p-1))
                solved[n]=sqr(fibonacci(p+1,k))-sqr(fibonacci(p-1,k));
            }
        }
        return solved[n];
    }

    for(var i=0;i<10;i++){
        console.log('fib('+i+') is '+fibonacci(i));
    }

    //ab fibonacci 77 stimmt die präzision nicht mehr
    for(var j=10;j<80;j+=10){
        console.log('fib('+j+') is '+fibonacci(j));
    }

</script>

</body>
</html>


sooo... sollte ja schlafen, aber wollte es dann doch schnell probieren. hab länger gehabt als geplant, da ich bemerkt habe, dass es irgendwann nicht mehr stimmt. ab fibonacci(77) ist die präzision nicht mehr ausreichend. kannst das als html seite speichern und im browser öffnen. in der console zeigt es dir die ausgaben an.

von daher... die rekursive methode macht jetzt noch weniger sinn :D ... die folge steigt dermassen schnell an, dass es kaum einen vorteil bringt, weil man vorher an die präzisionsgrenze stösst...

ach und mir ist aufgefallen, dass es für n<3 mit der formel probleme gibt. fib(2) = fib(2)+fib(0) ist zwar korrekt, aber führt zu endlos-schlaufe...
Devader DevLog - Devader spielen

marcgfx

Treue Seele

Beiträge: 236

  • Private Nachricht senden

40

19.04.2016, 02:30

beim zähneputzen ist mir eingefallen, dass ichs ja einfach hochladen kann....
http://data.cyberlympics.com/fib.html
Devader DevLog - Devader spielen

Werbeanzeige

Ähnliche Themen