3. Rekursion so machbar?

Rekursion so machbar?

  • N
     

    const std::size_t array_size=...;

template<class U>
class l_table    //lästige initialisierungen...
{
private:
    U a[array_size];
public:
    l_table(){for(std::size_t i=0;i<array_size;++i)a[i]=0;a[0]=a[1]=1};
    U& operator[](std::size_t index){if(index>=array_size)return 0;return a[index];};
};

template<class U>
U fibonacci(U ui)
{
    static l_table look;
    if((U& t=l[static_cast<std::size_t>(ui)])!=0)
        return t;
    else
        return t=fibonacci(ui-1)+fibonacci(i-2);
};

    Weß au net wieso ich das jetzt hier hingeschrieben hab...
    Is auch nicht iterativ, dass kann der threadersteller machen wenn er will...

    0
  • L

    das else ist überflüssig und das if funktioniert so auch nicht.. musste so schreiben:

    template<class U> 
U fibonacci(U ui) 
{ 
    static l_table<U> look;
    U& t=look[static_cast<std::size_t>(ui)]);
    if(t) 
        return t;
     return t=fibonacci(ui-1)+fibonacci(ui-2); 
};

    außerdem geht dein

    U& operator[](std::size_t index){if(index>=array_size)return 0;return a[index];};

    so auch nicht, da du nicht die konstante 0 per nicht konstanter referenz übergeben kannst >_<

    0
  • ?

    Wenn du Fibonacci-Zahlen schnell ausrechnen willst, machst dus nicht rekursiv. (Hoffe ich mal...)

    0
  • ?

    Der klassische Fehler bei der Berechnung der Fibonacci-Zahlen 😉

    Ich will die Lösung nicht verraten, aber mal als Hinweis:
    Jede Fibonacci-Zahl berechnet sich aus der Summe ihrer beiden Vorgänger. Wenn ich nun f(n) = f(n-2) + f(n-1) schreibe, ist es dann wirklich nötig, für f(n-2) und f(n-1) die volle Rekursion durchzugehen? 😉

    Ich meine (kann sein, dass ich daneben liege), dass die Komplexität so exponentiell ist. Es geht aber linear.

    0
  • J

    Harry Hirsch schrieb:

    Ich meine (kann sein, dass ich daneben liege), dass die Komplexität so exponentiell ist.

    Da liegst Du richtig. Um so rekursiv fib(n) zu berechnen werden fib(n) (+/- 1) Aufrufe der Funktion durchgeführt. Da die Fibonacci-Zahlen exponentiell wachsen ist auch der Aufwand exponentiell.

    Lustigerweise könnte man fib(n) demnach auch berechnen, indem man in einer globalen Variable die Funktionsaufrufe mitzählt. 😃

    0
  • T

    Nochmal ich, vielen Dank für die Antworten, auch wenn ich noch nicht alle verstanden habe, ist aber spaßig was sich aus einer Anfängerfrage so alles entwickelt 🙂

    Theo

    0
  • N

    life schrieb:

    das else ist überflüssig und das if funktioniert so auch nicht.. musste so schreiben:

    Das else ist nicht überflüssig, sonst kann man t nicht mehr sehen. Was ist an dem if falsch?

    life schrieb:

    template<class U> 
U fibonacci(U ui) 
{ 
    static l_table<U> look;
    U& t=look[static_cast<std::size_t>(ui)]);
    if(t) 
        return t;
     return t=fibonacci(ui-1)+fibonacci(ui-2); 
};

    außerdem geht dein

    U& operator[](std::size_t index){if(index>=array_size)return 0;return a[index];};

    so auch nicht, da du nicht die konstante 0 per nicht konstanter referenz übergeben kannst >_<

    Da haste mich drangekriegt. Sollte man am besten als membervariable machen und der vor jeder Rückgabe 0 zuweisen. Ist aber nicht sonderlich performant.

    0
  • W

    Oder einfach keine Referenz zurückgeben...

    0
  • 7
     

    unsigned fibonacci( unsigned i)
{
  if( i == 0) return 0;
  if( i < 3) return 1;
  int n1( 1);
  int n2( 2);
  i -= 3;
  for( ; i != 0; --i) {
    int tmp( n1 + n2);
    n1 = n2;
    n2 = tmp;
  }
  return n2;
}
    0
  • N

    Walli schrieb:

    Oder einfach keine Referenz zurückgeben...

    ne, dann kann ich ja nicht das array editieren...
    @7H3 N4C3R und alle die nach iteration schreien:
    klar, is auch ne möglichkeit mehr performance raus zu kitzeln, aber das würde ich definitiv hinter dem lookuptable anordnen.

    0
  • 7

    Bevor Du anfängst, mir Lookup-Tabellen u.ä. zu hantieren, solltest Du sehen, dass Du den Algorithmus optimierst. Mit der iterativen Version wandelt man ein np-schweres (in nicht polynomialer Zeit lösbares) Problem in ein lineares um. Wer diesen Schritt der Optimierung nicht geht ist selber Schuld.
    Zu der Lookup-Tabelle... worst-case optimal betrachtet ändert sie garnichts an der Schwere des Problemes. Bei sehr häufigem Einsatz kann das was bringen, allerdings muss man sie dann schon sehr groß Anlegen, damit sie wirklich etwas bringt.

    Soo, jetzt sind wir aber gänzlich am Topic vorbeigeschossen... die Mods mögen uns verzeihen 🙂

    0
  • W

    ness: Naja, wenn schon LUT dafür, dann würde ich sie mir zur Compilezeit berechnen lassen oder dumm selber runterschreiben. Performanter geht es eigentlich nicht. Aber eigentlich ist es ja nur ne dumme Übung... 😉

    0
  • N

    Und ich soll mich nicht noch mal rechtfertigen? Dann will ich mal:
    Nehmen wir mal an, wir berechnen fib(7). Ohne LUT (ich kappe mal schon bei 2):

    fib(7)

