Itérations

Exercice d'application

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 à 5 la valeur à calculer est 5*4*3*2*1 soit: 120. Les variables utilisées sont :
  • n : la valeur à saisir par l’utilisateur;
  • produit : le résultat du calcul.
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 ;
  // ...
End
Les programmes est sur https://algotouch.irisa.fr/agt/

Retour sur la notion d'itération

Besoin

Considérons l’exemple qui consiste à calculer la somme des n premiers nombres entiers dans la variable somme . Par exemple, si n vaut 5:
somme = 5 + 4 + 3 + 2 + 1 = 15
En 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.

Notion de boucle

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:
  • il faut arrêter de répéter la séquence à un moment donné, notamment quand le résultat est atteint;
  • de même, il faut savoir comment commencer;
  • parfois, il reste même à effectuer quelques instructions après la boucle pour terminer le calcul.

Boucle AlgoTouch

Pour créer un programme constitué d’une boucle avec AlgoTouch, il faut utiliser une structure différente du bloc Do. On utilise la commande « Macro -> Créer macro boucle ». Dans la zone « Instructions », on constate la création du squelette d’un programme constitué de 4 blocs. L’utilisateur va les remplir progressivement.
La structure de la  boucle, inspirée du langage Eiffel, est divisée en 4 parties:
  • Le premier bloc est dénommé initialisation: From ;
  • l’arrêt est dénommée condition(s) de sortie: Until ;
  • Le bloc à répéter est dénommé corps de boucle: Loop ;
  • Le dernier bloc est dénommé terminaison: Terminate .

Construire une boucle étape par étape

Une boucle se construit généralement, étape par étape, dans l’ordre suivant :
  1. corps de boucle : les instructions à répéter;
  2. conditions de sortie :  les conditions pour lesquelles il  faut arrêter la boucle;
  3. initialisation : les instructions nécessaires pour initialiser les variables avant l’exécution de la boucle;
  4. terminaison : les instructions éventuelles à effectuer à la sortie du corps de boucle.
Nous utiliserons l’exemple de la somme des n premiers nombres entiers pour illustrer ce principe.

Déterminer le cas général

Repérer la séquence d’instructions qui se répète et l’exécuter à la main jusqu’à obtenir le résultat voulu:

  • additionner n à somme ;
  • soustraire 1 à n ;
  • recommencer jusqu’à ce que n soit égal à 0.

Dans la console la séquence suivante se répète :

somme = somme + n ;
n = n - 1 ;

Enregistrer la cas général

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 l’exécutant la séquence précédemment enregistrée pour vérifier son bon fonctionnement.

Déterminer la condition d’arrêt

Immanquablement, la valeur de n arrive à 0. Dans ce cas ce n’est pas la peine de continuer la boucle: ajouter 0 à somme ne changera pas sa valeur et ensuite n passant à -1, le résultat ne sera pas celui attendu. D’ailleurs dans le même temps, l’utilisateur peut constater que le résultat est atteint, la valeur de 15 dans notre exemple. L’utilisateur  peut alors enregistrer une condition de terminaison de la boucle:
n == 0
Sans entrer dans le détail, l’utilisateur peut choisir une meilleure condition avec:
n <= 0

Déterminer l’initialisation

Maintenant que le corps et la condition de sortie sont déterminés, l’utilisateur peut chercher quelles sont les bonnes valeurs initiales pour les deux variables:  n et somme . Pour n , c’est simple, il suffit de demander la valeur à l’utilisateur du programme. Pour somme , la valeur initiale est 0. Dans notre cas le code est :
somme = 0 ;
Read "Read n" n ;
Quand le programmeur est sûr de son code, il enregistre le bloc From .

Déterminer la terminaison

La terminaison (bloc  Terminate) dans ce cas consiste simplement à afficher le résultat obtenu :
Write "Valeur de somme " somme ;
A ce niveau le programme est complet.

Programme complet

