c++.de :: Fakultät in logarithmischer Lauftzeit berechnen

CBR-Racer Mitglied 19:07:51 09.12.2003 Titel:

also ich bin auch mal gespannt ... weil denke nicht, daß ich bis Freitag eine Lösung habe ... muss auch noch bis Donnerstag nen Vortrag zum Thema VPN für eine andere Vorlesung vorbereiten und habe einfach genug zu tun ...

habe mich aber trotzdem nochmal ein wenig beschäftigt mit der ganzen Sache und habe mal drüber nachgedacht ... es gab mal einen Algorithmus mit dem ich 2 natürliche Zahlen in logarithmischer Laufzeit berechnen kann ... aber das brachte mich dann wieder auch nicht weiter ... wollte die Zahlen dann variabel lassen und die Zahlen für die Fakultät einsetzen aber dadurch hat das ganze ja wieder keine logarithmische Laufzeit

Unregistrierter

Wollte den Thread mal wieder nach vorn holen ... heute ist doch die Antwort fällig, ne?

Gruß

Jester Moderator 11:54:48 12.12.2003 Titel:

Hab heut morgen auch schon dran gedacht.

SG1 Mitglied 13:20:20 12.12.2003 Titel:

*gespanntsei*

CBR-Racer Mitglied 22:01:48 12.12.2003 Titel:

*Trommelwirbel*

Und hier präsentier ich euch die Lösung

...

also ihr werdet es kaum glauben ... also der Prof sprach mich heute an und fragte, ob ich die Aufgabe geschafft hätte ... ich sagte mit herabgesenktem Kopf nein ... fragte aber auch gleich wie man die Fakultät in logarithmischer Laufzeit berechne ... er schaute nur etwas verdutzt und fragte, ob er wirklich Fakultät gesagt hätte ... das wurde ihm dann von mehreren Leuten bestätigt ... er entschuldigte sich höflich ... was er eigentlich wollte war ein Algorithmus um die Fibonacci-Zahlen in logarithmischer Lauftzeit ...

*lach* naja sorry Leute ... aber war nicht meine Schuld ... jetzt muss ich mir mal Gedanken über die neue "richtige" Aufgabe machen :rolleyes:

Gregor Moderator 22:07:38 12.12.2003 Titel:

Ich weiß die Lösung!

...ich weiß sogar 2 Lösungen!

CBR-Racer Mitglied 22:09:02 12.12.2003 Titel:

du meinst jetzt für die Fibonacci-Zahlen in logarithmischer Laufzeit ?? :eek:

.... her damit

Gregor Moderator 22:15:42 12.12.2003 Titel:

Du sollst ja auch noch etwas zu tun haben, aber ich gebe dir nen Tipp:

Es gibt für die Fibonaccizahlen eine explizite Formel (die also nicht rekursiv ist). Ich denke, dass man diese Formel leicht so implementieren kann, dass sie in logarithmischer Zeit berechnet werden kann.

...jetzt mußt du nur noch die Formel herausfinden!

...die zweite Lösung war natürlich:

Alles vorher ausrechnen und in nem Array speichern. Bei den 46 (glaube ich, mich zu erinnern) Fibonaccizahlen, die man auf herkömmlichen Wegen darstellen kann, ist das IMHO immer noch eine vollkommen legitime, richtige und natürliche Lösung. Es ist sogar die beste Lösung.

CBR-Racer Mitglied 22:28:41 12.12.2003 Titel:

THX ... muss dazu sagen, die Formel für die Fibonacci-Zahlen habe ich schon ... jetzt muss ich nur nochmal nen Prog dazu schreiben und das in logarithmischer Zeit ... aber das mach ich erst morgen oder so ... muss mich noch ein wenig um meine HP´s kümmern und Tagesguck schauen

...

war nur auf die zweite Lösung gespannt ...

xroads42 Mitglied 00:54:04 13.12.2003 Titel:

Ich machs in O(1) *gg*