Table des matières
Le programme à réaliser doit calculer le produit des nombres de 1 à n . La valeur de n est saisie par l’utilisateur du programme.
Pour n égale à 5 la valeur à calculer est (5*4*3*2*1) qui correspond à 120.
Les variables utilisées sont :
Les données du programme sont accessibles sur https://algotouch.irisa.fr/agt/
Define Mult From produit = 1 ; Read "Read n " n ; // ... Until n <= 1 // ... Loop produit = produit * n ; n = n - 1 ; // ... Terminate Write "Valeur de produit " produit ; // ... EndLes programmes est sur https://algotouch.irisa.fr/agt/
somme = 5 + 4 + 3 + 2 + 1 = 15En fonction de la valeur de n le résultat n’est pas le même. Pour réaliser ce programme, il est nécessaire d’utiliser une nouvelle structure de programmation appelée l’itération ou la boucle.
somme = somme + n; n = n - 1;Ce bloc est exécuté 5 fois. Cette valeur correspond à la valeur initiale de n qui vaut 5. Évidemment, si cette valeur est à 3, le bloc est exécuté 3 fois. Et, enfin, si la valeur initiale de n est négative, le bloc ne s'exécute pas.
Certains problèmes nécessitent d’effectuer plusieurs fois la « même » séquence d’opérations. Avec un ordinateur, cette séquence peut s’exécuter des dizaines de fois, des milliers de fois ou des millions de fois. On dit que cette séquence s’exécute en boucle. On l’appelle donc une boucle. On utilise aussi le terme itération. Pour gérer correctement une boucle:
de même, il faut savoir comment commencer;
La structure de la boucle, inspirée du langage Eiffel, est divisée en 4 parties:
MacroExemple From // ... Until // ... Loop // ... Terminate // ...
Une boucle se construit généralement, étape par étape, dans l’ordre suivant :
Nous utiliserons l’exemple de la somme des n premiers nombres entiers pour illustrer ce principe.
Repérer la séquence d’instructions qui se répète et l’exécuter à la main jusqu’à obtenir le résultat voulu:
Dans la console la séquence suivante se répète :
somme = somme + n ; n = n - 1 ;
Une fois le cas général trouvé, en l’occurrence l’addition de n à somme et la soustraction de 1 à n , l’utilisateur enregistre la séquence dans la section Loop .
Il peut ensuite répéter en exécutant la séquence précédemment enregistrée pour vérifier son bon fonctionnement.
n == 0Sans entrer dans le détail, l’utilisateur peut choisir une meilleure condition avec:
n <= 0
somme = 0 ; Read "Read n" n ;Quand le programmeur est sûr de son code, il enregistre le bloc From .
Write "Valeur de somme " somme ;A ce niveau le programme est complet.
Le programme correspondant à l’exemple est donné ci-dessous. Il est bien divisé en quatre parties :
Il reste à voir comment ce programme est exécuté. Nous le verrons en examinant tour à tour l’exécution de chaque bloc.
From somme = 0 ; Read "Read n " n ; // ... Until n <= 0 // ... Loop somme = somme + n; n = n - 1 ; // ... Terminate Write "Valeur de somme " somme ; // ...
Soit une variable x représentant un nombre, et n une variable représentant un entier positif ou nul. L’objectif de cet exercice est de calculer et d’afficher la valeur de x exposant n , soit xn.
Attention, par définition, si n vaut 0, x puissance 0 vaut 1.
Par exemple si x vaut 2 et n vaut 5, x exposant n vaut 2*2*2*2*2 soit 32.
Les données du programme sont disponibles sur https://algotouch.irisa.fr/agt/
Define Puissance From Read "Read x " x ; Read "Read n " n ; exp = 1 ; // ... Until n <= 0 // ... Loop exp = exp * x ; n = n - 1 ; // ... Terminate Write "Valeur de exp " exp ; // ... EndLe programme complet est disponible sur https://algotouch.irisa.fr/agt/
Define PGCD
From
Read "Read p " p ;
Read "Read q " q ;
// ...
Until
p == q
// ...
Loop
if (p < q) {
q = q - p ;
}
else {
// p >= q
p = p - q ;
}
// ...
Terminate
Write "PGCD : " p ;
// ...
End
Le programme est disponible sur https://algotouch.irisa.fr/agt/
Certains algorithmes itératifs nécessitent une boucle avec plusieurs sorties. C’est le cas de l’algorithme qui détermine si un entier est un nombre premier. Un nombre premier est divisible uniquement par deux nombres 1 et lui-même.
Par exemple 13 est un nombre premier. Il n’est divisible ni par 2, ni par 3, ni par 5, ni par 6. Seuls 1 et 13 divisent 13. Il n’est pas utile de vérifier la divisibilité de 13 par 7 et les entiers suivants car 2 fois 7 est supérieur à 13.
Par contre 35 n’est pas un nombre premier car 35 est divisible par 5 et 7, pas uniquement par 1 et 35.
– Vérifier les liens de cette partie
Le programme utilise 5 variables:
Deux cas sont à considérer:
Il est possible de commencer par l’un ou l’autre de ces cas. C’est le premier qui est considéré dans cette partie.
Les actions à réaliser sont :
reste = n % i ;
if (reste != 0) { }
i = i + 1 ;
Quand i a atteint la moitié de n , il faut sortir du corps de boucle:
i >= moitie
Define Premier
From
// ...
Until
i >= moitie
// ...
Loop
reste = n % i ;
if (reste != 0) {
i = i + 1 ;
}
else {
// reste == 0
// TO DO
}
// ...
Terminate
// ...
End
C’est le cas d’un nombre qui n’est pas premier qui est considéré dans cette partie.
Après plusieurs exécution du corps de boucle, AlgoTouch détecte que le reste de la division de n par i est à 0, il indique que ce cas est manquant. Il faut alors associer une action à ce cas manquant.
La seule action à réaliser est positionner premier à 0, pour indiquer que le nombre n n’est pas premier:
premier = 0 ;
Il faut également ajouter une condition de sortie car le programme a détecté que le nombre n n’est pas premier:
premier == 0
Define Premier
From
// ...
Until
i >= moitie
reste == 0
// ...
Loop
reste = n % i ;
if (reste != 0) {
i = i + 1 ;
}
else {
// reste == 0
premier = 0 ;
}
// ...
Terminate
// ...
End
Quand le corps de boucle et les conditions de sortie sont complets, il faut considérer l’initialisation:
Read "Read n " n ;
moitie = n / 2 ;
i = 2 ;
if (n > 1) {
premier = 1 ;
}
else {
// n <= 1
premier = 0 ;
}
Pour la terminaison, le programme se contente d’afficher la valeur de premier .
Write "La valeur de premier " premier ;
Une version plus évoluée peut tester la valeur de premier et afficher un message indiquant si n est premier ou pas.
Define Premier
From
Read "Read n " n ;
moitie = n / 2 ;
i = 2 ;
if (n > 1) {
premier = 1 ;
}
else {
// n <= 1
premier = 0 ;
}
// ...
Until i >= moitie
reste == 0
// ...
Loop
reste = n % i ;
if (reste != 0) {
i = i + 1 ;
}
else {
// reste == 0
premier = 0 ;
}
// ...
Terminate
Write "Valeur de premier " premier ;
// ...
End