Le programme correspondant à l’exemple est donné ci-dessous. Il est bien divisé en quatre parties :

  1. un bloc d’initialisation de la boucle (From);
  2. un bloc d’arrêt de la boucle (Until);
  3. un bloc de corps de la boucle (Loop);
  4. un bloc de terminaison de la boucle (Terminate).

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 ;
  // ...

Exercices

Calcul de la puissance
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 ;
  // ...
End
Le programme complet est disponible sur https://algotouch.irisa.fr/agt/
PGCD - méthode soustractive
Soit deux variables entières x et y . L’objectif de cet exercice est de calculer le Plus Grand Commun Diviseur (PGCD) de x et y . Par exemple, le PGCD de 45 et 60 est 15, car il n’existe pas de plus grand nombre que 15 qui divise à la fois 45 et 60. Pour cet exercice, l’idée est de soustraire le plus petit nombre du grand nombre jusqu’à trouver que les deux nombres soient égaux. Par exemple, pour x=45 et y=60 , après un tour, x=45 et y=15 , après un deuxième tour, x=30 et y=15 , puis après un troisième tour x=15 et y=15 . Comme les valeurs de x et y sont égales, le PGCD est trouvé et vaut 15. Les données du programmes sont disponibles sur https://algotouch.irisa.fr/agt/
<>Le programme 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/

Construire une boucle à plusieurs sorties

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 pas 1 et 35.

Algorithme de calcul

L’algorithme qui permet de déterminer un nombre premier est relativement élémentaire. Pour tester que 13 est premier, il faut réaliser les opérations suivantes:
  1. vérifier si 13 est divisible par 2;
  2. vérifier si 13 est divisible par 3;
  3. vérifier si 13 est divisible par 4;
  4. vérifier si 13 est divisible par 5;
  5. vérifier si 13 est divisible par 6.
Comme ce n’est pas le cas, c’est que 13 est un nombre premier.
Pour tester que 35 n’est pas un nombre premier, il faut effectuer les opérations suivantes:
  1. vérifier si 35 est divisible par 2;
  2. vérifier si 35 est divisible par 3;
  3. vérifier si 35 est divisible par 4;
  4. vérifier si 35 est divisible par 5.
Comme 35 est divisible par 5, ce n’est pas un nombre premier

Variables du programme

Le programme utilise 5 variables:

  • n : le nombre à tester;
  • i : le diviseur de n . Si la reste de la division de n par i est 0, n est divisible par i , et donc n n’est pas un nombre premier;
  • reste : le reste de la division de n par i ;
  • premier : en fin de programme, premier vaut 1 si le nombre n est premier et 0 sinon;
  • moitie : qui contient la moitié de la valeur de n .

Cas d'un nombre premier : corps de boucle et condition d'arrêt

Deux cas sont à considérer:
  • le cas où n est premier;
  • le cas où n n’est pas premier.
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 :
  • calculer le reste de la division de n par i :
    reste = n % i ;
    
  • tester la valeur de reste qui est obligatoirement 1 pour un nombre premier:
    if (reste != 0) { }
    
  • passer à la valeur suivante de i :
    i = i + 1 ;
    
Quand i a atteint la moitié de n , il faut sortir du corps de boucle:
i >= moitie
Le programme est alors :
Define Premier
From
  // ...
Until
  i >= moitie
  // ...
Loop
  reste = n % i ;
  if (reste != 0) {
    i = i + 1 ;
  }
  else {
    // reste == 0
    // TO DO
  }
  // ...
Terminate
  // ...
End

Cas d'un nombre non premier : corps de boucle et condition d'arrêt

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étecteé que le nombre n n’est pas premier:
premier == 0
Le programme devient alors:
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

Initialisation et terminaison

Quand le corps de boucle et les conditions de sortie sont complets, il faut considérer l’initialisation:
  • saisir la valeur de n :
    Read "Read n " n ;
    
  • calculer la moitié de n :
    moitie = n / 2 ;
    
  • initialiser le premier diviseur en mettant i à 2 :
    i = 2 ;
    
  • initialiser premier en tenant compte du fait que 0, 1 et les nombres négatifs ne sont pas premiers:
    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.
Le programme complet est:
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