Inizialmente avevo codificato il programma in modo sbagliato. Invece di restituire i numeri di Fibonacci tra un intervallo (cioè startNumber 1, endNumber 20 dovrebbe = solo i numeri tra 1 & 20), ho scritto per il programma di visualizzare tutti i numeri di Fibonacci tra un intervallo (cioè startNumber 1, endNumber 20 visualizza = primi 20 numeri di Fibonacci). Pensavo di avere un codice sicuro. Inoltre non capisco perché questo accade.
startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))
def fib(n):
if n < 2:
return n
return fib(n-2) + fib(n-1)
print map(fib, range(startNumber, endNumber))
Qualcuno ha sottolineato nella mia Parte II (che è stata chiusa per essere un duplicato - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii) che ho bisogno di passare lo startNumber e l'endNumber attraverso un generatore usando un ciclo while. Qualcuno può per favore indicarmi la direzione su come farlo? Qualsiasi aiuto è benvenuto.
Sono un programmatore in fase di apprendimento e mi sono imbattuto in un piccolo guaio. Mi è stato chiesto di scrivere un programma che calcolerà e visualizzerà la sequenza di Fibonacci da un numero iniziale e finale inseriti dall'utente (ad esempio startNumber = 20 endNumber = 100 e visualizzerà solo i numeri tra questo intervallo). Il trucco è quello di usarlo in modo inclusivo (che non so come fare in Python? - Presumo che questo significhi usare un intervallo inclusivo?).
Quello che ho finora non è una vera e propria codifica, ma piuttosto:
Non ho idea da dove iniziare e sto chiedendo idee o intuizioni su come scrivere questo. Ho anche provato a scrivere la forumla della sequenza Fib ma mi perdo anche su questo.
Ci sono molte informazioni sulla sequenza di Fibonacci su wikipedia e su wolfram. Molto di più di quello di cui potreste aver bisogno. Comunque è una buona cosa imparare ad usare queste risorse per trovare (velocemente se possibile) ciò di cui avete bisogno.
In matematica, è data in forma ricorsiva:
In programmazione, infinito non esiste. Puoi usare una forma ricorsiva traducendo la forma matematica direttamente nel tuo linguaggio, per esempio in Python diventa:
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)
Provatelo nella vostra lingua preferita e vedrete che questa forma richiede molto tempo man mano che n diventa più grande. Infatti, questo è O(2n) in tempo.
Andate sui siti che vi ho linkato e vedrete questo (su wolfram):
Questo è abbastanza facile da implementare e molto, molto veloce da calcolare, in Python:
from math import sqrt
def F(n):
return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))
Un altro modo per farlo è seguire la definizione (da wikipedia):
Il primo numero della sequenza è 0, il secondo numero è 1, e ogni numero successivo è uguale alla somma dei due numeri precedenti della sequenza stessa, ottenendo la sequenza 0, 1, 1, 2, 3, 5, 8, ecc.
Se il vostro linguaggio supporta gli iteratori potete fare qualcosa come
def F():
a,b = 0,1
while True:
yield a
a, b = b, a + b
Una volta che sapete come generare i numeri di Fibonacci, dovete solo scorrere i numeri e controllare se verificano le condizioni date.
Supponiamo ora di aver scritto un f(n) che restituisce l'n-esimo termine della sequenza di Fibonacci (come quello con sqrt(5) )
Nella maggior parte dei linguaggi potete fare qualcosa come
def SubFib(startNumber, endNumber):
n = 0
cur = f(n)
while cur <= endNumber:
if startNumber <= cur:
print cur
n += 1
cur = f(n)
In python userei la forma iteratore e andrei per:
def SubFib(startNumber, endNumber):
for cur in F():
if cur > endNumber: return
if cur >= startNumber:
yield cur
for i in SubFib(10, 200):
print i
Il mio suggerimento è di imparare a leggere ciò di cui hai bisogno. Il progetto Euler (cercalo su Google) ti insegnerà a farlo :P Buona fortuna e buon divertimento!
L'idea dietro la sequenza di Fibonacci è mostrata nel seguente codice Python:
def fib(n):
if n == 1:
return 1
elif n == 0:
return 0
else:
return fib(n-1) + fib(n-2)
Questo significa che fib è una funzione che può fare una delle tre cose. Definisce fib(1) == 1, fib(0) == 0, e fib(n) essere:
fib(n-1) + fib(n-2)
Dove n è un intero arbitrario. Questo significa che fib(2), per esempio, si espande nella seguente aritmetica:
fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1
Possiamo calcolare fib(3) allo stesso modo con l'aritmetica mostrata qui sotto:
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0
La cosa importante da capire qui è che fib(3) non può essere calcolato senza calcolare fib(2), che è calcolato conoscendo le definizioni di fib(1) e fib(0). Avere una funzione che chiama se stessa come fa la funzione fibonacci si chiama ricorsione, ed è un argomento importante nella programmazione.
Questo suona come un compito a casa, quindi non ho intenzione di fare la parte iniziale e finale per voi. Python è un linguaggio meravigliosamente espressivo per questo però, quindi questo dovrebbe avere senso se si capisce la matematica, e si spera che vi insegnerà la ricorsione. Buona fortuna!
Edit: Una potenziale critica al mio codice è che non usa la super-maneggevole funzione Python yield, che rende la funzione fib(n) molto più breve. Il mio esempio è un po' più generico però, dal momento che non molti linguaggi al di fuori di Python hanno effettivamente il rendimento.