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.

BigDecimal : pour les calculs avec une grande précision

La précision du calcul avec les nombres en virgule flottante dépend fortement de la taille (nombre de bits) de ces nombres.
Ainsi, il est très facile de montrer les limites des différents types élémentaires largement utilisés. Par exemple, le code suivant qui utilise le type float :

public class ExempleBigDecimal {
 
 public static void main (String args[]) {
  
  float exemple = (float)34/145;
  System.out.println(exemple);
  
 }
}

Affiche le résultat suivant :

Pour augmenter la précision, il est possible d'utiliser le type double. Le code suivant :

public class ExempleBigDecimal {
 
 public static void main (String args[]) {
  
  double exemple = (double)34/145;
  System.out.println(exemple);
  
 }
}

Donne le résultat suivant :

Les deux résultats sont loin d'être complets et précis. Pour atteindre une précision beaucoup plus supérieure, nous pouvons utiliser les BigDecimal. BigDecimal est une classe du package java.math. Elle permet de créer des nombres avec des grandes précisions et de faire des opérations arithmétiques sur ces nombres. Comme étant une classe, les opérateurs traditionnels (+, -, *, /, %) ne peuvent pas être appliqués directement. Il faut faire recours à des fonctions pour effectuer ces opérations.
Le code suivant fait le même calcul que les deux codes cités ci-dessus. La précision choisie est 20 chiffres après la virgule :

import java.math.BigDecimal;
import java.math.RoundingMode;

public class ExempleBigDecimal {
 
 public static void main (String args[]) {
  
  BigDecimal bd34 = new BigDecimal(34);
  BigDecimal bd145 = new BigDecimal(145);
  BigDecimal result = bd34.divide(bd145, 20, RoundingMode.DOWN);
  System.out.println(result.toPlainString());
  
 }
}

Il affiche le résultat suivant :

Mettons les trois codes ensemble et augmontons la précision à 100 chiffres après la virgule :

import java.math.BigDecimal;
import java.math.RoundingMode;

public class ExempleBigDecimal {
 
 public static void main (String args[]) {
  
  float exemplef = (float)34/145;
  System.out.println("Float      : " + exemplef);
  
  double exempled = (double)34/145;
  System.out.println("Double     : " + exempled);
  
  BigDecimal bd34 = new BigDecimal(34);
  BigDecimal bd145 = new BigDecimal(145);
  BigDecimal result = bd34.divide(bd145, 100, RoundingMode.DOWN);
  System.out.println("BigDecimal : " +result.toPlainString());
  
 }
}

Le résultat sera :

Il est important de noter que ces opérations sont beaucoup plus lentes. Un test rapide :

import java.math.BigDecimal;
import java.math.RoundingMode;

public class ExempleBigDecimal {
 
 public static void main (String args[]) {
  
  float exemplef;
  long d = System.currentTimeMillis();
  for(int i = 0; i < 1000; i++)
   exemplef = (float)34/145;
  long f = System.currentTimeMillis(); 
  System.out.println("Float temps 1000 opérations    : " + (f - d));
  
  double exempled;
  d = System.currentTimeMillis();
  for(int i = 0; i < 1000; i++)
   exempled = (double)34/145;
  f = System.currentTimeMillis(); 
  System.out.println("Double temps 1000 opérations    : " + (f - d));
  
  BigDecimal bd34 = new BigDecimal(34);
  BigDecimal bd145 = new BigDecimal(145);
  BigDecimal result;
  d = System.currentTimeMillis();
  for(int i = 0; i < 1000; i++)
   result = bd34.divide(bd145, 100, RoundingMode.DOWN);
  f = System.currentTimeMillis(); 
  System.out.println("BigDecimal temps 1000 opérations : " + (f - d));
  
 }
}

Le résultat est :

Nous voyons clairement que 1000 opérations de division en BigDecimal sont beaucoup plus lentes que les opérateurs traditionnels.

Les fonctions : par analogie avec les fonctions mathématiques

Les fonctions sont présentes dans tous les programmes. Il est pratiquement impossible d'écrire un programme qui effectue plusieurs tâches sans faire recours aux fonctions (pas impossible mais très difficile, pénible et coûteux).

