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
Tribonacci-Nummer, binär ohne Rekursion
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
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
Spannender ist ja eh die Umwandlung in eine funktionale Berechnung... hach ja, das war mein zweites Semester
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
assert encoding_kapiert
Das ist leider richtigDann erläutere den doch mal bitte, Google spuckt mir dazu ausnahmsweise wenig hilfreiches aus.
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)
Stimmt, die guten alten Zeiten...hach ja, das war mein zweites Semester