Contenu | Rechercher | Menus

Annonce

Ubuntu 16.04 LTS
Commandez vos DVD et clés USB Ubuntu-fr !

Pour en savoir un peu plus sur l'équipe du forum.

Appel à contributeurs pour la doc.

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

#1 Le 14/07/2017, à 14:35

Typheonn

[Résolu] Algorithme de Fibonacci en Caml

Bonjour.

Je ne vois pas de quelle manière l'algorithme ci-dessous arrive à calculer le terme demander de la suite de fibonacci :

let fibonacci n=
	let rec fibonacci_aux n acc1 acc2 = match n with
		|0 -> acc1
		|1 -> acc2
		|_ -> fibonacci_aux (n-1) acc2 (acc1+acc2)
	in fibonacci_aux n 1 1
;;

Pourriez vous m'aider s'il vous plaît, merci d'avance.

Dernière modification par Typheonn (Le 16/07/2017, à 17:11)

Hors ligne

#2 Le 15/07/2017, à 17:08

ublender

Re : [Résolu] Algorithme de Fibonacci en Caml

Bonjour,

Je ne connais pas le Caml mais le calcul du terme demandé de la suite se fait par récurrence, c'est d'ailleurs comme ça que la suite de Fibonacci est définie:
u_(n+2)=u_(n+1)+u_(n)
avec les valeurs initiales
u_0=1
u_1=1

Ici, u_0, c'est acc1 et u_1, c'est acc2 (ce sont aussi des variables dans la fonction, ces deux valeurs varient donc)

Ici, on calcule les termes de la suite de cette manière: on garde les deux derniers termes calculés (u_k et u_(k+1)), à partir de ça, on peut calculer u_(k+2) (puisque c'est la somme). Pour le calcul du terme suivant, on a simplement besoin de garder u_(k+1) et u_(k+2), u_k ne nous est plus utile. Au final, on ne garde que deux éléments.

Je te conseille de calculer à la main les termes de la suite de Fibonacci.

Hors ligne

#3 Le 15/07/2017, à 17:20

Roschan

Re : [Résolu] Algorithme de Fibonacci en Caml

Le Caml c'est toujours très bizarre parce que je comprends comment marcherait le code mais je suis incapable de l'expliquer. Tu as des notions en Caml déjà ? Le pattern matching et l'ordre supérieur, ça te parle où il faut l'expliquer aussi ?

En ligne

#4 Le 16/07/2017, à 17:08

Typheonn

Re : [Résolu] Algorithme de Fibonacci en Caml

Bonjour.

Merci ublender pour tes explications, j'ai compris son fonctionnement.

Merci à toi aussi Roschan pour ta réponse. Je maîtrise les bases du langage. Il n'y a que l'algorithme qui me posait problème.

Hors ligne