Corrigé 2

Prérequis

1.	Une variable de type tableau contient autant de valeurs que d’éléments, c’est-à-dire n valeurs dans ce cas. En effet, chaque élément possède sa propre valeur.
2.	C’est le produit de la taille de chaque dimension. Un tableau de trois dimensions ayant pour taille respective 20, 30 et 50 est de 203050, soit 30 000 éléments.
3.	a., b. et e. En effet, en Java, dans la déclaration de la variable tableau, figurent bien le nom, le type des éléments et le nombre de dimensions (exprimé par la présence d’autant de [] à la suite du type ou du nom) mais pas les tailles de chaque dimension. Les tailles sont précisées lors de la création du tableau. Quant à la borne inférieure, elle vaut toujours zéro en Java.
4.	t est déclaré ainsi : int[][] t;
5.	Il s’agit de l’opérateur new.
6.	t est créé ainsi : t = new int[10][20];
7.	En Python, les tableaux sont traités comme des listes qui sont des structures dynamiques. Cela signifie que la taille d’un tableau n’est pas déclarée au moment de la création et que celle-ci peut changer dynamiquement par ajout ou suppression d’éléments sans avoir à recréer le tableau. Une autre particularité est que les tableaux n’ont...

Corrigé 2.1 : Moyenne des éléments d’un tableau

L’algorithme du calcul de la moyenne est illustré ci-dessous. Il déclare un tableau de 20 entiers, procède à la lecture de chaque élément puis calcule la somme à l’aide d’une boucle Pour. Nous utilisons 0 comme borne inférieure du tableau 0 afin que notre algorithme soit plus proche du programme Java ou Python.

PROGRAMME Moyenne  
CONST 
     taille : entier = 20 
VAR 
     i, somme :    entier  
     moyenne : réel 
     tableau : tableau[0..taille-1] d'entiers 
DÉBUT 
     // lecture du tableau 
     Pour i De 0 à taille-1 Faire  
           Lire tableau[i] 
     FinPour 
     // calcul et affichage de la moyenne  
     somme <- 0 
     Pour i De 0 à taille-1 Faire  
           somme <- somme + tableau[i] 
     FinPour 
     moyenne <- somme / taille  
     Écrire moyenne 
FIN

Le programme Java correspondant à l’algorithme se trouve ci-dessous. Il convient de remarquer la création du tableau à...

Corrigé 2.2 : Variance et écart type des éléments d’un tableau

L’algorithme précédent est étendu pour calculer la variance et l’écart type. Pour calculer la variance, la somme des différences au carré entre chaque valeur et la moyenne est d’abord calculée. La variance est obtenue par la division de cette somme par la taille du tableau, puis l’écart type est obtenu par la racine carrée de la variance.

PROGRAMME Variance  
CONST 
     taille : entier = 20  
VAR 
     i, somme : entier moyenne : réel 
     tableau : tableau[0..taille-1] d'entiers 
     variance, écartType : réel 
DÉBUT 
     // lecture du tableau 
     Pour i De 0 à taille-1 Faire 
           Lire tableau[i]  
     FinPour 
     // calcul et affichage de la moyenne 
     somme <- 0 
     Pour i De 0 à taille-1 Faire  
           somme <- somme + tableau[i] 
     FinPour 
     moyenne <- somme/taille 
     Écrire moyenne 
     // calcul et affichage de la variance...

Corrigé 2.3 : Recherche séquentielle d’une valeur dans un tableau

La première version de l’algorithme utilise une boucle Pour afin de tester si la valeur recherchée est égale à chaque élément du tableau. Quand le test est vérifié, un message est affiché. La variable entière nbrValeursTrouvées permet d’afficher un message dans le cas où la valeur n’a pas été retrouvée dans le tableau. Dans le cas contraire, elle permet d’afficher le nombre d’occurrences.

PROGRAMME RechercheValeur  
CONST 
     taille : entier = 10 
VAR 
     i, valeur : entier 
     tableau : tableau[0..taille-1] d'entiers  
     nbrValeursTrouvées : entier 
