Discussion :

[matdu27]

Bonjour,
Je dois écrire une fonction qui donne les n premiers termes de la suite de fibonnaci dans une liste.

Voici ce que j'ai fait pour l'instant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let rec fibo n = 
  match n with
  0 -> [0]
| 1 -> [0 ; 1]
| n -> [fibo(n-1)]::[fibo(n-1)+fibo(n-2)];;

mais je sais que pour "l'etape n" c'est faux... Pouvez vous m'aider ?
Merci.

[gasche]

Tu peux commencer par faire les choses en deux temps:

1) définir la fonction de fibonacci
2) définir une fonction qui utilise fibonacci pour construire la liste

Ensuite on peut mélanger les deux pour obtenir une implémentation plus efficace, mais je ne sais pas si c'est le but de ton exercice. Avoir une implémentation qui marche est un bon premier pas.

Par ailleurs il y a plusieurs erreurs dans ton code:
- ta fonction "fibo" renvoie une liste et tu essaies d'aditionner les résultats de deux appels; c'est sans espoir
- pour concaténer deux listes il faut utiliser (@), pas ::

[matdu27]

Merci, pour la fonction fibonnaci j'ai reussi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let rec fibo = 
  function
  0 -> 0
| 1 -> 1
| n -> (fibo(n-1)) + (fibo(n-2));;

après pour la liste j'ai modifié :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let rec fibo n = 
  match n with
  0 -> [0]
| 1 -> (fibo (n-1))@[1]
| n -> (fibo(n-1))@(fibo(n-2));;

mais sa me renvoie pas la bonne liste..

[gasche]

Tu devrais définir une fonction *différente* qui *appelle* la fonction fibonacci (qui renvoie juste un élément) et qui renvoie une liste. Plus généralement, tu peux définir une fonction "images" telle que "images f n" qui renvoie la liste [f 0; f 1; f 2; ...; f n].

[matdu27]

Tel que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let rec applique f l =
  match l with 
  [] -> []
| ee::ll -> (f ee)::(applique f ll);;

?

[gasche]

Oui sauf que pour obtenir le bon résultat il faudrait fournir en entrée de "applique" la liste [0; 1; ..; n]. Pour "images" on donnerait juste "n".

[matdu27]

Ok donc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let rec images f n =
  match n with 
  0 -> [0]
| 1 -> [1]
| n -> (f n-1)::(images f n);;

[TropMDR]

Est ce que tu as au moins essayé de compiler puis de lancer ta fonction ?

