Pratique sur les boucles : Afficher les multiples d'un nombre

Énoncé 

Ecrire un algorithme qui affiche le nombre des entiers qui sont des multiples de 3 et inférieur à un nombre n donné par l'utilisateur.

Solution(s)

Plusieurs solutions peuvent être données. Il s'agit d'un autre exercice très classique pour commencer avec les boucles.

Premièrement, nous pouvons voir qu'il y a une borne supérieure à ne pas dépasser. Cela veut dire que le nombre d'itérations est connu et la boucle "Pour" peut être utilisée (toute boucle peut être écrite sous la forme Tant Que).

Ainsi, la solution la plus simple et la plus intuitive sera composée de :

• Une boucle qui parcours les valeurs jusqu'à n,
• Une structure conditionnelle pour vérifier est ce qu'il s'agit d'un multiple de 3 pour l'afficher.

En Pascal :

Program AfficherMultiples3;

Var 
 n, i : Integer;

Begin
 
 WriteLn('Faites entrer la limite n :');
 ReadLn(n);
 
 For i := 0 to n Do
  If (i mod 3 = 0) Then
  WriteLn(i, ' est un multiple de 3');
  
 ReadLn;
 
 
End.

En Java :

import java.util.Scanner;

public class AfficherMultiples3 {
 
 public static void main (String args[]) {
  
  System.out.println("(Java) Faites entrer la limite n :");
  
  Scanner entree = new Scanner(System.in);
  int n = entree.nextInt();
  
  for(int i = 0; i <= n; i++)
   if(i % 3 == 0)
    System.out.println(i + " est un multiple de 3");
  
 }
 
}

Le résultat d'exécution est exactement le même pour les deux codes :

D'habitude, l'étape suivante est de montrer que même avec ce petit code, on arrive à l'optimiser. En effet, pourquoi parcourir toutes les valeurs et faire le test pour chaque valeur. Il est possible de ne parcourir que les valeurs désirées, c'est à dire, il est possible de parcourir les multiples de 3 seulement. L'idée réside dans le pas effectué par la boucle Pour à chaque itération.

