Médaille
N°1 pour apprendre & réviser du collège au lycée.
Marianne

Conforme au programme
officiel 2018 - 2019

Algorithme d’Euclide : rechercher le PGCD de deux entiers naturels a et b - TI
Algorithme

Type de calculatrice

TI

Prérequis

L’algorithme d’Euclide repose sur le principe de la division euclidienne : soient deux entiers a>ba>b, et rr le reste de la division euclidienne de aa par bb, alors le PGCD de aa et bb est le même que le PGCD de bb et rr. Ainsi, par divisions euclidiennes successives on arrive à déterminer le PGCD de deux entiers.

Description

Programme

Le programme prend deux entiers a>ba>b et effectue la division de aa par bb, de reste rr, ensuite aa prend la valeur de bb, et bb prend la valeur de rr, la boucle est répétée tant que r=0r\not=0. Alors la valeur de bb est le PGCD recherché.

Variables

aa et bb deux entiers entrés par l’utilisateur tels que a>ba>b
rr un entier calculé par le programme

Algorithme

|demander aa et bb
|r=r= le reste de la division euclidienne de aa par bb
|tant que r=0r\not=0
|aa prend la valeur de bb
|bb prend la valeur de rr
|r=r= le reste de la division euclidienne de aa par bb
|afficher bb

Programme TI

:PromptA:\mathsf{Prompt} \rightarrow \mathsf{A}

:PromptB:\mathsf{Prompt} \rightarrow \mathsf{B}

:Aent (A/B)×BR:\mathsf{A}- \mathsf{ent}\ (\mathsf{A}/ \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R}

:While R=0:\mathsf{While}\ \mathsf{R}\not= 0

:BA:\mathsf{B}\rightarrow \mathsf{A}

:RB: \mathsf{R}\rightarrow \mathsf{B}

:Aent (A/B)×BR:\mathsf{A}- \mathsf{ent}\ (\mathsf{A}/ \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R}

:End:\mathsf{End}

:Disp B:\mathsf{Disp}\ \mathsf{B}

prgmentrer « Prompt » alphamath « A » entrer

prgmentrer « Prompt » alphaapps « B » entrer

alphamath « A »  - 
math « NUM » entrer « ent( »
alphamath « A » ÷ alphaapps « B » )
 ×  alphaapps « B » sto ➔ «  ➔ » alpha×\times « R » entrer

prgm entrer « While » alpha×\times « R »
2ndemath « ≠ » 0 entrer

alphaapps « B » sto ➔ «  ➔ » alphamath « A » entrer
alpha×\times « R » sto ➔ «  ➔ » alphaapps « B » entrer

alphamath « A »  - 
math « NUM » entrer « ent( »
alphamath « A » ÷ alphaapps « B » )
 ×  alphaapps « B » sto ➔ «  ➔ » alpha×\times « R » entrer

prgm « End » entrer entrer

prgm « Disp » entrer alphaapps « B »

Remarque
Décortiquons l’instruction Aent (A÷B)×BR\mathsf{A}- \mathsf{ent}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R} sur un exemple.
Prenons A=14\mathsf{A}=14 et B=5\mathsf{B}=5 alors :

  • A÷B=2,8\mathsf{A}\div \mathsf{B}=2,8
  • donc ent (A÷B)=2\mathsf{ent}\ (\mathsf{A}\div \mathsf{B})=2
  • donc ent (A÷B)×B=10\mathsf{ent}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B}=10
  • ainsi AInt (A÷B)×B=1410=4\mathsf{A}- \mathsf{Int}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B}=14-10=4, c’est le reste (R\mathsf{R}) de la division euclidienne de 1414 par 55.

Cours associés

Arithmétique et problèmes de codage