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

Tobiking

1x Rätselkönig

Beiträge: 1 231

  • Private Nachricht senden

21

13.04.2016, 09:59

Zitat von »Nimelrian«


Am Ende würde man ja eine Funktion fibonacci(n) haben und die sollte dann meines Erachtens die n-te Fib.-Zahl liefern.

Damit verfehlst du aber die Aufgabenstellung. Mathematisch (informal) formuliert geht es um die Menge {x | x = fibonacci(n) ^ x < Eingabe}. Dein fibonacci(n) kommt also vor, ist aber nur ein Teil von dem was gewünscht ist.

marcgfx

Treue Seele

Beiträge: 236

  • Private Nachricht senden

22

13.04.2016, 10:58

Ach ja Fibonacci... da hab ich mal in einer langweiligen Unterrichtsstunde gedacht ich hätte ne neue Formel rausgefunden. Bin über Aufzeichnen auf einen mir bis dahin unbekannten Zusammenhang gekommen.

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

//position:
0,1,2,3,4,5,6, 7, 8, 9,10
//wert:
0,1,1,2,3,5,8,13,21,34,55

//für n%2==1, n integer
f(n) = f(n/2+1)^2 + f(n/2-1)^2

//z.B. 
f(9) = f(5)^2 + f(4)^2 = 25 + 9 = 34

//Ich weiss nicht mehr was ich für die geraden für eine Lösung hatte, aber folgendes würde gehen:
f(n) = f(n+1)-f(n-1)

//z.B.
f(8) = f(9)-f(7) = f(5)^2+f(4)^2-(f(4)^2+f(3)^2) = f(5)^2 - f(3)^2 = 25 - 4 = 21;

//hmmm... also für gerade, n%2==0 :
f(n) = f(n/2+1)^2 - f(n/2-1)^2

//mit fallunterscheidung gehts also...
f(8) = f(5)^2 - f(3)^2 = 25 - 4 = 21
f(9) = f(5)^2 + f(4)^2 = 25 + 9 = 34

f(17) = f(9)^2 + f(8)^2 = 34*34 + 21*21 = 1597

Der Beweis wird als Aufgabe für den Leser überlassen :D


edit: ich musste eben alle Formeln korrigieren, weil ich zu blöd bin zu wissen, dass Fibonacci bei 0=0 anfängt und nicht bei 0 = 1.... argh
Devader DevLog - Devader spielen

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »marcgfx« (13.04.2016, 12:25)

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

23

13.04.2016, 12:03

Zitat von »marcgfx«

edit: ich musste eben alle Formeln korrigieren, weil ich zu blöd bin zu wissen, dass Fibonacci bei 0=0 anfängt und nicht bei 0 = 1.... argh

Es gibt da durchaus verschiedene Definitionen der Fibonacci Folge.
f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 2
oder aber auch
f(0) = 1
f(1) = 1
f(2) = 2
„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

24

13.04.2016, 12:24

Gut zu wissen :)
Die Formel ist jedenfalls schöner wenn f(0)=0 von daher war es kein totaler Verlust. War ganz witzig noch mal an meinen vermeintlichen Nobelpreis zu denken.
Devader DevLog - Devader spielen

Checkmateing

Community-Fossil

Beiträge: 2 218

  • Private Nachricht senden

25

13.04.2016, 16:08

Zitat von »marcgfx«

an meinen vermeintlichen Nobelpreis zu denken.

Für Mathematik, genau und im Buddhismus gibt es einen Gott...

