Follow

Dopo aver affrontato con non troppa difficoltà il primo problema, ci prepariamo ad affrontare il secondo. Il testo recita più o meno in questo modo.

Each new term in the Fibonacci sequence is generated by adding
the previous two terms.
By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which
do not exceed four million.

Il nostro compito consiste quindi nel trovare tutti i numeri di Fibonacci minori di 4 milioni, scartare i dispari e sommare i pari. Matematicamente l’algoritmo consiste in:

1. Trovare l’n-esimo numero della successione partendo dal n-1esimo e n-2esimo.
2. Verificare se è pari. Ovvero vedere se il resto della divisione per due è zero.
3. Se è pari, sommarlo alla somma parziale che teniamo da parte.

Useremo per la realizzazione ancora il Python, che trovo il linguaggio più simile allo pseudocodice e quindi più adatto per la descrizione di algoritmi.

L’algoritmo è il seguente:

def sommaPariFibonacci() :
    ultimo = 2
    penultimo = 1
    somma = 2
    while ultimo<4000000 :
        nuovo = ultimo + penultimo
        penultimo = ultimo
        ultimo = nuovo
        if nuovo%2==0 :
            somma = somma + nuovo
    return somma

Ultimo e Penultimo mantengono il valore dei due numeri precedenti, mentre Somma mantiene la somma parziale. Il ciclo while (la cui sintassi è simile agli altri linguaggi) non fa altro che calcolare il nuovo numero della serie e verificare se è pari per sommarlo alla somma parziale.

L’algoritmo è chiaramente in-place e con complessità computazionale pari a O(x) dove x è il numero di elementi della successione di Fibonacci minori del massimo (nel nostro caso 4.000.000), generalmente sub-lineare.

Dalla teoria sulla serie di Fibonacci sappiamo che partendo dal 3° numero (2), il numero di indice 3+2 è pari. In generale il numero di indice 3+2n è sempre pari.

Potremmo sfruttare questa proprietà per ottimizzare il codice?

Si. Bisogna però usare la formula di calcolo diretto dell’n-esimo numero della serie e sommare solo quelli con indice 3+2n. Ma a mio avviso non ne vale la pena perchè il vantaggio computazionale che si ricava non bilancia la maggiore difficoltà realizzativa.