En Pascal (j'utilise fpc qui ne supporte pas des pas dans la boucles For, alors je suis obligé de passer à la boucle While):

Program AfficherMultiples3;

Var 
 n, i : Integer;

Begin
 
 WriteLn('Faites entrer la limite n :');
 ReadLn(n);
 
 i := 0;
 While(i <= n)Do
 Begin
  WriteLn(i, ' est un multiple de 3');
  i := i + 3; { Le compteur change par 3 à chaque fois }
 End;
  
 ReadLn;
 
 
End.

En Java :

import java.util.Scanner;

public class AfficherMultiples3 {
 
 public static void main (String args[]) {
  
  System.out.println("(Java) Faites entrer la limite n :");
  
  Scanner entree = new Scanner(System.in);
  int n = entree.nextInt();
  
  for(int i = 0; i <= n; i+=3 /* le pas est 3 */)
   System.out.println(i + " est un multiple de 3");
  
 }
 
}

Ces deux codes donnent exactement les mêmes résultats mais dans un temps d'exécution plus court.

Afficher tous les nombres premiers inférieurs à un nombre donné

Enoncé
Ecrire un programme qui lit un entier n et affiche tous les nombres premiers inférieurs à n.

Solution
Dans cet exercice, l'enseignant tente de compliquer les choses pour pousser les étudiants à utiliser une boucle à l'intérieur d'une autre. C'est un autre exercice classique que nous rencontrons dans la majorité des livres d'introduction à l'algorithmique.

Le programme qui vérifie si un nombre donné est premier est expliqué ici.

Tous ce qui reste à faire c'est de parcourir les valeurs inférieurs à "n" et de tester pour chaque nombre est ce qu'il est premier ou pas.

Le code sera ainsi :

Program Premiers;

Var 
 n, i, j : Integer;
 diviseur : Boolean;

Begin
 
 WriteLn('Donnez la limite n : ');
 ReadLn(n);
 
 WriteLn('Les nombres premiers inférieurs à ', n, ' sont : ');
 {Boucle extérieure pour le parcours des valeurs}
 i := 2;
 While (i <= n) Do
 Begin
 
  j := 2;
  diviseur := false;
  
  {Boucle intérieur pour voir est ce que 
   la valeur i est un nombre premier}
  While ((j < i) And not(diviseur)) Do
  Begin
   If (i mod j = 0) Then
    diviseur := true
   Else
    j := j + 1;
  End;
  
  If (not(diviseur)) Then
   WriteLn(i);
  
  {Vérification de la valeur suivante}
  i := i + 1;
 End;
 
End.

Triangle d'étoiles

Ennoncé
Ecrire un programme qui lit un entier "n" et affiche par la suite un triangle d'étoiles de hauteur "n". Par exemple, si n = 5, l'affichage sera :
*
**
***
****
*****

Solution
Cet exercice est un autre exercice classique pour aider les apprenants avec les boucles. Le principe pratiqué dans ce cas est le principe des boucles imbriquées (ici). Deux petites différences :

1. La borne supérieure de la boucle est lue à partir du clavier.
2. On affiche des "*" au lieu des indices utilisés dans les boucles.

Code en Pascal :

Program TriangleEtoiles;
 
Var 
 n, i, j : Integer;

Begin
 
 WriteLn('Donnez la hauteur de triangle : ');
 ReadLn(n);
 
 For i := 1 to n do
 Begin
  For j := 1 to i do
   Write('*');
  WriteLn;
 End; 
 
End.

Boucles imbriquées : boucle à l'intérieur d'une autre boucle

Pour ce petit code, je n'ai pas d'énnoncé. Je vais présenter, brièvement, la notion des boucles imbriquées.

Une boucle nous permet de faire un passage sur un ensemble de valeurs (intervalle, valeurs dans un tableau, etc.). Ce passage peut être vu comme le parcours d'une ligne; d'une seule dimension.

Les boucles imbriquées nous permettent de faire un peu plus de cela. Elles nous permettent d'effectuer un parcours dans deux dimensions : pour chaque valeur de la première boucle (boucle extérieure), nous faisons un parcours (passage) entier dans la deuxième boucle (boucle intérieure).

Un code exemple (en Pascal) :

Program ExempleBI;

Const 
 n = 10;
 
Var 
 i, j : Integer;

Begin
 
 For i := 1 to n do
 Begin
  For j := 1 to n do
   Write(j, ' ');
  WriteLn;
 End; 
 
End.

Le résultat d'exécution est :

Le parcours peut ne pas être complet : il se peut que les limites des deux boucles ne soient pas basées sur les mêmes variables :

Program ExempleBI2;

Const 
 n = 9;
 m = 15;
Var 
 i, j : Integer;

Begin
 
 For i := 1 to n do
 Begin
  Write(i, ' : ');
  For j := 1 to m do
   Write(j, ' ');
  WriteLn;
 End; 
 
End.

Il se peut même que la deuxième boucle fait appel à l'indice de la première boucle. Cela veut dire que les passages effectués par la deuxième boucle ne sont pas de même taille, néanmoins, cela ne change pas la structure du programme et cela reste un parcours en deux dimensions. Exemple :

Program ExempleBI3;

Const 
 n = 10;
 
Var 
 i, j : Integer;

Begin
 
 For i := 1 to n do
 Begin
  For j := 1 to i do
   Write(j, ' ');
  WriteLn;
 End; 
 
End.

Extraire les chiffres d'un nombre entier

Exercice
Ecrire un programme qui affiche les chiffres d'un nombre lu à partir du clavier.

Soution
Cet exercice est l'un des exercices classiques. Il vise à donner un exemple de manipulation sur deux éléments :

1. Boucles "Tant que" (while)
2. Extraîre les chiffres d'un nombre.

L'extraction d'un chiffre (une position) dans un nombre n'est pas aussi simple que l'extraction d'une lettre à partir d'une chaîne de caractères; il ne faut pas confondre les deux situations.

Dans le cas d'une chaîne de caractères, nous avons un tableau de caractères. En mémoire, chaque caractère occupe une case (d'un ou de deux octets, selon le langage et la plate-forme). Ainsi, il suffit de connaître la position d'un caractère pour l'extraire. Le parcours peut être réalisé avec une boucle "Pour" (connaissant la taille de la chaîne de caractères).

