Fibonacci-Reihe bis in eine Tiefe von x

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Hi,
Ich brauche für ein andres Script die Zahlen der Fibonacci-Reihe bis zu einer Tiefe von x.
Mit diesem Script bekomme ich im Endeffekt das was ich brauche, allerdings dauert das bei einer Tiefe von 50 und höher, bis zu einer Stunde und mehr.

Code: Alles auswählen

import os, sys

path = "C:/Dokumente und Einstellungen/Craven/Desktop/Fibonacci.val"
file = open(path, "w+")

n = 100
V = float(raw_input("Geben Sie de Anzahl der Durchlaeufe ein: "))

def CompFibonacci(n):
	x = 1
	fibonacci = [0, 1]
	while x <= V:
		for i in xrange(2, n): 
			asd = fibonacci.append(fibonacci[-2] + fibonacci[-1])
			print i, "---", x
		n += 100
		x += 1
	else:
		pass
	file.write(str(fibonacci))

CompFibonacci(n)

Also dachte ich mir, dass man sozusagen die liste nach jedem Durchlauf an die Datei anhängt, dann die Liste löscht, damit der speicherverbraucht nicht so utopisch wie oben ist :wink:

Hat jemand nen Vorschlag, wie das konkret gehen könnte?

Danke

MfG,
Craven
Zuletzt geändert von Craven am Sonntag 27. August 2006, 13:54, insgesamt 2-mal geändert.
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Maho
User
Beiträge: 10
Registriert: Sonntag 27. August 2006, 11:14

Das ist kein Wunder. Die funktion berechnet nicht die ersten 50 Zahlen, sondern die ersten 50*n (also etwa 150.000(!) Zahlen). Woher hast du die Funktion?

Code: Alles auswählen

def CompFibonacci():
    n = float(raw_input("Geben Sie die Anzahl der Durchlaeufe ein: "))
    fib = [0, 1]
    for i in xrange(n):
        fib.append(fib[-2]+fib[-1])
    return fib
Diese Funktion berechnet die ersten n Fibonacci-Zahlen und gib sie als Liste zurück.
Zuletzt geändert von Maho am Sonntag 27. August 2006, 12:56, insgesamt 1-mal geändert.
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Hi Maho

Dass das script nicht die 'ersten' 50 Zahlen berechnet, ist mir auch klar ^^
Mit "einer Tiefe von 50" mein ich die Durchgänge, also in dem fall 50 * 100 Zahlen

Genau deswegen will ich ja das ganze etwas Ressourcenfreundlicher machen.

Die Funktion hab ich zu 90% selber geschrieben :wink:

MfG,
Craven
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Crush
User
Beiträge: 44
Registriert: Montag 1. Mai 2006, 11:32

Craven hat geschrieben:Mit "einer Tiefe von 50" mein ich die Durchgänge, also in dem fall 50 * 100 Zahlen
Hi Craven,

Aber wozu steht denn das "n += 100" in Zeile 16? Das gibt dann ja nicht 50*100 Zahlen sondern 100+200+300+400+...+n*100 Zahlen!

(oder in pythoncode:

Code: Alles auswählen

def anzahl(n,p):
    z = 0
    for i in range(n):
        z += (i+1)*p
    return z

print anzahl(50,100)
)
Das wären dann 127'500 Zahlen.

Zum eigentlichen Problem fällt mir leider nichts ein, tut mir Leid ...

Crush
Maho
User
Beiträge: 10
Registriert: Sonntag 27. August 2006, 11:14

Craven hat geschrieben: Dass das script nicht die 'ersten' 50 Zahlen berechnet, ist mir auch klar ^^
Mit "einer Tiefe von 50" mein ich die Durchgänge, also in dem fall 50 * 100 Zahlen
Häh? Das ergibt ziemlich wenig sinn. Wenn du die ersten 5000 Zahlen haben willst, dann benutze eben n=5000. Obendrein berechnet deine Funktion ja nicht 50*100, sondern 50*(100-2), da du nur von 2 bis n gehen lässt.

Code: Alles auswählen

def CompFibonacci(path):
    n = float(raw_input("Geben Sie die Anzahl der Durchlaeufe ein: "))
    target = file(path, 'a')
    a, b = 0, 1
    print >> target, a
    print >> target, b
    for i in xrange(n):
        a, b = b, a+b
        print >> target, b
Hier, das ganze ohne Liste, und direkt in eine Datei gespeichert. Beachte bitte das die daten an die Datei angehängt werden. D.h. wenn die Datei bereits existiert, musst du selber für Ordnung sorgen.

