Come vieni con gli algoritmi?

Una espressione in forma chiusa (chiamata formula di Binet) per i termini della sequenza di Fibonacci è ben conosciuto: Fₙ = (φⁿ-ψⁿ) / √5, dove φ = (1 + √5) / 2 e ψ = (1-√5) / 2. Potresti essere in grado di provare quella formula tramite il teorema Master per le ricorrenze. In ogni caso, esaminando la formula di Binet o calcolando numericamente i rapporti dei termini consecutivi della sequenza di Fibonacci, dovresti rapidamente osservare che Fₙ è nell'ordine di φ volte più grande di Fₙ₋₁. Poiché φ è circa 1.618, ciò implica che Fₙ cresca abbastanza rapidamente con n che presto supera i 4 milioni.

Ecco un esempio di un codice Python che calcola i valori di Fibonacci meno di un limite.

def smallFib(fmax):
    a, b = 0, 1
    while b<fmax:
        print b
        a, b = b, a+b

Esegui il codice (ovvero, inserisci il codice in un interprete python, quindi pronuncia smallFib(4000000) ) e vedrai che in realtà solo circa 33 termini della sequenza di Fibonacci sono inferiori a 4 milioni. Quindi, ha senso semplicemente fare la cosa semplice, e sommare l'11 di quei termini che sono pari. (Per verificare se un numero è pari e aggiungerlo a una somma in tal caso, puoi dire if not b&1: sum += b .)

Si noti che la formula di Binet non fornisce alcuna informazione a priori se un termine sarà pari o dispari. Ad ogni modo, ogni terzo F è pari, quindi puoi calcolare F₃, F₆, F₉ ..., ma sapere che ogni terzo Fₙ è anche necessario per ispezionare i numeri o provare qualcosa sui numeri di Fibonacci. In molti casi, l'uso di una formula chiusa leggermente complicata non è in grado di risparmiare tempo rispetto ai valori di elaborazione tramite una ricorrenza estremamente semplice.

Riepilogo: non utilizzare un approccio complicato quando si eseguirà un approccio semplice. Impara un linguaggio interpretato come python in modo che tu possa eseguire semplici test per scoprire se un approccio semplice è abbastanza buono.

Questo dovrebbe probabilmente essere chiuso come troppo ampio. Voglio dire, ti farò riferimento a How To Solve di Polya , che è qualcosa di classico, ma questa lista potrebbe andare avanti indefinitamente.

Un po 'più specificamente -

1. Ordina. Sì, con un sacco di pensieri e rielaborazioni, ma mi capita di conoscere la forma chiusa per Fibonacci dal mio argomento, da quando mi sono laureato in matematica e ho lavorato su insiemi di problemi che mi hanno portato in questa direzione abbastanza da permettermi di capire grandi parti di esso per conto mio - "auto-scoperta guidata", se vuoi. Ma , come programmatore professionista, trascorri il tuo tempo non tanto su questo tipo di pensiero e di problem solving quanto fai ricerche, googlando e chiedendo in giro finché non trovi qualcosa.

2. Esistono sicuramente modi più efficienti per farlo. È una decisione personale da parte tua se vuoi capire il più possibile da solo o cercare altri modi. La mia raccomandazione? Il primo, poi l'altro.