Dans cet article, je vais essayer de présenter la notion de fonction en la rapprochant de la notion de fonction mathématique; une notion largement plus maîtrisée.

Une fonction mathématique à une seule variable peut être déclarée par la forme suivant :

Cette déclaration se divise en deux partie :

• La première partie désigne l'ensemble de départ; l'ensemble dans lequel la variable d'entrée va prendre ses valeurs.
• La deuxième partie désigne l'ensemble d'arrivé; l'ensemble dans lequel la fonction prend ses valeurs.

Un exemple concret :

Ainsi, cette fonction prend une variable réelle et renvoie une valeur réelle. Cette valeur est calculée comme étant le double du cub de la valeur prise en entrée.

Plus généralement, une fonction à n variables est déclarées de la manière suivante :

La première partie désigne un produit cartésien de plusieurs ensemble, c'est à dire, la fonction prend un t-uple en entrée et prend ses valeur dans un ensemble d'arrivé.

Un exemple concret :

Cette fonction prend un couple de nombres réels et prend ses valeurs dans l'ensemble des nombres réels. La deuxième partie montre la formule de calcule.

La deuxième partie peut être un peu plus compliqué qu'une formule unique. La fonction "valeur absolue", par exemple, est définie comme suit :

Ainsi, la formule varie selon la valeur de la variable.

Passons maintenant à la programmation.

La déclaration d'une fonction doit préserver, au moins, les notions requises par la déclaration mathématique. Autrement, la conception d'une fonction sera vraiment difficile à imaginer.

Ainsi, il faut garder :

• Les ensemble de départ et l'ensemble d'arrivé.
• La formule du calcul.

En Pascal, la déclaration sera ainsi :