DÉBUT 
     // remplissage du tableau 
     Pour i De 0 à taille-1 Faire  
           tableau[i] <- nombreAléatoire(l,10) 
     FinPour 
     // affichage du tableau 
     Pour i De 0 à taille-1 Faire  
           Écrire tableau[i] 
     FinPour 
     // lire la valeur à rechercher  
     Lire valeur 
     // recherche dans le tableau 
     nbrValeursTrouvées <- 0 
     Pour i De 0 à taille-1 Faire 
           Si tableau[i] = valeur Alors 
                 nbrValeursTrouvées <- nbrValeursTrouvées + 1 
                 Écrire "Valeur trouvée à l'indice "  
                 Écrire i 
           FinSi  
     FinPour 
     Si nbrValeursTrouvées = 0 Alors 
           Écrire "Valeur non trouvée dans...

Corrigé 2.4 : Valeurs communes à deux tableaux

La première version de l’algorithme consiste à boucler sur tous les éléments du premier tableau et pour chacun d’entre eux, à rechercher s’il existe un élément de même valeur dans le second tableau.

Si tel est le cas, alors la variable nbrValeursCommunes est augmentée de un.

PROGRAMME ValeursCommunes  
CONST 
     taille : entier = 10 
VAR 
     tableau : tableau[0..taille-1] d'entiers  
     tableau2 : tableau[0..taille-1] d'entiers  
     i, j, nbrValeursCommunes : entier 
DÉBUT 
     // remplissage des tableaux 
     Pour i De 0 à taille-1 Faire 
           tableau[i] <- nombreAléatoire(l,10)  
           tableau2[i] <- nombreAléatoire(l,10) 
     FinPour 
     // affichage des deux tableaux 
     Pour i De 0 à taille-1 Faire  
           Écrire tableau[i] 
     FinPour 
     Pour i De 0 à taille-1 Faire  
           Écrire tableau2[i] 
     FinPour 
     // recherche du nombre de valeurs communes 
     nbrValeursCommunes <- 0 
     Pour i De 0 à taille-1 Faire 
           j <- 0 
           Tant Que (j < taille) ET (tableau2[j] != tableau[i])     
                 j <- j  + 1 
           FinTantque 
           Si (j < taille) Alors 
                 nbrValeursCommunes <- nbrValeursCommunes + 1 
           FinSi  
     FinPour 
     Écrire nbrValeursCommunes 
FIN

Le programme Java correspondant est à la suite.

public class ValeursCommunes { 
 
