Iterations

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.

Exécution détaillée de l’exemple

Au début du programme, somme est initialisé à 0 et n prend la valeur saisie par l’utilisateur.
somme vaut 0 et n vaut 5
Lors de l’exécution pas à pas du programme, les variables somme et n prennent les valeurs suivantes :
somme vaut 5 et n vaut 4
somme vaut 9 et n vaut 3
somme vaut 12 et n vaut 2
somme vaut 14 et n vaut 1
somme vaut 15 et n vaut 0
A la fin, la valeur de somme (15) est affichée.

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.

Sous Algotouch 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 à 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 condition supérieure 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 :
Read "Read n" n ;
somme = 0;
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  "La valeur de somme" somme ;
A ce niveau le programme est complet.

Programme complet

Le programme correspondant à l’exemple est donné ci-contre. 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
   Read n;
   somme = 0;

Until
   (0>=n)

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

Terminate
   Write  "La valeur de somme" somme ;

Exercices

Produit des nombres de 1 à n

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 soit : 120.   Les variables utilisées sont :
  • n
  • produit : le résultat du calcul
La version de base de ce programme est dans le fichier produitBase.alg
[embedyt]https://youtu.be/vqBzVu71GNY [/embedyt]
Define Main
From
   produit = 1 ;
   Read  "Read n" n ;
Until
    (n <= 1) 
Loop
   produit = produit * n ;
   n = n - 1 ;

Terminate

End
Source AlgoTouch de la solution : Produit.alg

Calcul de la puissance

Soit x une variable 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 3 et n vaut 5, x exposant n vaut 3*3*3*3*3 soit 243. Source AlgoTouch : Puissance.alg
[embedyt] https://youtu.be/Y__CEM_MXWU[/embedyt]

Solution en AlgoTouch Puissance.alg

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  "La valeur de la puissance est " exp ;
End
Source Algotouch de la solution : Puissance.alg

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. Source AlgoTouch : PGCD
[embedyt]https://youtu.be/wcHICcadoIE[/embedyt] Solution en AlgoTouch : PGCD
Define PGCD
    From
    Read "x :" x ;
    Read "y :" y ;
Until
    (x == y)
Loop
    if (x < y) { 
        y = y - x ;
    } else { // x >= y
        x = x - y ;
    }
Terminate
    Write "Le PGCD est : " x ;
End
Source AlgoTouch : PGCD

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 :
  • nb : le nombre à tester,
  • i : le diviseur de nb. Si la reste de la division de nb par i est 0, nb est divisible par i, et donc nb n’est pas un nombre premier,
  • reste : le reste de la division de nb par i
  • premier : à la fin du programme, premier vaut 1 si le nombre est premier et 0 sinon,
  • double : qui contient le double de la valeur de i.

Cas général et conditions d’arrêt

Le corps de la boucle est :
Loop
    reste = nb % i ;
    if (reste != 0) {
      i = i + 1 ;
      double = i + i ;
    }
    else {
      // reste == 0
      premier = 0 ;
    }
Et les deux conditions d’arrêt :
  • premier == 0 : le nombre n’est pas premier
  • nb < double : le nombre est premier

Initialisation et terminaison

L’initialisation est :
    Read "Read nb" nb ;
    i = 2 ;
    premier = 1 ;
Et la terminaison :
    Write "La valeur de premier" 
           premier ;