Also du sagst für Fibonacci gelte: §f\left(n\right)=\begin{cases}0&\text{wenn } n = 0\\1&\text{wenn } n = 1\\f\left(n-2\right)+f\left(n-1\right)&\text{wenn } n > 1\end{cases}=\begin{cases}f\left(\lfloor\frac{n}{2}\rfloor+1\right)^2 + f\left(\lfloor\frac{n}{2}\rfloor-1\right)^2 & \text{wenn } n \mod 2 = 1 \\ f\left(\frac{n}{2}+1\right)^2 - f\left(\frac{n}{2}-1\right)^2 & \text{wenn } n \mod 2 = 0\end{cases}§.
Ok, schauen wir uns mal für §n=0§ das ganze an: §f\left(0\right)=0=f\left(1\right)^2-f\left(-1\right)§ oh nein, das ist nicht definiert... :(
Dann eben für §n=1§: §f\left(1\right)=1=f\left(1\right)^2+f\left(0\right)^2=1^2+0^2=1§, cool!

Jetzt für irgendein §n>0,n\mod 2=0§: §f\left(n-2\right)+f\left(n-1\right)=f\left(\frac{n}{2}+1\right)^2+f\left(\frac{n}{2}-1\right)§
Nehmen wir uns die absolute Formel §f\left(n\right)=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)=\frac{1}{\sqrt{5}}\left(\phi^n-\bar{\phi}^n\right)§ dazu nun zur Hilfe:
§\frac{1}{\sqrt{5}}\left(\phi^{n-2}-\bar{\phi}^{n-2}\right)+\frac{1}{\sqrt{5}}\left(\phi^{n-1}-\bar{\phi}^{n-1}\right)=\left(\frac{1}{\sqrt{5}}\left(\phi^{\frac{n}{2}+1}-\bar{\phi}^{\frac{n}{2}+1}\right)\right)^2+\left(\frac{1}{\sqrt{5}}\left(\phi^{\frac{n}{2}-1}-\bar{\phi}^{\frac{n}{2}-1}\right)\right)^2=\cdots§ hach, jetzt hab ich keine Lust mehr. :crazy:

Das erste Bild auf Wikipedia legt den Zusammenhang schon nahe: https://de.wikipedia.org/wiki/Fibonacci-…nacciBlocks.svg
Danke LG

MfG
Check
Das gibt Übersicht! Stay gold.

marcgfx

Treue Seele

Beiträge: 236

  • Private Nachricht senden

26

13.04.2016, 17:05

C-/C++-Quelltext

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

/*
haha :) das ist mir viel zu kompliziert...
Ich seh bei Wikipedia unter Identitäten steht zumindest die Formel für 2n+1 (bei mir die ungeraden Zahlen):
*/

f(2n+1) = f(n)^2 + f(n+1)^2

n=4;
f(9) = f(4)^2 + f(5)^2 = 9 + 25 = 34

//was fehlt ist:

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

f(8) = f(5)^2 - f(3)^2 = 25-4 = 21

//oder seh ich da was nicht richtig?
Devader DevLog - Devader spielen

cojo2015

Alter Hase

  • »cojo2015« ist der Autor dieses Themas

Beiträge: 516

Wohnort: bei mir zu Hause

Beruf: Schüler

  • Private Nachricht senden

27

13.04.2016, 18:42

Puh da hatte ich ja zu lesen :D Schon mal vielen Danke für die ganze Hilfe. Leider kann ich erst am Wochenende programmieren, da Schule im Moment recht stressig ist und Schule geht nunmal vor. Da lässt sich nichts machen ;)

cojo2015

Alter Hase

  • »cojo2015« ist der Autor dieses Themas

Beiträge: 516

Wohnort: bei mir zu Hause

Beruf: Schüler

  • Private Nachricht senden

28

17.04.2016, 11:09

Zitat von »marcgfx«

C-/C++-Quelltext

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

/*
haha :) das ist mir viel zu kompliziert...
Ich seh bei Wikipedia unter Identitäten steht zumindest die Formel für 2n+1 (bei mir die ungeraden Zahlen):
*/

f(2n+1) = f(n)^2 + f(n+1)^2

n=4;
f(9) = f(4)^2 + f(5)^2 = 9 + 25 = 34

//was fehlt ist:

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

f(8) = f(5)^2 - f(3)^2 = 25-4 = 21

//oder seh ich da was nicht richtig?

Kurze Frage: Das n ist eine vom User eingegebene Zahl, oder? Und f gibt dann was zurück?

Nimelrian

Alter Hase

Beiträge: 1 216

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

  • Private Nachricht senden

29

17.04.2016, 11:17

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

30

17.04.2016, 11:22

Zitat von »Nimelrian«

Die n-te Fib.-Zahl

Also gibt sie die dazugehörige Fib.-Zahl von n zurück?

Werbeanzeige

Ähnliche Themen