(O)Caml est langage avec un typeur et un interpréteur, ce qui permet rapidement de tester les fonctions. C'est cet interpréteur qui doit te servir d'oracle dans ta façon aléatoire de programmer (je fais une modif au pif, sans vraiment me demander ce que j'essaye de faire, et je "teste"), ce n'est pas ce forum. Dans ce cas là, tu aurais pu lancer la fonction sur 4, tu aurais reçu un message d'erreur, et tu n'aurais donc pas à nous demander "est ce que c'est la bonne solution", puisque de toutes évidences, ça ne l'est pas.

Après, une autre option serait éventuellement de tenter de te poser quelques minutes, et de réfléchir, en français, à ce que tu essayes de faire.

Quelle fonction tentes-tu d'écrire ? Quelle est la description du résultat ?

Puisque tu veux produire une liste, il est probable que tu veuilles écrire une fonction récursive. Comment fait-on le design d'une fonction récursive ?

On se pose les questions suivantes :
- quel est le cas de base (ou quels sont les cas de bases)
- à partir du moment où je sais résoudre le problème pour une valeur de n, comment est ce que je le résouts pour n + 1?

Cherche les solutions à ces deux questions. Décris l'algorithme en français, déroule le sur un exemple, regarde le résultat, et demande toi si c'est exactement ce que tu veux (par exemple, les nombres sont-il dans le bon ordre).

Et tu pourras alors revenir ici soit avec une solution qui marche, soit avec des vraies questions, du genre "j'ai essayé de donner telle et telle réponse au problème, mais j'ai été confronté à tel et tel problème, que je n'ai pas su résoudre pour telle et telle raison". Pas juste un "ça ?"

Maintenant, bon courage

[gorgonite]

bon allez, je me lance... mais ça risque de te donner la réponse un peu trop sur un plateau à mon goût

en gros, la suite de fibonacci répond aux critères suivants :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
fibo(0) = 0
fibo(1) = 1
pour tout n >= 2, fibo(n) = fibo(n-1) + fibo(n-2)

maintenant tu veux le debut de la suite de fibonacci jusqu'au n-ième élément, ce qui donne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
fibo(0) = [ 0 ]
fibo(1) = [ 0 ; 1 ]
pour tout n >= 2, fibo(n) = fibo(n-1) @ [ dernier élement de  fibo(n-1) + dernier élement de  fibo(n-2) ]

mais par miracle, le dernier élément de fibo(n-2) est aussi l'avant-dernier élément de fibo(n-1)
(preuve laissée en exercice au lecteur... )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
fibo(0) = [ 0 ]
fibo(1) = [ 0 ; 1 ]
pour tout n >= 2, fibo(n) = fibo(n-1) @ [ dernier élement de  fibo(n-1) + avant-dernier élement de  fibo(n-1) ]

et là, on voit vite que les listes ne seront pas bien gérées puisqu'on ajoute à la fin... je propose donc de travailler sur la version à l'envers... plus proche du fonctionnement des listes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
fibo(0) = [ 0 ]
fibo(1) = [ 1 ; 0 ]
pour tout n >= 2, fibo(n) = ( premier élement de  fibo(n-1) + second élement de  fibo(n-1) ) :: fibo(n-1)

on voit qu'il y a un appel à fibo(n-1), donc inutile de le répéter 2 fois (ce qui au passage est une erreur classique de débutant en récursivité transformant des algo de complexité log(n) en algo de complexité n*log(n) )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
fibo(0) = [ 0 ]
fibo(1) = [ 1 ; 0 ]
pour tout n >= 2, 
  resultat = fibo(n-1)
  fibo(n) = ( premier élement de  resultat + second élement de resultat ) :: resultat

maintenant, donnes moi le code correspondant...


EDIT: si tu connais ce qu'est la programmation dynamique à partir de la forme ci-dessus, donnes nous la taille maximale du tableau à allouer pour calculer un élement de la suite de fibonacci par programmation dynamique. Puis donnes nous l'algorithme (et le code ^^) correspondant

[matdu27]

Je te remercie pour ta réponse !
Alors j'ai fait sa :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let rec fibo n =
  match n with
  0 -> [0]
| 1 -> [1; 0]
| n -> (e::fibo(n-1)+e::f::fibo(n-2))::(fibo(n-1));;

mais sa ne marche pas car sa me dit que (e::fibo(n-1)+e::f:::fibo(n-2)) est de type 'a list et qu'il devrait etre de type int... je pensai qu'avec le "+" sa ne pouvait etre que du int...

[TropMDR]

Je te remercie pour ta réponse !
Alors j'ai fait sa :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let rec fibo n =
  match n with
  0 -> [0]
| 1 -> [1; 0]
| n -> (e::fibo(n-1)+e::f::fibo(n-2))::(fibo(n-1));;

mais sa ne marche pas car sa me dit que (e::fibo(n-1)+e::f:::fibo(n-2)) est de type 'a list et qu'il devrait etre de type int... je pensai qu'avec le "+" sa ne pouvait etre que du int...

Est ce que tu peux expliquer, avec tes propres mots et en français (donc en remplaçant "sa" par "ça" ) ce que tu as compris et ce que tu essayes de faire exactement ?

Et pour essayer de limiter la confusion, disons que l'on appelle "fibo" la fonction de type int -> int qui retourne *une* valeure de la suite de Fibonacci, et fibo_list la fonction de type int -> int list qui retourne les n premières valeurs de la suite. Je pense que ça t'aidera à être moins perdu, et peut être même à résoudre ton problème de typage !

[matdu27]

D'accord je vais regarder sa !
Par contre est ce que le premier élément et le 2e s'écrit bien : e::fibo(n-1) et e::f::fibo(n-2) car je n'ai pas encore vu sa en cours.

[Ptival]

matdu27 : Jette tout ton code, et réfléchis !

Ta question est inappropriée : tu n'as même pas défini e et f, comment veux-tu que ce soit la réponse !?

Tu confonds également les utilisations de :: pour analyser la "forme" d'un paramètre d'entrée, et celle consistant à produire un résultat.

x :: xs représente la liste dont le premier élément est x, et donc le reste des éléments est dénoté xs.
Lorsque tu disposes d'un élément e de type 'a, et d'une liste l de type 'a list, tu peux construire la liste qui débute par e et contient ensuite les éléments de l à l'aide de la notation (x :: l).
Lorsque tu disposes d'une liste l de type 'a list, et que tu souhaites l'examiner afin de savoir si elle est vide ou si elle contient un élément, tu peux le faire à l'aide de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
match l with
| nil     -> ... cas où l est vide ...
| x::xs -> ... cas où l est non vide, son premier élément étant dénoté x et le reste xs ...
end

Par exemple, je peux écrire la fonction change_tete, qui prend un élément e et une liste l, et retourne la même liste mais dont la tête a été remplacée par e (si elle existait) ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
change_tete e l =
  match l with
  | nil     -> nil
  | x::xs -> e::xs
  end

Tu vois ici que les deux occurences de :: n'ont pas la même signification. Le motif x :: xs permet de déconstruire la liste l, afin de séparer la tête de la queue, alors que l'expression e :: xs permet de construire une nouvelle liste.

C'est la "construction syntaxique" match qui te permet de faire cette analyse déconstructive sur une valeur (ici sur l), et le motif x :: xs signifie "si la liste est consitutée d'une tête et d'une sous-liste, retourne ce qui est à droite de la flèche ->, en ayant pris le soin de nommer la tête x et le reste xs".

Ainsi, quand j'ai affaire à une liste non vide, je peux référer, à droite de la flèche ->, à sa tête par le nom x et à sa queue par le nom xs. C'est ce que je fais dans l'expression e :: xs. Puisque je ne me sers que de xs, et pas de x, j'aurais pu écrire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
change_tete e l =
  match l with
  | nil     -> nil
  | _::xs -> e::xs
  end

où le motif _ :: xs indique "si la liste l a une tête et une queue, retourne ce qui est à droite de la flèche, en ayant pris soin de nommer la queue xs" (pas besoin de nommer la tête, je ne vais pas m'en servir).

J'espère qu'avec ces quelques éléments de détails syntaxiques, et en relisant le pseudo-algorithme fourni par gorgonite quelques posts précédemment, tu arrives à écrire une fonction qui soit, si elle n'est pas sémantiquement correcte, au moins syntaxiquement valide.

PS : "je vais regarder sa" -> sois plus attentif à ce qu'on te dit... cf. le dernier post de TropMDR

[matdu27]

Merci à tous, le problème est résolu.

[gorgonite]

penses quand même à mettre ta solution qu'on vérifie/commente... et que les autres visiteurs aient la réponse