Dans le cas d'un nombre, nous avons une seule valeur sauvegarder dans un seul emplacement mémoire (de un, deux, quatre ou huit octets). La valeur est sauvegardée en binaire et les chiffres ne sont pas distingués. Ainsi, connaître la position d'un chiffre de facilite pas son extraction. En effet, il faut faire appel à des calculs pour extraire ce chiffre. Dans ce cas les deux opérations nécessaires sont la division et le modulo.Pour récupérer un chiffre, il faut faire deux choses :

1. Couper le nombre pour rendre le chiffre recherché dans la position des unités. Cela est fait par la division sur une puissance de 10.
2. Extraire le chiffre qui devient (après avoir coupé le nombre) le modulo 10.

Par exemple, si le nombre n = 123456. Pour extraire le troisième chiffre à partir de droite, il faut :

1. Diviser le nombre sur 100 (10^(position - 1)), n devient 1234.
2. Extraire le nombre la module 10, le chiffre extrait sera 4.

Le parcours est beaucoup plus simple parce que on fait des divisions successives sur 10; aucun besoin pour utiliser la fonction puissance de 10.

Il nous reste à signaler deux remarques très importantes :

1. Contrairement à un tableau (ou chaîne de caractères), le parcours se fait de droite à gauche.
2. L'opération détruit la valeur d'origine. Si vous aurez besoin d'utiliser cette valeur plus loin dans le programme alors il faut la sauvegarder dans une variable.

En Pascal :

Program ExtraireChiffres;

Var 
 n, c : Integer;

Begin
 WriteLn('Donnez un nombre entier');
 ReadLn(n);
 
 WriteLn('Ses chiffre (de droite à gauche) sont :');
 While (n > 0) Do
 Begin
     c := n mod 10;
     WriteLn(c);
     n := n div 10;
 End;
End.

En Java :

import java.util.Scanner;

public class ExtraireChiffres {
 
 public static void main (String args[]) {
  
  Scanner s = new Scanner(System.in);
  
  System.out.println("Donnez un nombre entier :");
  int n = s.nextInt();
  
  System.out.println("Ses chiffres sont :");
  while(n > 0){
   System.out.println(n % 10);
   n = n / 10;
  }
  
 }
}

L'exécution est identique pour les deux codes :

La somme des nombres entiers de 1 à N

Enoncé

Ecrire un algorithme qui calcule la somme des nombres entiers de 1 à N.

Plusieurs énoncés proches de celle-ci sont proposées et l’objectif est toujours le même : donner un premier exemple sur l’utilisation des boucles.

Dans cet article, nous allons voir cet exemple en se concentrant sur trois points essentiels :

1. L’utilité des boucles, qui est l’objectif principal de l’exercice.
2. L’exercice cache deux problèmes en un; faisons la séparation.
3. L’exercice nous “force” à choisir la solution informatique au lieu de la solution mathématique.

Les boucles font partie des structures de contrôle. C’est à dire, elles visent à modifier l’enchaînement d’exécution des instructions en forçant l’ordinateur à ré-exécuter les mêmes instructions plusieurs fois. La forme simple est-ce que nous appelons la boucle Pour. Cette forme est utilisée lorsque nous connaissons combien de fois le code sera exécuté. Sans ces boucles, nous serons obliger de copier/coller le code autant de fois que nécessaire et il sera impossible de créer modifier le nombre de fois à l'exécution. La puissance du calcul (des milliards d'opérations par seconde) sera vraiment difficile à exploiter.

Un point essentiel dans cette forme est le compteur. Si nous connaissons l'intervalle ou le nombre de répétitions, il nous faut un compteur pour se rappeler de combien de fois avons nous déjà exécuter le bloc de la boucle.

