Tribonacci-Nummer, binär ohne Rekursion

[uuull]

Hallo Leute,

Ich arbeite in meiner Uni in zweit-Semester Computer-Labs als Tutor. Das heißt, dass ich für Fragen der Studenten da bin und ihnen weiterhelfe wenn sie nicht mehr weiterwissen.
Heutiges Lab war jedoch außerhalb meines Vermögens, eine Lösung ließ sich einfach nicht finden. Die Aufgabe war:

"Angenommen wir definieren die Fibolucci-Nummern als
f0=0, f1=1, f2=1, und im allgemeinen als fn+1 = fn + fn-1 + fn-2 für n größer als 1.
Die Sequenz sieht demnach so aus: 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, ... Benutze die Idee der binären Berechnung um ein Python-Programm zu schreiben, welches die n. Fibolucci-Nummer berechnet. Es darf keine Rekursion verwendet werden!"

Wir sind zu dritt als Tutor in diesem Lab, und keiner von uns dreien war in der Lage eine Lösung zu finden.

Kann mir jemand da weiterhelfen?? Wäre wirklich außerordentlich dankbar dafür

Viele Grüße
uuull

[webspider]

Code: Alles auswählen

>>> tribs = [0, 1, 1]
>>> tribs.append(sum(tribs[-3:]))
>>> tribs
[0, 1, 1, 2]
>>> tribs.append(sum(tribs[-3:]))
>>> tribs
[0, 1, 1, 2, 4]
>>> tribs[3]
2

Anhand dieses beschämend leichten Ansatzes könnt ihr ganz sicher das gewünschte Programm bauen. Außerdem wundert mich, dass ausgerechnet iterative Ansätze problematisch sein sollen.

[uuull]

Nun ja, keine Frage, die Iteration an sich ist kein Problem. Das Problem ist jedoch der "binäre" Teil...

[webspider]

Dann erläutere den doch mal bitte, Google spuckt mir dazu ausnahmsweise wenig hilfreiches aus.

[Hyperion]

Spannender ist ja eh die Umwandlung in eine funktionale Berechnung... hach ja, das war mein zweites Semester

[uuull]

Dann erläutere den doch mal bitte, Google spuckt mir dazu ausnahmsweise wenig hilfreiches aus.

Das ist leider richtig


Mir steht eine binäre Berechnung von den Fibonacci-Nummern zur Verfügung (vom Professor als Hilfestellung gegeben), die erklärt wohl am besten was ich meine:

Code: Alles auswählen

x=int(input("type in a number\n"))
a=0
b=1
u=0
v=1
n=x
count=0
while (x>0):
  count=count+1
  # Dies ist die "binäre" Berechnung, halbiert die Anzahl der Schritte immer wenn der momentane Schritt ein gerader ist
  if (x%2==0):
    dummy=a
    a=a*a+b*b
    b=2*dummy*b + b*b
    x=x/2
  else:
    x=x-1
    dummy=u
    u=a*u+b*v
    v=b*dummy+(a+b)*v
print (n,"th fibonacci number is",u)
print ("number of times WHILE loop ran is", count)

Leider war keiner von uns in der Lage, dies an Tribonacci anzupassen, das hat sich als erheblich schwieriger herausgestellt als ursprünglich angenommen...

hach ja, das war mein zweites Semester

Stimmt, die guten alten Zeiten...