Médaille
N°1 pour apprendre & réviser du collège au lycée.
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>b$, et $r$ le reste de la division euclidienne de $a$ par $b$, alors le PGCD de $a$ et $b$ est le même que le PGCD de $b$ et $r$. Ainsi, par divisions euclidiennes successives on arrive à déterminer le PGCD de deux entiers.

Description

Programme

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

Variables

$a$ et $b$ deux entiers entrés par l’utilisateur tels que $a>b$
$r$ un entier calculé par le programme

Algorithme

|demander $a$ et $b$
|$r=$ le reste de la division euclidienne de $a$ par $b$
|tant que $r\not=0$
|$a$ prend la valeur de $b$
|$b$ prend la valeur de $r$
|$r=$ le reste de la division euclidienne de $a$ par $b$
|afficher $b$

Programme TI

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

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

$:\mathsf{A}- \mathsf{ent}\ (\mathsf{A}/ \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R}$

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

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

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

$:\mathsf{A}- \mathsf{ent}\ (\mathsf{A}/ \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R}$ ↵

$:\mathsf{End}$

$:\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 $\mathsf{A}- \mathsf{ent}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R}$ sur un exemple.
Prenons $\mathsf{A}=14$ et $\mathsf{B}=5$ alors :

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

Cours associés

Arithmétique et problèmes de codage