Ubuntu-fr

reaver

Programmation de la division euclidienne sur Caml

Bonjour,
Je ne comprend pas le contenu d'un programme qui consiste à calculer la division euclidienne de a par b.
Voilà ce fameux programme.

---------------------
let rec eucl a b =
  if a<b then 0,a
  else let q,r = eucl(a-b) b
  in q+1,r;;
---------------------
Il a l'air simple mais je n'arrive pas à comprendre par quel procédé il réussit à calculer la division !!
Merci d'avance pour vos réponses

Bobbybionic

Re : Programmation de la division euclidienne sur Caml

Bonjour

<Mode dérouille toi en Caml >

let rec eucl a b = // Jusqu'ici ça va, deux arguments, fonctions récursive
  if a<b then 0,a // Si a < b, le quotient est 0 le reste a, normal
  else let q,r = eucl(a-b) b // J'ai un peu oublié comment ça marchait ça, c'est bête...
  in q+1,r;;

</Mode>

Ma mission a échouée

Zut, j'ai pas le temps de me replonger dans le Caml, mais ça m'intéresse, I'll be back !

---

Non à la vente liée. Non au monopole Windows.
Tous ensemble, refusons les logiciels préinstallés et tournons nous vers le libre.

http://bobbybionic.wordpress.com

reaver

Re : Programmation de la division euclidienne sur Caml

hehehe c'est justement cette phrase que je n'ai pas compris

Tom_L

Re : Programmation de la division euclidienne sur Caml

else let q,r = eucl(a-b) b
in q+1,r;;

Suis pas un pro du Caml mais bon:

Si a > b on rapelle la même fonction avec comme argument (a-b) (b), on incrémente un compteur q, le reste est a.

Exemple avec a=10 et b=3
a>b -----> on rapelle la fonction avec a = 7 et b = 3 ; q=1
a>b -----> on rapelle la fonction avec a = 4 et b = 3 ; q=2
a>b -----> on rapelle la fonction avec a = 1 et b = 3 ; q=3
a<b -----> q=3 et le reste a = 1

a=q*b+reste

---

~~~~~~
Thomas.

Freddy

Re : Programmation de la division euclidienne sur Caml

Pour démontrer ce programme, montrons par une récurrence forte sur a entier positif, b étant fixé et strictement positif, que le programme renvoie q,r tels que
a = q×b + r, 0 <= r < b.

Pour a = 0, le programme renvoie 0, 0 et on a bien
a = 0×b + 0, et 0 <= 0 < b.

Soit a entier, on suppose avoir montré que pour tout k entier, k < a, le programme renvoie q, r tels que k = q×b + r, et 0 <= r < b. On va montrer que l'appel « eucl a b » renvoie bien le quotient et le reste de la division euclidienne de a par b.
Permier cas : a < b. Le programme renvoie 0, a, ce qui est bien les nombres voulus.
Deuxième cas : a >= b. On a
a - b < a
donc l'appel
eucl (a - b) b
renvoie (hypothèse de récurrence) q, r vérifiant a - b = q×b + r avec 0 <= r < b.
Donc (q + 1), r sont bien les entiers recherchés : on a
a = (q + 1)×b + r, et 0 <= r < b.
D'où par récurrence la justesse de l'algorithme.
Je ne me souviens plus de la preuve de l'existence des nombres q, r pour la division euclidienne dans Z, mais je pense qu'une simple adaption de cette preuve aurait suffi.

---

There is no system but GNU, and Linux is one of its kernels.

reaver

Re : Programmation de la division euclidienne sur Caml

Ok j'ai bien compris !
mais en quoi le fait de mettre q+1, permet d'afficher la valeur du quotient à la fin sans l'avoir initialiser à 0 ??
Merci bien

reaver

Re : Programmation de la division euclidienne sur Caml

Freddy > il me semble que les preuves de q et r découlent du fait que R est archimédien ! donc on peut considérer l'ensemble {b*q<a/b appartient à N}
On montre que cet ensemble est non vide ( justement la propriété d'archimède) et majoré ... ben ensuite ca coule de source ...