Quelques techniques usuelles
CHAPITRE 6
108
Notez qu’ici, notre programme n’est pas protégé contre une réponse incorrecte de l’utilisateur (valeur négative, nulle, ou même égale à 1). Dans ce cas, il fournirait la valeur 2 !
D’une manière générale, on parle d’itération dès lors qu’à l’intérieur d’une répétition, les
valeurs d’une ou de plusieurs variables évoluent d’une manière qui dépend de leurs valeurs
courantes. On progresse ainsi d’un état initial (valeurs des variables avant l’entrée dans la
répétition) vers un état final (valeurs des variables après la fin des répétitions), en passant par
une succession d’états intermédiaires.
La recherche d’un maximum correspondait à cette définition plus générale de l’itération.
Il faut bien voir que la mise en œuvre d’une itération nécessite de « deviner » les bonnes instructions permettant de progresser d’un état intermédiaire au suivant, le bon état initial et le
bon test d’arrêt. La difficulté peut être très variable suivant la nature du problème à résoudre.
Voici enfin, un dernier exemple d’itération, à savoir le calcul du PGCD de deux entiers par
l’algorithme d’Euclide. Rappelons que si a et b sont deux entiers positifs, on a :
PGCD (a, b) = PGCD (b, a mod b)
ou a mod b désigne le reste de la division entière (euclidienne) de a par b.
L’algorithme d’Euclide consiste à répéter les étapes suivantes :
• calculer r, reste de la division de a par b,
• remplacer a par b et b par r,
jusqu’à ce que r soit nul. Alors, le PGCD cherché est l’actuelle valeur de a.
Voici le programme correspondant. Ici, nous avons supposé que nous ne disposions que de
l’opérateur / de division entière. Pour obtenir le reste de la division de a par b, il faut utiliser
l’expression a - b * (a/b) (certains langages disposent d’un opérateur de « modulo »
qui fournirait directement ce résultat).
entier a, b
// on cherche le PGCD de a et b
entier r
// pour le reste de division
écrire «donnez deux entiers positifs : »
lire a, b
// ici, on ne vérifie pas que a et b sont positifs
répéter
{ r := a - b * (a/b)
// reste de division entière de a par b
a := b ;
b := r ;
}
jusqu’à r = 0
écrire «leur PGCD est : », a
donnez deux entiers positifs : 48 60
leur PGCG est : 12
Calcul du PGCD de deux entiers
CHAPITRE 6
108
Notez qu’ici, notre programme n’est pas protégé contre une réponse incorrecte de l’utilisateur (valeur négative, nulle, ou même égale à 1). Dans ce cas, il fournirait la valeur 2 !
D’une manière générale, on parle d’itération dès lors qu’à l’intérieur d’une répétition, les
valeurs d’une ou de plusieurs variables évoluent d’une manière qui dépend de leurs valeurs
courantes. On progresse ainsi d’un état initial (valeurs des variables avant l’entrée dans la
répétition) vers un état final (valeurs des variables après la fin des répétitions), en passant par
une succession d’états intermédiaires.
La recherche d’un maximum correspondait à cette définition plus générale de l’itération.
Il faut bien voir que la mise en œuvre d’une itération nécessite de « deviner » les bonnes instructions permettant de progresser d’un état intermédiaire au suivant, le bon état initial et le
bon test d’arrêt. La difficulté peut être très variable suivant la nature du problème à résoudre.
Voici enfin, un dernier exemple d’itération, à savoir le calcul du PGCD de deux entiers par
l’algorithme d’Euclide. Rappelons que si a et b sont deux entiers positifs, on a :
PGCD (a, b) = PGCD (b, a mod b)
ou a mod b désigne le reste de la division entière (euclidienne) de a par b.
L’algorithme d’Euclide consiste à répéter les étapes suivantes :
• calculer r, reste de la division de a par b,
• remplacer a par b et b par r,
jusqu’à ce que r soit nul. Alors, le PGCD cherché est l’actuelle valeur de a.
Voici le programme correspondant. Ici, nous avons supposé que nous ne disposions que de
l’opérateur / de division entière. Pour obtenir le reste de la division de a par b, il faut utiliser
l’expression a - b * (a/b) (certains langages disposent d’un opérateur de « modulo »
qui fournirait directement ce résultat).
entier a, b
// on cherche le PGCD de a et b
entier r
// pour le reste de division
écrire «donnez deux entiers positifs : »
lire a, b
// ici, on ne vérifie pas que a et b sont positifs
répéter
{ r := a - b * (a/b)
// reste de division entière de a par b
a := b ;
b := r ;
}
jusqu’à r = 0
écrire «leur PGCD est : », a
donnez deux entiers positifs : 48 60
leur PGCG est : 12
Calcul du PGCD de deux entiers