Funktion zur Überprüfung ob Wert in Folge.

[Miscelo]

Hallo liebe Forumer:
Ich habe hier gerade einen hänger. Ich möchte eine Funktion schreiben, die mir den Wert TRUE zurückgibt, wenn eine bestimmte natürliche Zahl in einer Zahlenfolge vorkommt.
Ich habe als Bespiel hier mal die Fibonacci-Zahl genommen.
Ich möchte in diesen Beispiel testen, ob die Zahl 13 auch eine Fibonacci-Zahl ist. Ich bin sehr unzufrieden mit meiner Lösung. Ich habe den Ergebnissraum in eine Liste gesteckt und iterier dann über diese und vergleiche ob die natürliche Zahl in der Liste ist. True, wenn ja, False, wenn nein. Aber das muss doch auch ohne Liste gehen. Bei grösseren Zahlen wird das doch brutal langsam. Danke für eure Hilfe.

Code: Alles auswählen

#Funktion gibt einen bestimmten Fibonacci-Wert zurück
def fibo(n):
    a,b = 0,1
    for i in range(n):
        a,b = b, a + b
    return a

#Funktion testet, ob eine bestimmte natürliche Zahl in der Zahlenfolge enthalten ist.
def check_true_false(n):
    liste = []
    for i in range(n+1):
        liste.append(fibo(i))
    print(liste)
    if n in liste:
        return True
    else:
        return False

print(check_true_false(13))

[__deets__]

Es zwingt dich doch niemand eine Liste anzulegen. Du musst doch nur die Fibonacci Funktion bis zum gegebenen Limit aufrufen & jeweils das Ergebnis prüfen.

[Sirius3]

Dann steck die Zahlen doch einfach nicht in eine Liste, sondern prüfe sofort.

Code: Alles auswählen

def check_true_false(n):
    for i in range(n+1):
        if n == fibo(i):
            return True
    return False

Die letzten vier Zeilen hätten sich auch kürzer als

Code: Alles auswählen

return n in liste

schreiben lassen können.
Du hast Glück dass die Fibonacci-Folge monoton steigend ist, sonst wäre die Prüfung auf nicht vorhanden deutlich komplizierter.
Du gehst auch noch zu weit. Sobald fibo(i) größer n ist, kannst Du die Suche abbrechen. Der Funktionsname ist verwirrend. Du testest ja nicht true und false, sondern ob eine Zahl in der Fibonacci-Folge ist.

[Miscelo]

Danke vielmals:
Die Idee ist schon, das ich die Funktion auf alle monoton steigenden/fallenden Zahlenfolgen anwenden kann.

#folgender Code Funktioniert nicht für n=2 und n=3.

Code: Alles auswählen

def check_true_false(n):
    for i in range(n+1):
        if n == fibo(i):
            return True
    return False

Ich habe mir das auch so einfach vorgestellt. Ich werde das mal mit Generatoren angehen und laufzeiten testen.

[__blackjack__]

@Miscelo: Das ist ja nur eine Vereinfachung *Deiner* Funktion. Die funktionierte ja auch schon nicht für 2 und 3. Das `n` auf diese Weise zur Bestimmung der Listenlänge zu verwenden ist halt falsch. Bei zu kleinen Werten werden nicht genug Elemente erzeugt, und bei grösseren Werten werden zu viele Elemente erzeugt. Man muss solange Elemente erzeugen, solange die kleiner als `n` sind. Wenn man beispielsweise n=10 hat, dann erzeugt Dein Ansatz die ersten 11 Elemente, von denen aber schon vier überhaupt nicht mehr in Frage kommen weil die Zahlen grösser als 10 sind.

Noch mal (fast) Dein Original:

Code: Alles auswählen

In [38]: def check_true_false(n): 
    ...:     liste = [fibo(i) for i in range(n+1)] 
    ...:     print(liste) 
    ...:     return n in liste

In [39]: check_true_false(2)                                                    
[0, 1, 1]
Out[39]: False

In [40]: check_true_false(3)                                                    
[0, 1, 1, 2]
Out[40]: False

In [41]: check_true_false(10)                                                   
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Out[41]: False

Mindestens 21, 34, und 55 hätte man gar nicht mehr erzeugen brauchen. Und bei n=2 und n=3 sind es halt zu wenige erzeugte Elemente.

[nezzcarth]

Ich werde das mal mit Generatoren angehen und laufzeiten testen.

Wenn ich den gängigen iterativen Algorithmus ohne Listen zur Berechnung von Fibonaccizahlen nehme und abbreche, sobald die Zahlen zu hoch werden, bekomme ich für alle halbwegs realistischen Zahlen sofort ein Ergebnis. Bereits die 1000. Fibonacizahl ist ja schon so gigantisch, dass sie alles abdecken dürfte, was man je testen will und augenblicklich berechnet. Wenn du es richtig implementierst, sollte es also im Grunde keine nennenswerte Laufzeit geben, die sich zu messen lohnt.

[DeaD_EyE]

So?

Code: Alles auswählen

import itertools


def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b


def check():
    # exception handling ...
    val = int(input("Bitte eine Zahl eingeben: "))
    # exeption handling ....
    if val > max_val:
        raise ValueError("Zahl ist leider zu groß")
    if val in lookup_table:
        print(f"{val} kommt in der Fibonacci-Folge vor.")
    else:
        print(f"{val} kommt nicht in der Fibonacci-Folge vor.")
    print()

lookup_table = set(itertools.islice(fib(), 0, 100_000))
max_val = max(lookup_table)
print("Die größte Zahl in der lookup_table is", max_val.bit_length(), "bit lang.")
while True:
    check()

Ich habe mich vorhin nur gewundert, dass ich nach dem sortieren des sets die doppelte 1 fehlte.
Ja, logisch. In einem set kommt jedes Element nur einmal vor.
Der Lookup ist sehr schnell, weswegen ich ein set verwendet habe.

Und als Hinweis: Die größte Zahl in der lookup_table is 69423 bit lang.

Hatte die Zahl hier gepostet, aber dann meckert JavaScript, dauert zu lange.

Ich bin mir ziemlich sicher, dass niemals ein Mensch eine so große Zahl in einem Computer eingeben wird.