Accueil
Programme Lycée Tle S Cours Mathématiques Algorithme d’Euclide : rechercher le PGCD de deux entiers naturels a et b - TIAlgorithme : Algorithme d’Euclide : rechercher le PGCD de deux entiers naturels a et b - TI
Algorithme d’Euclide : rechercher le PGCD de deux entiers naturels a et b - TI
Si tu es un lycéen en terminale, tu dois déjà avoir planifié tes révisions pour ton baccalauréat 2025. Si ce n’est pas le cas, tu peux te baser sur notre programme de révision en le planifiant en fonction des dates du bac 2025 ou des coefficients des matières … 💪
TI
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.
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}$ |
« Prompt » « A »
« Prompt » « B »
« A »
« NUM » « ent( »
« A » « B »
« B » « ➔ » « R »
« While » « R »
« ≠ »
« B » « ➔ » « A »
« R » « ➔ » « B »
« A »
« NUM » « ent( »
« A » « B »
« B » « ➔ » « R »
« End »
« Disp » « 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$.
Arithmétique et problèmes de codage