Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
13.03.2003, 17:45 Uhr
~0xdeadbeef
Gast

Ha, was virtual kann, kann ich schon lange.

Schreibt ein Programm, dass in höchstens logarithmischer O-Zeit Fibonacci-Zahlen ausrechnet. Der Gewinner darf sich einen Keks freuen.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
13.03.2003, 20:47 Uhr
Hans
Library Walker
(Operator)

Hi,

Bitte nicht sauer sein, aber wenn ich mich recht erinnere war da doch mal was im Matheforum...

Hans
--
Man muss nicht alles wissen, aber man sollte wissen, wo es steht. Zum Beispiel hier: Nachdenkseiten oder Infoportal Globalisierung.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
13.03.2003, 21:24 Uhr
~0xdeadbeef
Gast

Ja gut, aber seine Lösung lief in linearer O-Zeit, und dass kann ja nun jeder. Schaffst du's in O(log(n))?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
14.03.2003, 13:01 Uhr
~0xdeadbeef
Gast

OK; das mit der log(n)-Zeit ist mehr ne akademische Anwendung, weiter als bis zur 84igsten kommt man wegen Rundungsfehlern nicht, selbst wenn man long doubles verwendet... (Das muss jetzt aber genug Hilfestellung sein)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
14.03.2003, 19:53 Uhr
NemoEimi

Zitat:

~0xdeadbeef postete
Ha, was virtual kann, kann ich schon lange. Schreibt ein Programm, dass in höchstens logarithmischer O-Zeit Fibonacci-Zahlen ausrechnet. Der Gewinner darf sich einen Keks freuen.

Die n-te Fibonacci-Zahl mit O(log n) Multiplikationen/Additionen zu berechnen, ist leicht (das einfachste Verfahren, mit dem das zu erreichen ist, nutzt einfach die übliche square-and-multiply-Methode zur Berechnung der richtigen Potenz der darstellenden Matrix der Rekursionsgleichung für die Fibonaccizahlen). Die Grundoperationen für Zahlen beliebiger Größe in konstanter Zeit durchzuführen, dürfte allerdings schwierig sein

......

Grüße,
NemoEimi

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
24.03.2003, 15:51 Uhr
~0xdeadbeef
Gast

Ich habs konstant:

C++:

template <int i> class fibonacci {
public:
    inline int betrag() { return fibonacci<i-1>.betrag() + fibonacci<i-2>.betrag(); }
};

class fibonacci<0> {
public:
    inline int betrag() { return 0; }
};

class fibonacci<1> {
    inline int betrag() { return 1; }
};

Es dürfte zwar bei entsprechend großen Fibonacci-Zahlen recht lange dauern, bis der Compiler fertig ist, und man muss zur Compilezeit wissen, die wievielte Fibonacci-Zahl man haben will, aber naja, man kann nicht alles haben

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
24.03.2003, 16:09 Uhr
~0xdeadbeef
Gast

Oder was haltet ihr davon?

C++:

#include <iostream>

using namespace std;

/////////////////////////////////
// Fibonacci Templates         //
/////////////////////////////////

template <int i> class fibonacci {
public:
  static const unsigned long long betrag = fibonacci<i-1>::betrag + fibonacci<i-2>::betrag;
};

class fibonacci<0> {
public:
  static const int betrag = 0;
};

class fibonacci<1> {
public:
  static const int betrag = 1;
};

///////////////////////////////////
// Loop templates                //
///////////////////////////////////

template<int i> class fib_loop {
public:
  static const void body() {
    cout << i << ":\t" << fibonacci<i>::betrag << endl;
    fib_loop<i+1>::body();
  }
};

class fib_loop<93> {
public:
  static const void body() {
    cout << "93:\t" << fibonacci<93>::betrag << endl;
  }
};

int main(int argc, char* argv[]) {
  fib_loop<0>::body();
  return 0;
}

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
08.04.2003, 18:21 Uhr
TBO

Zitat:

~0xdeadbeef postete
Ich habs konstant:
[...]
Es dürfte zwar bei entsprechend großen Fibonacci-Zahlen recht lange dauern, bis der Compiler fertig ist, und man muss zur Compilezeit wissen, die wievielte Fibonacci-Zahl man haben will, aber naja, man kann nicht alles haben

Das gilt aber nicht, einfach die (nicht-konstante) Berechnung den Compiler machen lassen und dann behaupten, der Algorithmus sei O(1).
Da könnt' ja jeder kommen. *g*

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ Rätselecke ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: