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

Algorithme

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

Type de calculatrice

Casio

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

Programme Casio

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

$\mathsf{A}- \mathsf{Int}\ (\mathsf{A}\div \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{Int}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R}$ ↵

$\mathsf{WhileEnd}$

$\mathsf{B}\blacktriangleleft$

SHIFTVARSF4 « ? » ➔ Alpha$X,\theta,T$ « A »
SHIFTVARSF6 « ▷ » F5 « : »
SHIFTVARSF4 « ? » ➔ Alphalog « B » EXE « ↵ »
Alpha$X,\theta,T$ « A » -
OPTNF6 « ▷ » F4 « NUM » F2 « Int »
( Alpha$X,\theta,T$ « A » ÷ Alphalog « B » )
× Alphalog « B » ➔ Alpha6 « R » EXE « ↵ »
SHIFTVARSF1 « COM » F6 « ▷ » F6 « ▷ » F1 « While » Alpha6 « R » SHIFTVARSF6 « ▷ » F3 « REL » F2 « ≠ » 0 EXE « ↵ »
Alphalog « B » ➔ Alpha$X,\theta,T$ « A »
SHIFTVARSF6 « ▷ » F5 « : »
Alpha6 « R » ➔ Alphalog « B » EXE « ↵ »
Alpha$X,\theta,T$ « A » -
OPTNF6 « ▷ » F4 « NUM » F2 « Int »
( Alpha$X,\theta,T$ « A » ÷ Alphalog « B » )
× Alphalog « B » ➔ Alpha6 « R » EXE « ↵ »
SHIFTVARSF1 « COM » F6 « ▷ » F6 « ▷ » F2 « WhileEnd »
EXE « ↵ »
Alphalog « B » SHIFTVARSF5 « ◄ »

Remarque
Décortiquons l’instruction $\mathsf{A}- \mathsf{Int}\ (\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{Int}\ (\mathsf{A}\div \mathsf{B})=2$
donc $\mathsf{Int}\ (\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