Zitat von »Draco«

Ich hab grad ein Brett vorm Kopf oder bin einfach zu dumm.

hab grad ne Aufgabe in C fertig programmiert zum Thema Fibonacci Zahlen. Als Abschluss steht noch eine Frage in der Aufgabe:

Das Ergebniss sieht so aus:
(links nur Nummerierung, Kommazahl=Fibo.Zahl...)



Im netz habe ich noch folgendes dazu gefunden: klick

Was ist für ne Abhängigkeit gemeint ?

also von coden habe ich nicht wirklich ahnung aber in der rechten spalte kann man eine reihe erkennen

und zwar

1+1 -> 2+1=3 -> 1+3+1=5 -> usw...

also eigendlich so

temp=a+b+1
a=b
b=temp

ka ob dir das weiter hilft

Zitat von »Y0Gi«

these: deine funktion ist hochgradig inperformant. wenn die musterlösung in der beziehung wirklich auch so aussieht, dann gute nacht!

schau mal auf http://wikisource.org/wiki/Fibonacci_sequence
da steht, wie man das mit gescheiter und minimaler laufzeit implementieren kann. das beispiel in C zwar ohne separate funktion, aber dafür auch ruhig mal einen blick auf die lösungen in den anderen sprachen werfen.

In Dracos Aufgabe ging es um Rekursion.
Der Wiki Code ist kein Bisschen rekursiv. Insofern ...
Und dass Draco in der main Methode jede Zahl von Anfang an berechnet ist insofern nicht schlimm, als dass es ihm noch krasser veranschaulicht, dass Rekursion nicht gerade schnell ist.
Diese Erkenntnis war wohl auch das Ziel der Aufgabe.
Ergo: 10 Punkte verdient.
So, das war mein Senf dazu.

Zitat von »Bruce_Lee«

In Dracos Aufgabe ging es um Rekursion.
Der Wiki Code ist kein Bisschen rekursiv. Insofern ...
Und dass Draco in der main Methode jede Zahl von Anfang an berechnet ist insofern nicht schlimm, als dass es ihm noch krasser veranschaulicht, dass Rekursion nicht gerade schnell ist.
Diese Erkenntnis war wohl auch das Ziel der Aufgabe.
Ergo: 10 Punkte verdient.
So, das war mein Senf dazu.

der wikipedia-code ist nicht rekursiv, aber darum ging es auch nicht. die rekursion hat er ja auch schon verstanden.
es ging vielmehr darum zu zeigen, wie man mit mehr als einer variable in der rekursiven funktion eben nur einen unteraufruf pro stufe braucht und nicht zwei, genau das veranschaulicht der code bei wikipedia.
wie verschwenderisch das mit mehreren unteraufrufen ist, fällt bei flüchtiger betrachtung kaum auf, zumal die produzierte zahlenfolge ja richtig ist. wenn man das richtig macht, dann ist die rekursion auch so schnell wie es geht. zu behaupten, rekursion wäre im allgemeinen langsam, ist quatsch. kommt nur darauf an, wie intelligent man sie einsetzt, und das habe ich hier bemängelt (was draco keine dummheit bescheinigen soll).

und nun betrachten wir mal den initalgrund dieses topics: welche abhängigkeit besteht zwischen einer fibonacci-zahl und den funktionsaufrufen?
wenn man das "richtig" löst, ist das eine andere als wenn man das mit dracos ergebnis macht. und diese abhängigkeit ist normalerweise eben n-1 bzw. n funktionsaufrufe zur n. fibonacci-zahl. und das ist hier nicht der fall, also ist das irgendwo verkehrt oder zumindest keineswegs optimal.
ich meine hey, ob nun bei der 20. zahl 20/21 oder knappe 14.000 funktionsaufrufe stattfinden ist ja vollkommen egal! oder?

wenn man also dieses beispiel in der zukunft hernimmt, um darauf ein programm aufzubauen, dann kann das ganz schön in die hose gehen wenn man sich keinen kopf macht.

Zitat von »Y0Gi«

zu behaupten, rekursion wäre im allgemeinen langsam, ist quatsch.

Wirklich? Kannst du mir ein Beispielproblem geben, in dem die rekursive Lösung schneller ist als die iterative? Oder zumindest gleich schnell? Am besten noch ohne größeren Speicherplatzbedarf?
Ich glaube nicht. Falls doch, dann lasse ich mich gerne eines Besseren belehren.

Zitat von »Y0Gi«

der wikipedia-code ist nicht rekursiv, aber darum ging es auch nicht.

Zitat von »Y0Gi«

es ging vielmehr darum zu zeigen, wie man mit mehr als einer variable in der rekursiven funktion eben nur einen unteraufruf pro stufe braucht und nicht zwei, genau das veranschaulicht der code bei wikipedia.

Widersprichst du dir da nicht?

nein, ich habe gerade kein beispiel zur hand. rekursive und iterative lösungen sind aber meist von der geschwindigkeit vergleichbar. was den speicherbedarf angeht, haben iterative aber einen konstanten bereich, während bei der rekursion sehr viel speicher notwendig sein kann. an dieser stelle verweise ich nochmal auf das problem mit den 20 zu 14000 funktionsaufrufen... : allerdings erlauben rekursive funktionen eine elegantere darstellung bestimmter algorithmen.

Zitat von »Bruce_Lee«

Widersprichst du dir da nicht?

vielleicht habe ich mich nur unklar ausgedrückt. draco benutzt mehrere unteraufrufe bei der rekursion. um das zu vermeiden, braucht man mehr variablen. wie man diese einsetzt, zeigt das code-beispiel von wikipedia - nicht rekursiv, aber in die rekursion übertragbar. speziell bei dem wikipedia-beispiel ging es also nicht um rekursion. bei dem anderen geht es, wie alles hier, um rekursion, im speziellen aber durch die optimierung mit mehreren variablen.

Zitat von »powerslide«

hihi..

das is die fibonacci reihe..

die nächste zahl ergibt sich immer aus der summe der beiden vorangegangenen..

also
0 = 0
1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
usw....

definiert durch :

f₀ = 0
f₁ = 1
f_n = f_n-1 + f_n-2

slide

nein das meinte ich nicht ich meine die spalte ganz rechts das ist die fiboncci reihe aber irgendwie immer noch +1. Ich habe ka wie man das mathematisch ausdrückt.