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.
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Sonntag 27. August 2006, 11:18

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

Sonntag 27. August 2006, 12:05

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

Sonntag 27. August 2006, 12:13

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

Sonntag 27. August 2006, 12:39

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

Sonntag 27. August 2006, 12:53

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

Sonntag 27. August 2006, 13:53

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

Sonntag 27. August 2006, 14:24

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

Sonntag 27. August 2006, 14:46

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:

Sonntag 27. August 2006, 22:28

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

Montag 28. August 2006, 00:55

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

Montag 28. August 2006, 06:17

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

Mittwoch 13. September 2006, 18:35

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)

Mittwoch 13. September 2006, 18:50

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

Mittwoch 13. September 2006, 19:01

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)

Mittwoch 13. September 2006, 19:32

genau!!!
Antworten