Fibonacci OOP

otze

desert pinguin schrieb:

Das ist die richtige Lösung

#include <iostream> 
using namespace std; 
template<unsigned i> 
struct fibonacci { 
  static const unsigned result = fibonacci<i-1>::result + fibonacci<i-2>::result; 
}; 

template<> 
struct fibonacci<0> { 
  static const unsigned result = 1; 
}; 

template<> 
struct fibonacci<1> { 
  static const unsigned result = 1; 
};
int main() { 
  cout << fibonacci<9>::result; 
}

Copyright von Rainer Baumann

2 fragen:
1. wird das hier während des compilieren berechnet?
2. ist das wirklich der richtige algorithmus? fiboacci war doch
1,1,2,3,5,8,13...

//edit aua... hab mich verguckt, die funktion berechnet die Zahl an der 9. stelle der liste oder?^^

davie

zu 1. ja
zu 2.(edit): ja

SideWinder

@otze: Falls dich das interessiert google mal nach "Metaprogrammierung" bzw. "Generische Programmierung".

MfG SideWinder

otze

SideWinder schrieb:

@otze: Falls dich das interessiert google mal nach "Metaprogrammierung" bzw. "Generische Programmierung".

MfG SideWinder

da kannste dich drauf verlassen, dass ich danach googlen werde, ich intressiere mich für alle fein(grob)heiten der programmierung

volkard

otze schrieb:

SideWinder schrieb:

@otze: Falls dich das interessiert google mal nach "Metaprogrammierung" bzw. "Generische Programmierung".

da kannste dich drauf verlassen, dass ich danach googlen werde, ich intressiere mich für alle fein(grob)heiten der programmierung

perfekter einsteig in die metaprogrammierung ist imho Blitz++ und Todd Verhouldsons artikel über expression templates (als link bei Blitz++ angegeben). die expression templates ruhig mal ein wenig nachprogrammieren. danach am besten ein bis zwei jahre lisp oder prolog programmieren. die kluft zwischen den einfachen sachen und den krassen ist schlimm gross. und dann den code von boost lesen.

Walli

Wenn man die Fibonaccizahlen schon in eine Klasse kapselt wäre das doch ein schönes Beispiel für Memoization, um die Laufzeit im Zaun zu halten.

volkard

MaSTaH schrieb:

Wenn man die Fibonaccizahlen schon in eine Klasse kapselt wäre das doch ein schönes Beispiel für Memoization, um die Laufzeit im Zaun zu halten.

warum nicht iterov oder tail-recursive machen?
memoization ist für micht nur ne zweitbeste lösung.

SirLant

Jester schrieb:

SirLant schrieb:

... sollte ja auch nur zeigen,
wie ich so was schreiben würde.

Eben, und ich hoffe doch eigentlich, daß Du es iterativ schreiben würdest.

Hälst du mich wirklich für so dumm

Klar würd ichs iterativ machen, aber warscheinlicher wäre, dass es es mit der
Templatemetaprogrammierung lösen würd, weil ich das schon fertig aufm PC hab,
das andere müsst ich erst schreiben

Jester

Nein, ich halte Dich nicht für dumm, deswegen habe ich ja gesagt, ich hoffe, daß Du es iterativ schreiben würdest und nicht, wie Du weiter oben behauptet hast rekursiv.

Und die template-Lösung scheidet aus:

int i;
cin >> i;
cout << fibonacci(i);

int i;
std::cin >> i;
std::cout << fibonacci<i>::result;

SirLant

Jester schrieb:

Nein, ich halte Dich nicht für dumm, deswegen habe ich ja gesagt, ich hoffe, daß Du es iterativ schreiben würdest und nicht, wie Du weiter oben behauptet hast rekursiv.

Und die template-Lösung scheidet aus:
int i;
cin >> i;
cout << fibonacci(i);

War doch nur der einfachheit wegen Rekursiv, ist doch viel kürzer zu schreiben

Also wenn ich das mit der Metaprogrammierung richtig verstanden habe, wird das
in diesem Fall ganz normal zur Laufzeit ausgewertet, oder hab ich da was falsch verstanden?

Shade Of Mine

SirLant schrieb:

Also wenn ich das mit der Metaprogrammierung richtig verstanden habe, wird das
in diesem Fall ganz normal zur Laufzeit ausgewertet, oder hab ich da was falsch verstanden?

Ne, wie sollte das gehen?
schließlich ist i keine Compiletime Konstante, aber genau das wird von Templates verlangt.

SirLant

Shade Of Mine schrieb:

SirLant schrieb:

Also wenn ich das mit der Metaprogrammierung richtig verstanden habe, wird das
in diesem Fall ganz normal zur Laufzeit ausgewertet, oder hab ich da was falsch verstanden?

Ne, wie sollte das gehen?
schließlich ist i keine Compiletime Konstante, aber genau das wird von Templates verlangt.

Dachte gerade, dass dann so lange neue Objekte erzeugt werden, bis der Spezialfall
eintritt, dieses Objekt wird zuEnde erstellt, wodurch die ganze Kette der Objekte
sich auflöst und wie bei ner Rekursion, dann eines nach dem anderen fertig wird
und das letzte, dann das Ergebnis enthält, aber hast ja recht, es kann ja gar
nicht gehen