Eccoci.

Even Fibonacci Numbers

ℹ️Published on Friday, 19th October 2001, 06:00 pm; Solved by 816498;
Difficulty rating: 5%

Problem 2

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, \dots$$

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Soluzione

Qui l'idea è di generare, in qualche modo, in numeri di Fibonacci fino a quattro milioni, e filtrare quelli pari per sommarli ad S. La parte interessante è come generare i numeri della sequenza di Fibonacci: un primo modo è di aggiornarli in place, cioè direttamente nel codice, come fa la linea fibs[1], fibs[2] = sum(fibs), fibs[1]. Altrimenti potremmo affidarci a delle funzioni, che calcolano l'\(n\)-esimo numero di Fibonacci. La creazione di questa funzione nella forma immediata è molto inefficiente, mentre in quella veloce è ottimizzata conservando i valori creati e richiamandoli per i futuri calcoli.

S = 0
fibs = [2 1]
while fibs[1] <= 4_000_000
	if iseven(fibs[1])
		global S += fibs[1]
	end
	fibs[1], fibs[2] = sum(fibs), fibs[1]
end
@show S

S = 4613732

Se volessimo invece appoggiarci a delle funzioni, per generare i numeri della sequenza, queste sarebbero due possibili definizioni (scritte in forma didattica, con le varie print e il parametro depth per mostrare cosa accade materialmente quando le eseguiamo):

function fib_naive(n, depth = 0)
    println("| "^depth * "calcolo F($n)")
    n <= 2 && return n
    return fib_naive(n-1, depth + 1) + fib_naive(n-2, depth + 1)
end
fib_naive(7)

calcolo F(7)
| calcolo F(6)
| | calcolo F(5)
| | | calcolo F(4)
| | | | calcolo F(3)
| | | | | calcolo F(2)
| | | | | calcolo F(1)
| | | | calcolo F(2)
| | | calcolo F(3)
| | | | calcolo F(2)
| | | | calcolo F(1)
| | calcolo F(4)
| | | calcolo F(3)
| | | | calcolo F(2)
| | | | calcolo F(1)
| | | calcolo F(2)
| calcolo F(5)
| | calcolo F(4)
| | | calcolo F(3)
| | | | calcolo F(2)
| | | | calcolo F(1)
| | | calcolo F(2)
| | calcolo F(3)
| | | calcolo F(2)
| | | calcolo F(1)
21

function fib_smart(n, memo = Dict{Int,Int}(), depth = 0)
    println("| "^depth * "calcolo F($n)")
    n <= 2 && return n
    if haskey(memo, n)
        println("| "^depth * "ce l'avevo già salvato!")
        return memo[n]
    else
        memo[n-1] = fib_smart(n-1, memo, depth + 1)
        memo[n-2] = fib_smart(n-2, memo, depth + 1)
    end
    return memo[n-1] + memo[n-2]
end
fib_smart(7)

calcolo F(7)
| calcolo F(6)
| | calcolo F(5)
| | | calcolo F(4)
| | | | calcolo F(3)
| | | | | calcolo F(2)
| | | | | calcolo F(1)
| | | | calcolo F(2)
| | | calcolo F(3)
| | | ce l'avevo già salvato!
| | calcolo F(4)
| | ce l'avevo già salvato!
| calcolo F(5)
| ce l'avevo già salvato!
21