CAML ppcm
mickmac
Messages postés
415
Date d'inscription
Statut
Membre
Dernière intervention
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
Bonjour,
Pour m'entrainer, j'ai essayer de faire un algorithme en caml pour trouver le ppcm de deux nombre. Le voici
let ppcm a b =
(*la fonction récursif diviseur renvoie la liste des diviseurs de a dans l'ordre croissant*)
let rec diviseur a d l =
if (a=>d)||(a mod d =0) then diviseur a (d+1) d::l
else diviseur a (d+1) l in
(*la fonction locale compare regarde si b est divisible avec les diviseurs de a *)
let rec compare b l2 =
match l2 with
[]->b
|x::r-> if(x mod b =0) then x
else compare b r in
if(a<0)||(b<0) failwith("a et b doivent etre positif")
else if (a=b) then a
else if(a=0)||(b=0) then 0
else compare b (diviseur a 1 [])
Est ce juste ? Sinon pourquoi ???
Merci beaucoup
Pour m'entrainer, j'ai essayer de faire un algorithme en caml pour trouver le ppcm de deux nombre. Le voici
let ppcm a b =
(*la fonction récursif diviseur renvoie la liste des diviseurs de a dans l'ordre croissant*)
let rec diviseur a d l =
if (a=>d)||(a mod d =0) then diviseur a (d+1) d::l
else diviseur a (d+1) l in
(*la fonction locale compare regarde si b est divisible avec les diviseurs de a *)
let rec compare b l2 =
match l2 with
[]->b
|x::r-> if(x mod b =0) then x
else compare b r in
if(a<0)||(b<0) failwith("a et b doivent etre positif")
else if (a=b) then a
else if(a=0)||(b=0) then 0
else compare b (diviseur a 1 [])
Est ce juste ? Sinon pourquoi ???
Merci beaucoup
A voir également:
- CAML ppcm
- PPCM et le PGCD - Forum Java
- Fonction ppcm recursive ✓ - Forum Python
- Récursivité ! ✓ - Forum Programmation
3 réponses
pour la mise en page il faut utiliser les balise de code (à côté des boutons gras, italique, souligné)
<code>
Ton code mis en page</code>
Il faudrait que tu testes ton code, a minima pour corriger les erreurs de syntaxe, même si bien sûr il est préférable ensuite de regarder si ça fait bien ce que tu veux !
→ Quelques erreurs simples à corriger :
if (a=>d)||(a mod d =0) → if (a>=d)||(a mod d =0)
if (a<0)||(b<0) failwith → if (a<0)||(b<0) then failwith
→ Erreur plus compliquée :
Contrairement à ce que tu penses, le "::l" ne s'applique pas à "d", mais à tout ce qu'il y a à gauche, c'est à dire "(diviseur a (d+1) d)::l", or ce n'est pas compatible avec l'expression "diviseur a (d+1) l" puisque "l" aurait alors deux types différents.
Il faut donc rajouter des parenthèses sur ton "d::l" pour avoir ce que tu veux.
→ Une fois ces trois erreurs corrigées, ton code est syntaxiquement correct :
Si a=b, on obtient bien le résultat "a"
Si a≠b alors le programme ne s'arrête jamais...
Il faut donc absolument que tu testes chez toi, et que tu corriges ton algorithme.
Remarque : c'est bien la première fois que je vois un algorithme aussi compliqué pour le calcul de ppcm. Normalement on se sert d'une propriété mathématique simple :
→ Quelques erreurs simples à corriger :
if (a=>d)||(a mod d =0) → if (a>=d)||(a mod d =0)
if (a<0)||(b<0) failwith → if (a<0)||(b<0) then failwith
→ Erreur plus compliquée :
let rec diviseur a d l = if (a>=d)||(a mod d =0) then diviseur a (d+1) d::l else diviseur a (d+1) l in
Contrairement à ce que tu penses, le "::l" ne s'applique pas à "d", mais à tout ce qu'il y a à gauche, c'est à dire "(diviseur a (d+1) d)::l", or ce n'est pas compatible avec l'expression "diviseur a (d+1) l" puisque "l" aurait alors deux types différents.
Il faut donc rajouter des parenthèses sur ton "d::l" pour avoir ce que tu veux.
let rec diviseur a d l =
if (a>=d)||(a mod d =0) then diviseur a (d+1) (d::l)
else diviseur a (d+1) l in
→ Une fois ces trois erreurs corrigées, ton code est syntaxiquement correct :
ppcm : int -> int -> int = <fun>Mais sans surprise ça ne fonctionne pas !
Si a=b, on obtient bien le résultat "a"
Si a≠b alors le programme ne s'arrête jamais...
Il faut donc absolument que tu testes chez toi, et que tu corriges ton algorithme.
Remarque : c'est bien la première fois que je vois un algorithme aussi compliqué pour le calcul de ppcm. Normalement on se sert d'une propriété mathématique simple :
a*b = pgcd(a,b)*ppcm(a,b)Le calcul du pgcd s'obtenant facilement grâce à l'algorithme d'Euclide....
Le programme ne s'arrête pas, parce que diviseur appelle toujours diviseur, il n'y a jamais de clause terminale. Donc diviseur appelle diviseur qui appelle diviseur qui ... donc ça s'arrête jamais.
Remarque, au lieu de les imbriquer les unes dans les autres, tu peux mettre tes 3 fonctions au même niveau pour les valider les unes après l'autre.
Donc quand tu as diviseur : int -> int -> int list -> 'a = <fun> c'est évident qu'il y a un problème que vu le type du résultat n'est pas ce que tu attends.
De plus, avec des fonctions indépendantes, tu peux les tracer afin de les déboguer.
Voir Déboguer un programme en Caml
Exemple (simple) de traçage :
Ce qui te donne un affichage comme ça :
Les flèches vers la gauche <-- indiquent que c'est le début de la fonction, les valeurs après sont les paramètres d'entrée, et pour les flèches vers la droite --> indiquent que c'est la fin de la fonction, les valeurs indiquées étant les résultats.
Si on fait cela pour tes 3 fonctions indépendantes diviseur, compare et ppcm on aurait ceci.
Remarque : les étoiles permettent de distinguer les fonctions lambda.
Comme je le mettais un peu plus haut, on ne peux jamais sortir de la fonction diviseur (il n'y a jamais de flèche droite pour diviseur**) c'est pour ça que ça ne s'arrête jamais.
Remarque : ta fonction diviseur est censée donnée "la liste des diviseurs de a dans l'ordre croissant". Tu vois bien, outre le fait que ça ne s'arrête jamais, que le résultat n'est pas correct, car ici a=5, et [5; 4; 3; 2; 1] n'est ni la liste des diviseurs de 5, ni une liste en ordre croissant...
Il y a donc beaucoup de chose à revoir dans ton code, mais il faut que tu le testes chez toi pour le déboguer, tu ne peux pas faire ça de tête.
Remarque, au lieu de les imbriquer les unes dans les autres, tu peux mettre tes 3 fonctions au même niveau pour les valider les unes après l'autre.
Donc quand tu as diviseur : int -> int -> int list -> 'a = <fun> c'est évident qu'il y a un problème que vu le type du résultat n'est pas ce que tu attends.
De plus, avec des fonctions indépendantes, tu peux les tracer afin de les déboguer.
Voir Déboguer un programme en Caml
Exemple (simple) de traçage :
let rec factorielle n =
if n>1 then n*factorielle (n-1)
else 1;;
(* en OCaml *)
#trace factorielle;;
(* en Caml Light *)
trace "factorielle";;
factorielle(5);;
Ce qui te donne un affichage comme ça :
factorielle <-- 5 factorielle <-- 4 factorielle <-- 3 factorielle <-- 2 factorielle <-- 1 factorielle --> 1 factorielle --> 2 factorielle --> 6 factorielle --> 24 factorielle --> 120
Les flèches vers la gauche <-- indiquent que c'est le début de la fonction, les valeurs après sont les paramètres d'entrée, et pour les flèches vers la droite --> indiquent que c'est la fin de la fonction, les valeurs indiquées étant les résultats.
Si on fait cela pour tes 3 fonctions indépendantes diviseur, compare et ppcm on aurait ceci.
Remarque : les étoiles permettent de distinguer les fonctions lambda.
ppcm 5 10;; diviseur <-- 5 diviseur --> <fun> diviseur* <-- 1 diviseur* --> <fun> diviseur** <-- [] diviseur <-- 5 diviseur --> <fun> diviseur* <-- 2 diviseur* --> <fun> diviseur** <-- [1] diviseur <-- 5 diviseur --> <fun> diviseur* <-- 3 diviseur* --> <fun> diviseur** <-- [2; 1] diviseur <-- 5 diviseur --> <fun> diviseur* <-- 4 diviseur* --> <fun> diviseur** <-- [3; 2; 1] diviseur <-- 5 diviseur --> <fun> diviseur* <-- 5 diviseur* --> <fun> diviseur** <-- [4; 3; 2; 1] diviseur <-- 5 diviseur --> <fun> diviseur* <-- 6 diviseur* --> <fun> diviseur** <-- [5; 4; 3; 2; 1] diviseur <-- 5 diviseur --> <fun> diviseur* <-- 7 diviseur* --> <fun> diviseur** <-- [5; 4; 3; 2; 1] diviseur <-- 5 diviseur --> <fun> diviseur* <-- 8 diviseur* --> <fun> diviseur** <-- [5; 4; 3; 2; 1] diviseur <-- 5 diviseur --> <fun> diviseur* <-- 9 diviseur* --> <fun> diviseur** <-- [5; 4; 3; 2; 1] diviseur <-- 5 diviseur --> <fun> diviseur* <-- 10 diviseur* --> <fun> diviseur** <-- [5; 4; 3; 2; 1] ...
Comme je le mettais un peu plus haut, on ne peux jamais sortir de la fonction diviseur (il n'y a jamais de flèche droite pour diviseur**) c'est pour ça que ça ne s'arrête jamais.
Remarque : ta fonction diviseur est censée donnée "la liste des diviseurs de a dans l'ordre croissant". Tu vois bien, outre le fait que ça ne s'arrête jamais, que le résultat n'est pas correct, car ici a=5, et [5; 4; 3; 2; 1] n'est ni la liste des diviseurs de 5, ni une liste en ordre croissant...
Il y a donc beaucoup de chose à revoir dans ton code, mais il faut que tu le testes chez toi pour le déboguer, tu ne peux pas faire ça de tête.