fib(6)                                                                                     fib(5)

fib(5)                                                    fib(4)                           fib(4)                        fib(3)

fib(4)                          fib(3)                    fib(3)            fib(2)         fib(3)            fib(2)      fib(2) fib(1)

fib(3)           fib(2)         fib(2) fib(1)             fib(2) fib(1)                    fib(2) fib(1)

fib(2) fib(1)

    (Ich hoffe mal das ist verständlich)
    Mit LUT:

    fib(7)

fib(6)   fib(5)
         /
       /
     /
fib(5)  fib(4)       
         /
       /
     /
fib(4)  fib(3)
         /
       /
     /
fib(3)  fib(2)
         / 
       /   
     /      
fib(2) fib(1)

    Die LUT macht also eine ganze Menge Wett, aber ich will nicht bestreiten, dass es nicht sinnvoll ist, eine iterative Variante zu programmieren...
    /edit: streng genommen ist meins algorithmus-optimierung. Ich habs umgeformt, so das jetzt ein dynamischer topdown algorithmus ausgeführt wird...

    0
  • W

    ness: Was du machst ist eine Implementierung mit Memoization. Was ich vorgeschlagen habe war eine reine LUT.

    Also so etwas:

    unsigned fib[] = { 1, 1, 2, 3, 5, 8, 13 /* ... */ };

    Das könnte statt blödem runterschreiben selbstverständlich auch zur Compilezeit berechnet werden, wenn es denn sein muss. Schneller gehts eigentlich nicht mehr. Und sehr groß müsste die LUT auch garnicht sein.

    0
  • L

    ness schrieb:

    life schrieb:

    das else ist überflüssig und das if funktioniert so auch nicht.. musste so schreiben:

    Das else ist nicht überflüssig, sonst kann man t nicht mehr sehen. Was ist an dem if falsch?

    also bei VC++6 geht das jedenfalls nicht

    if((U& t=look[static_cast<std::size_t>(ui)])!=0) 
        return t; 
    else 
        return t=fibonacci(ui-1)+fibonacci(ui-2);

    error C2146: Syntaxfehler : Fehlendes ')' vor Bezeichner 't'
    Siehe Verweis auf Instantiierung der kompilierten Funktion
    svorlage 'unsigned long __cdecl fibonacci(unsigned long)'
    error C2065: 't' : nichtdeklarierter Bezeichner
    Siehe Verweis auf Instantiierung der kompilierten Funktion
    svorlage 'unsigned long __cdecl fibonacci(unsigned long)'
    error C2143: Syntaxfehler : Fehlendes ';' vor '!='
    Siehe Verweis auf Instantiierung der kompilierten Funktion
    svorlage 'unsigned long __cdecl fibonacci(unsigned long)'
    error C2059: Syntaxfehler : ')'
    Siehe Verweis auf Instantiierung der kompilierten Funktion
    svorlage 'unsigned long __cdecl fibonacci(unsigned long)'
    error C2181: Ungueltiges 'else' ohne zugehoeriges 'if'
    Siehe Verweis auf Instantiierung der kompilierten Funktion
    svorlage 'unsigned long __cdecl fibonacci(unsigned long)'
    Fehler beim Ausführen von cl.exe.

    _<

    0
  • W

    Naja, VC++6 ist normalerweise zwar nicht das Maß der Dinge wenn es um Standard-Konformität geht, aber der gcc lässt ein ähnliches Konstrukt jedenfalls auf ansi-pedantic nicht zu... Bin zu faul es auch noch im Standard nachzuschlagen.

    0
  • N

    Naja, ich weiß nicht ob es da ausnahmen gibt, aber sowas:

    if((int r=do_system_funktion())==0)
{
    hat_geklappt();
}
else
{
    melde_fehler(r);
};

    hat doch bestimmt jeder schon gesehen...
    /edit: OK, ihr habt gewonnen ganz so kann man das (warum auch immer) nicht schreiben, aber dank der Lücke, dass c++ 0 als false auswertet könnn wir uns den Vergleich und damit die Klammern schenken, dann gehts:

    if(U& t=look[static_cast<std::size_t>(ui)])
        return t;
    else
        return t=fibonacci(ui-1)+fibonacci(ui-2);

    compiliert mit --ansi fehlerfrei. Mich würde trotzdem mal interessieren, warum der code mit Klammern net geht...

    0
Anmelden zum Antworten