C'est comme lorsque je vous demande de compter le nombre de billes (par exemple) dans un sac. Vous allez être obligé de se rappeler du nombre de billes que vous avez déjà compter; si vous oubliez ce nombre, vous serez obligé de recommencer depuis le début.

Se rappeler en algorithmique est synonyme de "variable" : une zone mémoire où nous pouvons stocker une information. Ainsi, ce compteur doit être une variable déclarée de type entier (qui peut être incrémentée).

Ainsi, un premier exemple sera en Pascal :

Program ExempleBoucle;  
Var 
           i : Integer;  
Begin  
           For i:= 1 to 10 Do  
                     WriteLn('Bonjour'); 
End.

Si la boucle contient une seule instruction alors le "Begin" et "End" ne deviennent plus nécessaires. Dans le cas contraire, vous devez informer le compilateur des instructions à répéter et il faut les séparer d'autres instructions qui viennent après la boucle, ainsi, le "Begin" et "End" deviennent obligatoires.

L'objectif de cet premier exemple est de vous montrer le mot "Bonjour" affiché dix (10) fois comme prévu. A chaque fois, le compteur "i" est incrémenté par un, ainsi, le programme se rappelle du nombre de répétition et est-ce qu'il aterminé l'exécution ou pas. IL N'EST PAS OBLIGATOIRE D'UTILISER LE COMPTEUR "i" A L'INTERIEUR DE LA BOUCLE, son rôle principal est de compter le nombre de fois seulement.

Néanmoins, nous pouvons voir que ses valeurs consécutives sont intéressantes pour le problème que nous tentons de résoudre :

Program ExempleBoucle;  
Var 
              i : Integer;  
Begin  
              For i:= 1 to 10 Do  
                            WriteLn('Valeur actuelle de i : ', i); 
End.

En effet, notre objectif est de calculer la somme : 1 + 2 + 3 + ... + N.
Cela ressemble aux valeurs de i dans sa boucle. Mais, il faut se rappeler que "i" ne prend pas toutes ces valeurs à la fois; il ne peut prendre qu'une seule valeur à la fois. Ces valeurs sont prises par "i" à travers les différentes itérations dans la boucle. Ainsi, à chaque itération, nous devons ajouter la valeur à la somme et attendre la prochaine itération pour obtenir une autre valeur (la valeur suivante) et ainsi de suite jusqu'à la fin de la boucle. Ainsi, la solution de l'exercise sera tout simplement :

Program ExempleBoucle;
Var
 i, n, somme : Integer;
Begin
        ReadLn(n);
 somme := 0;
 For i:= 1 to n Do
  somme := somme + i;
 WriteLn(somme);
End.

P. S. : Vous pouvez voir que l'affiche de la somme n'est exécuté qu'une seule fois. Sans un Begin et End le compilateur ne prend qu'une seule instruction comme bloc de la boucle.

La chose à ne pas faire 

Certains étudiants propose la solution suivante :

Program ExempleBoucle;
Var
 i, n, s : Integer;
Begin
        ReadLn(n);
 s := ((1 + n) * n) div 2;
 WriteLn(s);
End.

Nous pouvons exécuter cette solution et voir qu'elle donne exactement les même valeur (15 pour 5 et 55 pour 10) :

 

Néanmoins, pour un informaticien, cette solution est tout simplement fausse : c'est une solution d'un mathématicien. En effet, vous avez fait le calcul à la place de l'ordinateur. Si cela est facile pour l'exemple traité, cela ne sera pas toujours le cas; vous allez faire des calculs ou essayer de prouver des théorèmes pour simplifier les calculs au lieu de laisser la main à l'ordinateur avec sa puissance pour faire les calculs à votre place.

Si vous arriverez à séparer entre l'approche mathématique et l'approche algorithmique, cela sera un premier pas vers une meilleure compréhension de plusieurs problèmes en algorithmique et une meilleure utilisation de la puissance de votre ordinateur.