Somme des nombres de Fibonacci

Question

Je suis plutôt novice en Haskell. Le problème est de trouver la somme de tous les nombres pairs de Fibonacci qui ne sont pas supérieurs à 4 millions. Je ne peux pas utiliser de listes.

Si je comprends bien, la solution ci-dessous est fausse, car elle utilise des listes :

my_sum = sum $ filter (odd) $ takeWhile (< 4000000) fibs

Où fibres est la liste de tous les nombres de Fibonacci.

D'une certaine manière, je trouve difficile de ne pas penser en Haskell en termes de listes. Quelqu'un pourrait-il me guider vers une solution à ce problème ?

Salutations

EDIT :

Si cela intéresse quelqu'un, j'ai résolu ce problème. Voici le code (très maladroit, mais qui fonctionne néanmoins) :

findsum threshold = findsum' 0 1 0 threshold

findsum' n1 n2 accu t 
| n2 > t    = accu
| odd n2    = findsum' n2 n3 accu t 
| otherwise = findsum' n2 n3 accu2 t
where
    n3 = n2 + n1
    accu2 = accu + n2

Answer 1

Vous trouverez peut-être plus facile de construire cela dans Excel et de trouver le code à partir de là. C'est assez facile de le faire dans Excel. Il suffit de mettre 1 dans la première cellule et de mettre 1 juste en dessous. Ensuite, faites en sorte que chaque cellule en dessous additionne les deux au-dessus. (par exemple, la cellule a3 contient =A1+A2). Faites en sorte que la colonne suivante ne contienne que des valeurs paires : "ie, if(mod(a3,2)==0,a3,0)". Ensuite, mettez votre somme courante dans la troisième colonne. Sur cette base, vous devriez être en mesure de trouver la solution récursive.

Une autre façon de procéder est de commencer par le problème. Vous voulez seulement un total qui réclame un accumulateur.

sumFib :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer
sumFib' n1 n2 acc threshold

Vous pouvez voir les signatures de mes fonctions ci-dessus. J'ai construit un joli front-end qui prend un seuil (4.000.000) pour décider quand arrêter de construire des nombres de fibonacci. Puis je passe ce seuil plus les 2 premiers nombres de fibonacci et un accumulateur dans la fonction "sumFib" qui fait la récursion. Et voilà... la réponse, "4613732", sans liste.....

n1 est le nombre de fibonacci n-1 et n2 est le nombre de fibonacci n-2.

J'espère que cela vous aidera.

EDIT : voici ma solution complète :

sumFib :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer
sumFib' n1 n2 acc threshold
     | n1 > threshold = acc
     | otherwise = sumFib' (n2+n1) n1 newAcc threshold
            where newAcc = if n1 `mod` 2 == 0
                               then n1 + acc
                               else acc

Answer 2

Vous pouvez le faire sans liste, avec une solution récursive, en utilisant style de passation en continu .

D'ailleurs, parcourir tous les nombres de Fibonacci et filtrer les nombres impairs est la façon la plus lente de résoudre ce problème.

Answer 3

Encore une fois, un non-exemple de l'utilité des ordinateurs :

Vous pouvez le faire sans ordinateur !

1ère observation : Un nombre de Fibo sur trois est pair, le premier nombre de Fibo pair est F_3=2.

En effet, impair+impair=pair ; impair+impair=impair ; pair+impair=impair, ce qui ferme déjà le cercle.

2ème observation : F_3 + F_6 + F_9 + ... + F_{3k} = 1/2 (F_{3k+2} - 1)

Par induction : F_3 = 2 = 1/2 (5 - 1) = 1/2 (F_5 - 1)

F_3 + F_6 + ... + F_{3k+3} = 1/2 (F_{3k+2} - 1) + F_{3k+3} = 1/2 (F_{3k+2} + 2F_{3k+3} -1) = 1/2 (F_{3k+4} + F_{3k+3} -1) = 1/2 (F_{3k+5} -1)

3ème observation : La somme aura 1333333 sommets, le dernier étant le 3999999ème Fibo-numbre.

4ème observation : F_n = 1/sqrt(5) * (phi^n - (1-phi)^n)

Preuve par Wikipedia

Maintenant, on peut assembler les pièces : F_3 + F_6 + ... + F_3999999 = 1/2 (F_4000001 - 1) = 1/2 1/sqrt(5) (phi^4000001 - (1-phi)^4000001) - 1/2 = int(1/2 1/sqrt(5) phi^4000001)

Ici, int est la partie entière. La dernière étape fonctionne, car -1 < 1-phi < 0 et donc (1-phi)^4000001 disparaît presque. Vous pouvez utiliser une calculatrice pour obtenir une valeur numérique.