Hallo.

Könnte bitte jemand den 6. Aufgabenzettel der T3 Übung hier posten, sofern die Aufgabe abzugeben ist.

Danke im Vorraus

Ist nicht abzugeben.

Worum gehts (grob)

fibonaccifunction mit ~96 bit breitem rueckgabewert. eine struct mit drei unsignet ints iirc.

also rekursiv ists krank 2^113 rechenschritte^^

also rekursiv ists krank 2^113 rechenschritte^^

Nicht unbedingt! [img]http://www.fb18.de/gfx/23.gif[/img] Mir ist neulich mal eine nette
Gleichung aufgefallen:
[img]http://mokrates.de/cgi-bin/texstring?%20f_n%3Df_k%5Ccdot%20f_%7Bn-k%7D%2Bf_%7Bk-1%7D%5Ccdot%20f_%7Bn-k-1%7D[/img],
die man leicht mit Induktion nach k beweist. Daraus folgt
nämlich insbesondere (wenn man k entsprechend wählt):
[img]http://mokrates.de/cgi-bin/texstring?%20f_%7B2n%7D%3Df_n%5E2%2Bf_%7Bn-1%7D%5E2[/img]
und
[img]http://mokrates.de/cgi-bin/texstring?%20f_%7B2n%2B1%7D%3Df_n(f_%7Bn-1%7D%2Bf_%7Bn%2B1%7D)%3Df_n%5E2%2B2f_n%5Ccdot%20f_%7Bn-1%7D[/img]

Damit kann man die Berechnung von [img]http://mokrates.de/cgi-bin/texstring?f_n[/img] sehr
schnell rekursiv programmieren, man muss nur unterscheiden,
ob n gerade oder ungerade ist. Und das ganz ohne die Speicher-
Technik aus P1! Ich weiß allerdings nicht, wie bekannt diese
Gleichungen sind (hab sie noch nicht irgendwo in einem Buch
oderso entdeckt), also im Zweifel dazuschreiben.

Viel Spass! [img]http://www.fb18.de/gfx/28.gif[/img]