EDIT: Was mir gerade eingefaellen ist: du könntest die Funktion natuerlich auch in einen Generator umwandeln, anstatt mit einer grossen Liste im Speicher zu hantieren, oder alles in einer Datei zwischenzuspeichern. Vorteil der Datei ist allerdings: du berechnest die Zahlen nur einmal, und kannst die Datei später immer wieder auslesen.

Code: Alles auswählen

def CompFibonacci(n=5000):
    a, b = 0, 1
    yield a
    yield b
    for i in xrange(V):
        a, b = b, a+b
        yield b
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Danke für die schnellen Antworten

Das ganze ist erst mal ein beta script, das ich heute um 3 in der früh nach einer 5 Tage LAN gemacht hab :wink:
Nicht dass ihr meint, ich würde sonst so nen Bockmist reinhauen ^^

Dass es nicht 5000 Zahlen sind, stimmt natürlich :oops:

Ich wollte eigentlich die Fibonacci-Reihe (rein theoretisch) bis ins Unendliche berechnen lassen, und gleichzeitig die Ressourcen schonen, durch etwas wie das zwischenspeichern der Zahlen, sozusagen ein Resuming-system.

Ich werde mich nochmal dahinter setzen, wenn ich genug Schlaf nachgeholt hab :D
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Maho
User
Beiträge: 10
Registriert: Sonntag 27. August 2006, 11:14

Code: Alles auswählen

def CompFibonacci(n, path):
    try:
        source = file(path)
        a = int(source.readline())
        b = int(source.readline())
        source.close()
    except IOError:
        a, b = 0, 1
        yield a
        yield b

    for i in xrange(n):
        a, b = b, a+b
        yield b
         
    file(path, 'w').write('%s\n%s' % (a, b))
Berechnet n Zahlen und speichert zum Schluss die letzten beide Werte für den nächsten durchlauf. Beim start prüft die Funktion, ob eine Datei mit neuen startwerten existiert um diese dann ggf. zu nutzen.

Ist das in etwa das was du suchst?
Crush
User
Beiträge: 44
Registriert: Montag 1. Mai 2006, 11:32

man könnte das so lösen:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def fib(a, b, n):
    fib = [a,b]
    for i in xrange(n-2):
        fib.append(fib[-2]+fib[-1])
        fib.pop(0)
    
    return fib