   public static void main(String[] args) { 
 ...

Corrigé 2.5 : Insertion d’une valeur dans un ensemble d’entiers

L’algorithme d’insertion présente deux parties importantes qu’il faut étudier :

La déclaration de l’ensemble qui consiste en la déclaration d’un tableau et d’une variable qui contient sa taille.
L’insertion d’une valeur dans l’ensemble qui nécessite au préalable de vérifier que cette valeur n’existe pas déjà dans l’ensemble. Ensuite, l’insertion est réalisée simplement en affectant la nouvelle valeur au sommet du tableau et en incrémentant la taille de l’ensemble.

Il convient d’ajouter que cette dernière opération d’insertion est réalisable car la taille de l’ensemble est strictement inférieure à sa taille maximale, en raison de la condition de la boucle principale Tant Que.

PROGRAMME AjoutEnsembleEntiers  
CONST 
     tailleMaximaleEnsemble : entier = 10 
VAR 
     // déclaration de l'ensemble 
     ensemble : tableau[0.. tailleMaximaleEnsemble-1] d'entiers  
     tailleEnsemble : entier = 0 
     valeur, j : entier 
 
DÉBUT 
     Tant Que tailleEnsemble < tailleMaximaleEnsemble  
   ...

Corrigé 2.6 : Suppression d’une valeur dans un ensemble d’entiers

L’algorithme de suppression d’une valeur dans un ensemble d’entiers commence par la déclaration de l’ensemble à l’aide d’une constante de type tableau. Puis, la taille de l’ensemble est fixée à 5.

Avant de chercher à supprimer la valeur, il faut vérifier que celle-ci existe dans le tableau. Si oui, on effectue une boucle Pour afin de la supprimer.

PROGRAMME SuppressionEnsembleEntiers  
CONST 
     tailleMaximaleEnsemble : entier = 10 
VAR 
     // déclaration de l'ensemble 
     ensemble : tableau[0 .. tailleMaximaleEnsemble-1] d'entiers  
= {1, 2, 3, 4, 5, 0, 0, 0, 0, 0} 
     tailleEnsemble : entier = 5  
     valeur, i, j : entier 
DÉBUT 
     Lire valeur 
     i <- 0 
     Tant Que (i < tailleEnsemble) ET (ensemble[i] != valeur) 
           i <- i+ 1 
     FinTanQue 
     Si i < tailleEnsemble Alors  
           tailleEnsemble <- tailleEnsemble - 1 
           Pour j De i à tailleEnsemble-1 Faire 
     ...

Corrigé 2.7 : Insertion d’une valeur dans un ensemble d’entiers (version basée sur un tableau trié de valeurs)

L’algorithme d’insertion est basé sur la recherche par dichotomie. Celle-ci est programmée à l’aide d’une boucle Tant Que. Elle se poursuit tant que la valeur recherchée n’a pas été trouvée et tant que tout le tableau n’a pas été parcouru, c’est-à-dire tant que la borne gauche est inférieure ou égale à la borne droite.

PROGRAMME AjoutEnsembleTriéEntiers 
CONST 
     tailleMaximaleEnsemble : entier = 10 
VAR 
     // déclaration de l'ensemble 
     ensemble : tableau[0..tailleMaximaleEnsemble-1] d'entiers  
     tailleEnsemble : entier = 0 
     borneGauche, borneDroite, milieu, i : entier  
     valeur : entier 
     trouvé : booléen 
DÉBUT 
     Tant Que tailleEnsemble < tailleMaximaleEnsemble 
           Lire valeur 
           // recherche de la valeur dans l'ensemble par dichotomie  
           borneGauche <- 0 
           borneDroite <- tailleEnsemble - 1  
           trouvé <- FAUX 
           Tant Que (NON trouvé) ET (borneGauche <= borneDroite)  
                 milieu <- (borneGauche + borneDroite) DIV 2 
                 Si ensemble[milieu] = valeur Alors  
     ...

Corrigé 2.8 : Suppression d’une valeur dans un ensemble d’entiers (version basée sur un tableau trié de valeurs)

L’algorithme de suppression est proche de celui de l’insertion. Si la valeur recherchée est retrouvée par la méthode de dichotomie, alors elle est supprimée par un décalage des valeurs du tableau.

PROGRAMME SuppressionEnsembleTriéEntiers  
CONST 
     tailleMaximaleEnsemble : entier = 10  
     VAR 
     // déclaration de l'ensemble 
     ensemble : tableau[0..tailleMaximaleEnsemble-1] d'entiers  
= {1, 2, 3, 4, 5, 6, 8, 10, 12, 14} 
     tailleEnsemble : entier = 10 
     borneGauche, borneDroite, milieu, i : entier 
     valeur : entier 
     trouvé : booléen 
DÉBUT 
     Lire valeur 
     // recherche de la valeur dans l'ensemble par dichotomie  
     borneGauche <- 0 
     borneDroite <- tailleEnsemble - 1  
     trouvé <- FAUX 
     Tant Que (NON trouvé) ET (borneGauche <= borneDroite)  
           milieu <-(borneGauche + borneDroite) DIV 2 
           Si ensemble[milieu] = valeur Alors 
                 trouvé <- VRAI  
           Sinon 
                 Si ensemble[milieu]...

Corrigé 2.9 : Suppression des doublons dans un tableau

Pour supprimer les doublons dans un tableau, l’algorithme copie les valeurs qu’il n’a pas déjà copiées dans un nouveau tableau. Il est possible d’examiner ce mécanisme dans la boucle Pour qui réalise le dédoublonnage. Au sein de celle-ci, la boucle Tant Que permet de vérifier que la valeur en cours n’a pas déjà été copiée dans le nouveau tableau.

PROGRAMME SuppressionDoublons 
CONST 
     taille : entier = 20  
VAR 
     // déclaration des tableaux 
     tableau : tableau[0 .. taille-1] d'entiers  
     tableau2 : tableau[0 .. taille-1] d'entiers  
     taille2 : entier 
     // nombre d'éléments de tableau2  
     i, j : entier 
DÉBUT 
     // remplissage du tableau 
     Pour i De 0 à taille-1 Faire 
           tableau[i] <- nombreAléatoire(0,10) 
     FinPour 
     // dédoublonnage 
     taille2 <- 0 
     Pour i De 0 à taille-1 Faire 
           j <- 0 
     ...

Corrigé 2.10 : Tri par sélection d’un tableau d’entiers

Le tri par sélection consiste à boucler sur chaque élément du tableau et à échanger sa valeur avec la plus petite valeur des éléments qui suivent cet élément.

PROGRAMME TriSélection 
CONST 
     taille : entier = 20 
VAR 
     // déclaration des tableaux 
     t : tableau[0..taille-1] d'entiers  
     temp, indiceValeurMin : entier 
     i, j : entier 
DÉBUT 
     // remplissage du tableau  
     Pour i De 0 à taille-1 Faire 
           t[i] <- nombreAléatoire(0,100) 
     FinPour 
     // tri par sélection 
     Pour i De 0 à taille-1 Faire  
           indiceValeurMin <- i 
           // recherche de la plus petite valeur 
           Pour j De i+l à taille-1 Faire 
                 Si t[j] < t[indiceValeurMin] Alors 
                       indiceValeurMin <- j  
     ...

Corrigé 2.11 : Tri bulle d’un tableau d’entiers

Le tri bulle est mis en œuvre par une boucle Répéter qui se poursuit jusqu’à ce qu’il n’y ait plus aucune permutation. Le corps de la boucle consiste à vérifier que le tableau est trié et dans le cas contraire à procéder à des permutations.

PROGRAMME TriBulle 
CONST 
     taille : entier = 20 
VAR 
     // déclaration des tableaux 
     t : tableau[0..taille-1] d'entiers  
     temp : entier 
     permuté : booléen 
     i : entier 
DÉBUT 
     // remplissage du tableau 
     Pour i De 0 à taille-1 Faire  
           t[i] <- nombreAléatoire(0,100) 
     FinPour 
     // tri bulle  
     Répéter 
           permuté <- FAUX 
           Pour i De 0 à taille-2 Faire  
                 Si t[i] > t[i+l] Alors 
                       // échange entre t[i] et t[i+l]  
     ...

Corrigé 2.12 : Fusion de deux tableaux triés d’entiers

L’algorithme de fusion des deux tableaux triés consiste à recopier les valeurs de chaque tableau en les comparant une à une. Ensuite deux boucles permettent de recopier les valeurs qui restent dans l’un des deux tableaux sources. En effet, la première boucle s’arrête soit avec i = taille1 soit avec j = taille2 soit encore avec ces deux conditions vérifiées. Dans ce dernier cas, la fusion est terminée. Aucune des deux boucles qui suivent n’est alors activée, car leurs conditions de fin sont immédiatement vérifiées.

Dans les autres cas, une seule des deux boucles suivantes est activée, celle dont la condition de fin n’est pas vérifiée. Elle termine la fusion.

PROGRAMME FusionTableauxTriés  
CONST 
     taillel : entier = 10  
     taille2 : entier = 20  
     taille3 : entier = taille1 + taille2 
VAR 
     // déclaration des tableaux à trier et à fusionner  
     tl : tableau[0..taillel-1] d'entiers 
     t2 : tableau[0..taille2-l] d'entiers  
     t3 : tableau[0..taille3-l] d'entiers  
     i, j, k : entier 
DÉBUT 
     // remplissage des deux tableaux  
     Pour i De 0 à taillel-1 Faire 
           t1[i] <- nombreAléatoire(0,100) 
     FinPour 
     Pour i De 0 à taille2-1 Faire 
           t2[i] <- nombreAléatoire(0,100) 
     FinPour 
     // tri de t1 
     ... 
     // tri de t2 
     ... 
     // affichage de t1 
     Pour i De 0 à taillel-1 Faire  
           Écrire t1[i] 
     FinPour 
     Pour i De 0 à taille2-1 Faire  
           Écrire t2[i] 
     FinPour 
     i <- 0 
     j <- 0 
   ...

Corrigé 2.13 : Comparaison de deux tableaux de caractères

La comparaison de tableaux de caractères consiste dans un premier temps à rechercher le nombre de caractères communs. Si ce nombre est égal à la longueur de l’un des deux tableaux, celui-ci précède l’autre. Si ce nombre est égal à la longueur des deux tableaux, ceux-ci sont égaux.

Si ce nombre est différent des longueurs des tableaux, il faut alors comparer le caractère qui suit le dernier caractère égal dans les deux tableaux. L’ordre de ces caractères pris dans les deux mots donne l’ordre des mots.

public class ComparaisonTableauxCaracteres { 
 
   public static void main(String[] args) { 
       // déclaration et création des tableaux 
       final char tableau1[] =  
{'b', 'o', 'n', 'j', 'o', 'u', 'r'}; 
       final char tableau2[] =  
{'b', 'o', 'n', 'j', 'o', 'u', 'a'}; 
       // comparaison des chaînes de caractères 
       int i = 0; 
       // calcul du nombre de caractères communs ...

Corrigé 2.14 : Lecture et écriture de matrices carrées d’entiers

Ce programme ne présente pas de difficultés. Il consiste à déclarer et créer la matrice sous la forme d’un tableau à deux dimensions de même taille. Pour la lecture comme pour l’écriture, le programme utilise deux boucles for imbriquées. Voici le code en Java.

import java.util.Scanner; 
public class LectureEcritureMatrices { 
 
   public static void main(String[] args) { 
       Scanner reader = new Scanner(System.in); 
       final int taille = 3; 
       // déclaration et création de la matrice 
       int[][] matrice = new int[taille][taille]; 
       // lecture de la matrice 
       for (int i = 0; i < taille; i++) 
           for (int j = 0; j < taille; j++) { 
               System.out.print("Entrez matrice[" + i + "][" + j + "] : "); 
               matrice[i][j] = reader.nextInt(); 
           } 
       // écriture de la matrice 
       for (int...

Corrigé 2.15 : Somme de deux matrices carrées d’entiers

La somme de deux matrices est obtenue en ajoutant, pour chaque ligne et colonne, la valeur de chaque matrice.

import java.util.Scanner; 
 
public class SommeMatrices { 
 
   public static void main(String[] args) { 
       Scanner reader = new Scanner(System.in); 
       final int taille = 3; 
       // déclaration et création des matrices 
       int[][] matrice1 = new int[taille][taille]; 
       int[][] matrice2 = new int[taille][taille]; 
       // lecture des matrices 
       for (int i = 0; i < taille; i++) 
           for (int j = 0; j < taille; j++) { 
               System.out.print("Entrez matrice1[" + i + "][" + j + "] : "); 
               matrice1[i][j] = reader.nextInt(); 
           } 
       for (int i = 0; i < taille; i++) 
           for (int j = 0; j < taille; j++) { 
               System.out.print("Entrez matrice2[" + i + "]["...

Corrigé 2.16 : Construction d’un index

En Java, le programme ConstructionIndex commence par déclarer le tableau mots qui contient cinq mots triés. Ensuite, l’index est déclaré et initialisé.

Sa construction se fait à l’aide des deux variables derniereLettrel et derniereLettre2. Elles contiennent la dernière position dans l’index qui a été créée. En balayant le tableau des mots, le programme construit pour chacun d’eux la position qui lui correspond dans l’index. Si cette position est différente de celle contenue dans les variables derniereLettrel et derniereLettre2, alors une nouvelle position est créée dans l’index et ces deux variables sont modifiées.

Au début, les variables derniereLettrel et derniereLettre2 sont initialisées à -1 pour garantir qu’une première entrée soit créée dans l’index pour le premier mot.

public class ConstructionIndex { 
 
     public static void main(String[] args) { 
           final int tailleIndex = 26; 
           char[][] mots = {{'i', 'n', 'd', 'e', 'x'}, 
                       {'i'...