function f([parametres : ensembles de depart]) : [ensemble d'arrivée];

reprenons l'exemple d'une fonction à une seule variable :

function f(x : Real) : Real;

La deuxième partie est facilement réalisable grace aux structures de contrôle offertes par le langage (le conditionnel et les boucles). Ainsi le code de la première fonction sera :

Function f(x : Real) : Real;
Begin
 f := 2 * x * x * x;
End;

Et la fonction qui implémente la fonction "valeur absolue" sera :

Function valeurAbsolue(n : Integer) : Integer;
Begin
 If(n >= 0)Then
  valeurAbsolue := n
 Else
  valeurAbsolue := -1 * n;
End;

Pour appeler une fonction, c'est comme appeler une personne :), c'est par son nom sans oublier de lui fournir les valeurs nécessaires en entrée (les paramètres). Un exemple complet :

Program ExempleFonctions;

Function f1(x : Real) : Real;
Begin
 f1 := 2 * x * x * x;
End;

Function f2(x, y : Real) : Real;
Begin
 f2 := x * x + y * y;
End;

Function valeurAbsolue(n : Integer) : Integer;
Begin
 If(n >= 0)Then
  valeurAbsolue := n
 Else
  valeurAbsolue := -1 * n;
End;

Begin
 
 WriteLn(f1(3.14):4:2);
 WriteLn(f2(2.5, 3.5):4:2);
 WriteLn(valeurAbsolue(-10));
 
End.

Les tableaux : Quoi et Pourquoi ?

Définition

Les tableaux sont des structures de données statiques.

Une structure de données est une manière d'organiser les données pour les traiter plus facilement (Wikipedia).

Statique désigne la taille fixe : un tableau est d'une taille (nombre de cellules) fixe.

Un tableau (array en anglais) est une structure de données qui consiste en un ensemble d'éléments ordonnés accessibles par leur indice (ou index) (Wikipedia).

Pourquoi utiliser un tableau ?

Un tableau est utilisé lorsque les données à manipuler satisfont les trois conditions suivantes :

1. Nous voulons sauvegarder toutes les données,
2. Nous avons des données de même types,
3. Nous allons appliquer le même traitement sur toutes les données.

Exemple 1 : Utilisation des tableaux recommandée

Supposons que nous voulons saisir les notes de tous les étudiants d'un groupe pour ensuite calculer la moyenne et connaître le min et le max.

Dans ce cas, les trois conditions sons satisfaites :

1. Nous voulons nous rappeler de toutes les notes,
2. Les notes sont toutes de même nature et de même types,
3. Le calcul de la moyenne et la recherche du min et de max nécessitent des traitement identiques sur chaque notes (addition et comparaison)

Exemple 2 : Utilisation des tableaux non recommandées

Supposons que nous avons les données suivantes : la taille (en m) d'une personne, son poids (en kg), son rythme cardiaque, sa tension et sa température au moment de la consultation médicale.

Ces données sont toutes des nombres (entiers ou réels). Nous voulons les sauvegarder dans le dossier médical du patient. Néanmoins, ces données ne peuvent pas subir des traitements identiques : la somme de la taille et du poids, la comparaison entre le poids et tension ou la multiplication de la tempértaure et du rythme cardiaque sont toutes des opérations qui n'ont aucun sens.

Ainsi, l'utilisation des tableaux n'est pas recommandée dans ce cas.

Déclaration et code : solution du premier exemple :

Program PremierExempleTableau;

Const
 N = 10;
 
Var 
 notes : Array [1..N] of Real; {toutes les données sont de même type, 
          la taille est fixe}
 i : Integer; {L'indice pour pouvoir accéder aux différentes valeurs}
 
 somme, max, min : Real;

Begin
 
 For i:= 1 to N Do
 Begin
  WriteLn('Donnez la ', i, 'ème valeur :');
  ReadLn(notes[i]);
 End;
 
 somme := notes[1];
 min := notes[1];
 max := notes[1];
 
 For i:= 2 to N Do
 Begin
  somme := somme + notes[i];
  
  If (notes[i] < min) Then
   min := notes[i];
   
  If (notes[i] > max) Then
   max := notes[i];
 End;
 
 WriteLn('Les notes saisies sont : ');
 For i:= 1 to N Do
 Begin
  Writeln('notes[', i, '] = ', notes[i]:2:2);
 End;
 
 WriteLn('La somme de ces notes est ', somme:2:2);
 WriteLn('La moyenne de ces notes est ', (somme / N):2:2);
 WriteLn('La plus grande note est ', max:2:2);
 WriteLn('La plus petite note est ', min:2:2);
 
End.

Effet de bord (variables) Démo

L'effet de bord (effet secondaire) pour les variables surgit lorsque la variable prend une valeur illogique. Cet effet peut figurer aussi avec les fonctions. (Pour un peu de détail : ici)

Pour les variables, la cause principale est la limite imposée par la taille de la variable.

Cet article vise à donner un exemple sur cet effet.

Démo

Pour démontrer cet effet, nous allons essayer de calculer le factoriel (n!) de quelques nombres. Cette fonction donne, rapidement, des valeurs très grandes.

En Pascal :

Program EffetDeBord;

Var
 i, factoriel : Integer;

Begin
 
 factoriel := 1;
 
 For i := 1 to 10 Do
 Begin
  factoriel := factoriel * i;
  WriteLn(i, '! = ', factoriel);
 End;
 
End.

L'exécution de ce code :

Nous pouvons voir que le calcul commence à donner des valeurs érronées et illogiques des (8!). En effet, le type Integer ne peut pas contenir des valeurs en dehors de l'intervalle : -32768 .. 32767.

Ce phénomène peut être réduit si on utilise des variables "plus grandes" comme le Longint (Long Integer) :

Program EffetDeBord;

Var
 i, factoriel : LongInt;

Begin
 
 factoriel := 1;
 
 For i := 1 to 10 Do
 Begin
  factoriel := factoriel * i;
  WriteLn(i, '! = ', factoriel);
 End;
 
End.

Ce code donne des valeurs plus correctes :

Un entier de type LongInt peut stocker des données de l'intervalle : -2147483648 .. 2147483647.

Pour plus d'information sur la taille des types de données, il faut consulter la documentation officielle du compilateur que vous utilisez. Par exemple :

Turbo Pascal : (ici) 
Free Pascal : (ici)

Un peu de pratique avec les boucles : calcul du cosinus

Enoncé
Ecrire le programme qui calcule la valeur du sinus grâce au développement limité suivant :

(source)
Solution
Dans cet exemple, j'ai présenté un problème très simiaire. On suit le même mode de raisonnement et on utilise l'écriture sous forme de série comme suit :

Le code Pascal sera ainsi :

Program CalculCosinus;

Var
 i, n, signe, factoriel : Integer;
 x, cosinus, puissancex : Real;

Begin
 
 WriteLn('Donnez le x pour cacluler cos(x) :');
 ReadLn(x);
 WriteLn('Donnez n qui désigne ma précision du calcul :');
 ReadLn(n);
 
 signe := 1;
 factoriel := 1;
 puissancex := 1;
 cosinus := 0;
 
 For i:= 1 to n Do
 Begin
  cosinus := cosinus + (signe * puissancex) / factoriel;
  WriteLn(signe, ' ', puissancex, ' ', factoriel, ' ', cosinus);
  signe := signe * -1;
  puissancex := puissancex * x * x;
  factoriel := factoriel * (2 * i - 1) * (2 * i);
  
 End;
 
 WriteLn('Valeur calculée par cet algorithme : ', cosinus:1:2);
 WriteLn('Valeur calculée par l''API de pascal : ', cos(x):1:2);
 
End.

Dans ce code comme le précédent, l'effet de bord est présent.

Un peu de pratique avec les boucles : calcul du sinus

Enoncé
Ecrire le programme qui calcule le sinus en utilisant le développement limité suivant :

(source)
Solution
Un autre exercice classique pour pratiquer avec les boucles.

L'astuce est simple : il ne faut pas penser à chaque élément d'une manière indépendant; il faut le baser sur l'élément précédent. En d'autres termes, pensez à utiliser l'écriture série de cette formule :

Ainsi, l'objectif est de calculer les éléments (les termes) de la sommes l'un après l'autre en se basant sur l'élément précédent.

Le code en Pascal sera :

Program CalculSinus;

Var
 i, n, signe, factoriel : Integer;
 x, sinus, puissancex : Real;

Begin
 
 WriteLn('Donnez le x pour cacluler sin(x) :');
 ReadLn(x);
 WriteLn('Donnez n qui désigne la précision du calcul :');
 ReadLn(n);
 
 signe := 1;
 factoriel := 1;
 puissancex := x;
 sinus := 0;
 
 For i:= 1 to n Do
 Begin
  sinus := sinus + (signe * puissancex) / factoriel;
  signe := signe * -1;
  puissancex := puissancex * x * x;
  factoriel := factoriel * (2 * i) * (2 * i + 1);
 End;
 WriteLn('Valeur calculée par cet algorithme : ', sinus:1:2);
 WriteLn('Valeur calculée par l''API de pascal : ', sin(x):1:2);
 
End.

Pour les deux exemples, j'ai donné 4 comme précision. Cela m'évite un effet de bord à cause de valeur 11! (11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) si je donne 5 comme précision. Evidemment, toute valeur supérieure à 5 provoquera le même problème.

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.

Vérifier si un nombre est premier

Enoncé
Ecrire un programme qui lit un entier "n" et vérifie s'il est entier.

Solution
Comme j'ai mentionné ici, l'astuce du diviseur est un excellent moins pour faire des travaux dirigés sur la notion de la variable booléenne. Cette dernière est utilisée très souvent dans les boucles de type "Tant que" et "Répéter jusqu'à" comme une condition d'arrêt (pour sortir de la boucle).

Ainsi, les auteurs et les enseignants tentent de mettre cette "petite" astuce de diviseur dans des boucles.

Dans le cas de cet exercice, l'idée est de vérifier s'il est premier ou pas, c'est à dire, de rechercher un autre diviseur de "n" que "1" et "n" lui même. Cela implique un parcours des valeurs de 2 à n - 1 (l'optimisation n'est pas vraiment ma priorité actuellement) et voir si on peut trouver un diviseur.

On sort de la boucle si :

1. On termine le parcours des valeurs de 2 à n - 1 sans trouver un diviseur et le nombre n est déclaré premier.
2. On trouve un diviseur alors on n'a plus besoin de vérifier autre chose et le nombre n est déclaré non premier.

La présence de deux conditions dans la définition de la boucle nous oblige à faire une vérification pour savoir "pourquoi avons nous quitter la boucle ?".

Ainsi, le code sera de la forme :

Program Premier;

Var
 n, i : Integer;
 diviseur : Boolean;

Begin

 WriteLn('Donnez un nombre à tester : ');
 ReadLn(n);
 
 i := 2;
 diviseur :=  false;
 
 While (not(diviseur) And (i < n)) Do
 Begin
  If (n mod i = 0) Then
   diviseur := true
  Else
   i := i + 1;
 End;
 
 {Vérification pourquoi a-t-on quitté la boucle}
 If (diviseur) Then
  WriteLn('n n''est pas un nombre premier')
 Else
  WriteLn('n est un nombre premier');
 
End.

L'opérateur "modulo" : un point essentiel pour comprendre la différence entre une définition théorique (mathématique) et une définition pratique (appliquée, informatique)

Enoncé
Ecrire un programme qui lit deux entiers a et b et vérifie est ce que b est un diviseur de a.

Solution
Ma principale motivation pour cette article est une solution que je lis plusieurs fois durant les séances de TD Algorithmique pour les étudiants MI. Les étudiants en Mathématiques et Informatique sont généralement des matheux qui maîtrise les maths et qui projèctent chaque nouvelle notion acquise sur une notion mathématiques.

Dans le cas de vérification si un nombre divise un autre, le code que je lis souvent est le suivant :

Program Diviseur;

Var
 a, b, k : Integer;

Begin
 ReadLn(a, b);
 If (k * b = a) Then
  WriteLn('b divise a')
 Else
  WriteLn('b ne divise pas a');
 
End.

Cette solution n'est même pas "compilable". En effet, la variable k n'a jamais été initialisée. Cela donne des avertissements (Warning) sous des compilateur et des erreur (Error) sous d'autres.

Mais cette solution n'est pas vraiement loin de la réalité. En effet, les étudiants, qui gardent encore un esprit matheux par excellence, reposent sur la définition suivante :

Soit a et b deux entiers.
On dit que b est un diviseur de a s'il existe un entier k tel que k.b = a.

L'erreur n'est pas dans la définition mais dans la traduction de la définition. L'erreur faite par les étudiants ici est plus simple de ce qu'elle parraît. En effet, ils ont montré deux confusions :

1. La déclaration algorithmique est différente de la déclaration mathématique. Décalrer une variable en algorithmique ne veut pas dire qu'elle prendra une valeur sur le champs.
2. L'ordinateur va chercher la bonne valeur pour eux.

Ainsi, une traduction plus correcte de la définition sera de la forme :

Program VerifierDiviseur;

Var
 a, b, k : Integer;
 diviseur : Boolean;

Begin
 ReadLn(a, b);
 k := 2;
 diviseur := false;
 
 While (not(diviseur) And (k < a)) Do
 Begin
  If (k * b = a) Then
   diviseur := true
  Else
   k := k + 1;
 End;
 
 If (diviseur) Then
  WriteLn('b divise a')
 Else
  WriteLn('b ne divise pas a');
 
End.

La suposition "il existe un entier k" nous oblige à le chercher, c'est à dire à parcourir les valeurs des nombres entiers, d'où la boucle.

Alors ce qu'il faut faire, c'est  de choisir la bonne définition. C'est aussi simple que cela. La définition à prendre est la définition la plus élémentaires que nous enseignons aux enfants :

Soient a et b deux entiers.
On dit que b est un diviseur de a si le reste de division de a sur b est nul.

Comment choisir la bonne définition ? Il n'y a pas une méthode exacte; c'est par la pratique, la lecture des codes et l'expérience. Dans ce cas, il fallait lister des opérations possibles et penser à choisir la définition la plus proche d'une telle ou telle opération ou bien celle qui nécessite un code minimal.

Le code sera ainsi :

Program VerifierDiviseur;

Var
 a, b : Integer;

Begin
 ReadLn(a, b);
 
 If (a mod b = 0) Then
  WriteLn('b divise a')
 Else
  WriteLn('b ne divise pas a');
 
End.

Dans les exemples suivants, vous allez voir que cette vérification n'est pas réalisée juste pour faire un affichage. Elle est utilisée pour aider les étudiants à comprendre et utiliser la notion d'une variable booléenne.