f = open('dateiname','w')
f.write(str(fib(0, 1, 1000)))
f.close()
hier befinden sich in "fib" jeweils nur 2 Zahlen. Nach dem Berechnen der nächsten wird die erste Zahl entfernt (mit "fib.pop(0)). Mit "return fib[-1]" wird schliesslich die "(n-1)-te" und die n-te Fibonacci-Zahl zurückgegeben. Ach ja, und a und b sind die Startwerte.

Crush
jAN
User
Beiträge: 170
Registriert: Samstag 4. Juni 2005, 18:51
Wohnort: Großmehlra (in Thüringen)
Kontaktdaten:

ich hab grad das hier gefunden... ich weis net ob dir das hilft aber trotzdem...

Code: Alles auswählen

class memoized(object):
   """Decorator that caches a function's return value each time it is called.
   If called later with the same arguments, the cached value is returned, and
   not re-evaluated.
   """
   def __init__(self, func):
      self.func = func
      self.cache = {}
   def __call__(self, *args):
      try:
         return self.cache[args]
      except KeyError:
         self.cache[args] = value = self.func(*args)
         return value
      except TypeError:
         # uncachable -- for instance, passing a list as an argument.
         # Better to not cache than to blow up entirely.
         return self.func(*args)
   def __repr__(self):
      """Return the function's docstring."""
      return self.func.__doc__

@memoized
def fibonacci(n):
   "Return the nth fibonacci number."
   if n in (0, 1):
      return n
   return fibonacci(n-1) + fibonacci(n-2)

print fibonacci(12)
EDIT:
habs mal ausprobiert... es ist sinnlos für das aktuelle Problem...
#adios.py
import os,sys
while 1: os.startfile(sys.argv[0])
BlackJack

Alternativvorschlag, der wohl jede reine Python-Implementierung schlagen dürfte:

Code: Alles auswählen

import gmpy

def fibonacci(n=5000):
    for i in xrange(n):
        yield gmpy.fib(i)
Das berechnen von `fib(10000000)` braucht auf meiner lahmen Kiste gerade mal 2 Sekunden. Die Umwandlung der ca. 2 Millionen Ziffern in eine Zeichenkette dauert wesentlich länger.
Maho
User
Beiträge: 10
Registriert: Sonntag 27. August 2006, 11:14

Vielleicht solltest du auch noch http://sourceforge.net/projects/gmpy erwähnen.
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Hier ist ein verspätetes Update, allerdings ist mir nicht ganz klar wie die Fehlermeldung zustande kommt.

Code: Alles auswählen

def cf(tiefe):
    file2 = open(Pfad, "a+")
    fibo = [1, 2]
    counter = 0
    try:
        resuming(file2, fibo)
    finally:
        while counter <= tiefe:
            fibos = fibo[-2] + fibo[-1]
            fibo.append(fibos)
            del fibo[0]
            file2.write("%s" % fibo[-1])
            file2.write("\r\n")
            counter += 1

def resuming(file2, fibo):
    try:
        a = file2.readline(-1)
        b = file2.readline(-2)
        fibo = []
        fibo.append(a, b)
        return fibo
    except:
        pass

cf(int(raw_input("Anzahl der loops:    ")))

Code: Alles auswählen

Traceback (most recent call last):
  File "Fibonacci.py", line 37, in ?
    cf(int(raw_input("Anzahl der loops:    ")))
  File "Fibonacci.py", line 23, in cf
    file2.write("%r" % fibo[-1])
IOError: (0, 'Error')
wenn ich

Code: Alles auswählen

    finally:
        while counter <= tiefe:
            fibos = fibo[-2] + fibo[-1]
            fibo.append(fibos)
            del fibo[0]
            file2.write(fibo[-1])
            file2.write("\r\n")
            counter += 1
ausführe, kommt

Code: Alles auswählen

TypeError: argument 1 must be string or read-only character buffer, not int
Ich hoffe jemand von euch kann mir da raushelfen, ich komm nicht drauf :wink:

Danke schonmal für eure Hilfe

MfG,
Craven

edit:// Falsche Variable returned ^^
Zuletzt geändert von Craven am Donnerstag 14. September 2006, 10:29, insgesamt 1-mal geändert.
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Benutzeravatar
DatenMetzgerX
User
Beiträge: 398
Registriert: Freitag 28. April 2006, 06:28
Wohnort: Zürich Seebach (CH)

fibo[0] ist ein integer und '%r' fibo[0] übergibt einen string

sonst mach str(fibo[0])
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Hi DatenMetzgerX

Du meinst so

Code: Alles auswählen

            file2.write(str(fibo[-1]))
?
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Benutzeravatar
DatenMetzgerX
User
Beiträge: 398
Registriert: Freitag 28. April 2006, 06:28
Wohnort: Zürich Seebach (CH)

genau!!!
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Code: Alles auswählen

    file2.write(str(fibo[-1]))
IOError: (0, 'Error')
:wink:
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
BlackJack

Deine `resuming()` Funktion funktioniert nicht. Man kann nicht einfach Zeilen vom Dateiende her mit negativen Zahlen ansprechen. Die Angabe ist die Puffergrösse die Python zum lesen von Zeilen benutzen soll. Werte >0 geben die Maximallänge an, Werte <=0 haben keinen Effekt. Du liest dort immer die ersten beiden Zeilen ein.

Und 'a+' ist als Dateimodus höchst undefiniert. Man sollte Dateien die man mit 'a' öffnet nur schreiben, nicht lesen und kein `seek()` durchführen.
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Hi Blackjack!

Danke für deine Antwort

Hast du eine Idee/Tipp, wie ich das realisieren könnte?
Ansonsten gehts auch ohne resuming, was eher als test gedacht war ... :wink:

MfG,
Craven
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Benutzeravatar
Michael Schneider
User
Beiträge: 569
Registriert: Samstag 8. April 2006, 12:31
Wohnort: Brandenburg

Craven hat geschrieben:Hast du eine Idee/Tipp, wie ich das realisieren könnte?
Ansonsten gehts auch ohne resuming, was eher als test gedacht war ... :wink:
Hi Craven,

erstmal generell statt "a+" sowas:

Code: Alles auswählen

try:
    file2 = open(Pfad, "r+")
    file2.seek(0,2)    ##  Cursor zum Dateiende
except IOError:
    file2 = open(Pfad, "w+")
Ich habe mich noch nicht weiter in den Code reingedacht, aber wenn Du nur die beiden letzten Werte brauchst (zum Addieren), dann solltest Du die nicht dauernd speichern und neu lesen. Das bremst unnötig.

Grüße,
Michael
Diese Nachricht zersört sich in 5 Sekunden selbst ...
Ezechielpitau
User
Beiträge: 7
Registriert: Freitag 25. August 2006, 16:00

Ansonsten gibt es auch eine nicht-rekursive Funktion zur Berechnung. Dann sinnvoll, wenn du nur den Wert für einzelne, sehr große Zahlen berechnen willst und nicht die ganze Reihe.

siehe Formel von Binet http://www.ijon.de/mathe/fibonacci/node2.html#0002200
Antworten