Exercices sur les structures de contrôle, les structures de données, les structures itératives #

Le résultat affiché sera BBB, car x != true donnera Faux et x == true donnera Vrai. Par définition, Faux ET Vrai = FAUX

Voici les erreurs :

• l'opérateur =< n'existe pas, c'est plutôt <=
• il manque une parenthèse ")" à la première ligne if (avant le })
• on ne peut assigner une String à un int
• en supposant que l'indentation est correcte, il manque le else pour } else if (
• l'opérateur !!= n'existe pas, c'est plutôt !=

int x = 5;

if((x > 1) && (x <= 10)) {
     x = 5;
} else if (x != 5) {
     x = 100;
} 

Le contrôle se fait au départ dans la boucle while alors que le contrôle se fait à la fin dans le do-while. Dans la boucle while, il y a donc un contrôle avant même de faire la première itération.

La sortie sera "Default", car la valeur de la variable index = 10 ne correspond à aucun des cas du switch. C'est donc le sous-bloc "Default" qui est exécuté.

Faux. Il est vrai qu'il y a 10 entiers (int) et que chaque entier occupe 4 octets. Cependant, Java doit aussi garder une trace de la longueur du tableau (10 éléments). Il y a aussi d'autres contraintes. Il serait plus juste de dire que le tableau va utiliser plus de 40 octets.

À l'exécution l'opération int x = tableau[20] va générer une erreur du type : java.lang.ArrayIndexOutOfBoundsException: 20, car nous tentons d'accéder à des index du tableau qui n'existe pas.

Le type int n’est pas une classe. Il faut plutôt utiliser la syntaxe ArrayList<Integer> = new ArrayList<Integer>();. Une mécanique de conversion automatique permet d’assigner des types à leur objet équivalent. Par exemple Integer i = 5; ou bien :

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(5);

Voici le code

public class Dictionnaire {
    
    int[][] tableau2D = {{5,3},{2,5},{4,3},{8,10},{105,32},{55,34},{12,21},
        {15,51},{4,1},{6,3},{19,3},{65,13},{1235,1353},{51515,32143},
        {15155,3555}};
    
    /**
     * Fonction permettant de trouver une valeur à partir d'une clé
     * @param clef
     * @return valeur
     */
    int trouver(int clef) {
        // Initialiation de la variable valeur. Si la clef n'est pas trouvé alors on retourne -1.
        int valeur = -1;
        // Itération dans le tableau pour trouver le bon
        for(int i = 0; i < tableau2D.length; i++) {
            // Vérification de la cle avec l'index courant;
            if (tableau2D[i][0] == clef) {
                // Si oui, arrêter l'exécution et retourner la valeur.
                return tableau2D[i][1];
                // ou valeur = tableau2D[i][1]; break;
            }
        }
        return valeur;
    }
    
    public static void main(String[] args) {
        
        Dictionnaire dict = new Dictionnaire();              
        
        //Trouver la valeur associée à la clé
        System.out.println("Valeur =" + dict.trouver(12));
    }
    
}

Le plus simple est d'utiliser la méthode Arrays.sort.

import java.util.Arrays;
class Main {
  public static void main(String[] args) {
    int[] tableauTest = {4, 6, 9, 1, 2, 76, 222, 5, 22};
    Arrays.sort(tableauTest);
    for (int i : tableauTest) {
      System.out.print(i + " ");
    } 
    System.out.println(); 
  }
}

Voici une solution possible. Elle est grossièrement inefficace sur le plus du temps de calcul: vous pouvez sans doute faire mieux.

import java.util.ArrayList;

public class ArrayListUtils {
    
    public static ArrayList inverser(ArrayList liste) {
        
        ArrayList inverse = new ArrayList();
        
        for(Object o : liste) {
            
            inverse.add(0, o);
        }
        
        return inverse;
    }
    
    public static void main(String[] args) {
        
        ArrayList<String> test = new ArrayList<String>();
        test.add("1");
        test.add("2");
        test.add("3");
        test.add("4");
        test.add("5");
        
        ArrayList<String> testInverse = ArrayListUtils.inverser(test);
        
        for(String s : testInverse) {
            
            System.out.print(s + " ");
        }
    }
    
}

Voici une autre solution (n'oubliez pas 'import java.util.Collections').

ArrayList<String> test = new ArrayList<String>();
test.add("1");
test.add("2");
test.add("3");
test.add("4");
test.add("5");

Collections.reverse(test);
for(String s : test) {
    System.out.print(s + " ");
}

La méthode addAll de la classe ArrayList permet de rapidement faire cette fusion :

import java.util.ArrayList;

public class ArrayListUtils {
    
    public static ArrayList inverser(ArrayList liste) {
        
        ArrayList inverse = new ArrayList();
        
        for(Object o : liste) {
            
            inverse.add(0, o);
        }
        
        return inverse;
    }
    
    public static ArrayList fusion(ArrayList a, ArrayList b) {
        ArrayList liste = (ArrayList) a.clone();
        liste.addAll(b);
        return liste;
    }
    
    public static void main(String[] args) {
        
        ArrayList<String> test = new ArrayList<String>();
        test.add("1");
        test.add("2");
        test.add("3");
        test.add("4");
        test.add("5");
        
        ArrayList<String> listFusion = ArrayListUtils.fusion(test, test);
        
        for(String s : listFusion) {
            
            System.out.print(s + " ");
        }
    }
    
}

Le code affiche « avant le second else ».

En effet le second if est évalué à false, et toute l’instruction qui suit (y compris l’évaluation du else qui se rapporte au if de cette instruction) n’est pas exécutée ; l’instruction suivante c’est le tout dernier if, qui est évalué à true, et donc le else qui s’y rapporte n’est pas évalué.

En a) Instruction n’est pas exécutée et on passe au tour suivant.

En b) on sort de la boucle, Instruction ne sera plus jamais exécutée.

Instruction1 n’est pas exécuté, dans tous les cas lorsque condition est vraie.

Instruction2 est toujours exécuté.

Instruction while.

public class Main {
 public static void main(String[] args) {
   final int NBRE = 10;
   int i=0;
   double harmonique;
   harmonique = 0;
   System.out.println("somme des " + NBRE + " premiers termes de la série harmonique");
   while (i < NBRE) {
     harmonique += (double)1/(i+1);
     i++;
   }
   System.out.println("Somme : " + harmonique);
 }
}

Instruction do…while

public class Main {
 public static void main(String[] args) {
   final int NBRE = 10;
   int i = 0;
   double harmonique;
   harmonique = 0;
   System.out.println("somme des " + NBRE + " premiers termes de la série harmonique");
   do {
     harmonique += (double)1/(i+1);
     i++;
   } while (i < NBRE);
   System.out.println("Somme : " + harmonique);
 }
}

En Java, les tableaux sont initialisées à une valeur nulle par défaut. Dans ce cas, x[0] prendra donc la valeur null. Cette valeur spéciale ne correspond pas à une instance de la classe String. On peut, par contre, assigner une valeur (x[0]="123").

La boucle for est généralement utilisée quand on connaît le nombre d’itérations à l’avance ; la boucle while est utilisée quand on ne le connaît pas.

// Boucle for
for (int i = 0; i < 5; i++) {
    System.out.println(i);
}
// Boucle while
int j = 0;
while (j < 5) {
    System.out.println(j);
    j++;
}

Un tableau a une taille fixe et ne peut pas être redimensionné après sa création. Une ArrayList est une structure de données dynamique qui peut changer de taille et offre des méthodes pratiques pour ajouter, supprimer ou rechercher des éléments.

Une HashMap est une structure de données qui associe des clés à des valeurs. Elle permet de retrouver rapidement une valeur à partir de sa clé. Exemple :

import java.util.HashMap;
HashMap<String, Integer> notes = new HashMap<>();
notes.put("Alice", 85);
notes.put("Bob", 92);
System.out.println(notes.get("Alice")); // Affiche 85

La deuxième insertion écrase la première : la valeur associée à la clé "clé" sera 2. Une HashMap ne peut contenir qu'une seule valeur par clé ; si on ajoute une clé déjà existante, la nouvelle valeur remplace l'ancienne.

On peut utiliser une Stack pour inverser l'ordre des éléments : on empile chaque élément, puis on les dépile un à un (LIFO : Last In, First Out).

import java.util.Stack;
int[] t = {1, 2, 3, 4, 5};
Stack<Integer> pile = new Stack<>();
for (int x : t) {
    pile.push(x);
}
while (!pile.isEmpty()) {
    System.out.println(pile.pop());
}

L’interface CharSequence représente une séquence de caractères et est implémentée par String, StringBuilder, etc. La méthode subSequence(start, end) permet d’obtenir une sous-séquence de caractères.

Exemple :

String texte = "Bonjour le monde";
CharSequence sousTexte = texte.subSequence(8, 14); // "le mon"
System.out.println(sousTexte);

On peut ainsi éviter de faire des copies.

StringBuilder permet de modifier une chaîne sans créer de nouveaux objets à chaque opération, ce qui améliore la performance, surtout dans les boucles. L’opérateur + de la classe String peut créer une nouvelle chaîne à chaque concaténation, ce qui est coûteux en mémoire et en temps.

Exemple :

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 5; i++) {
    sb.append("Ligne ").append(i).append("\n");
}
System.out.println(sb.toString());

Un type ou une classe est dit immuable si son état ne peut pas être modifié après sa création. En Java, les principaux types et classes immuables sont :

• String
• Les classes enveloppes des types primitifs : Integer, Double, Boolean, Long, Short, Byte, Character, Float

L’immuabilité facilite la programmation (pas de risque de modification imprévue), rend les objets sûrs à partager, et simplifie le raisonnement sur le code.

Le premier affichage (str1 == str2) retournera true car les deux variables pointent vers la même chaîne littérale dans le pool de chaînes de Java. Le second (str1 == str3) retournera false car str3 est un nouvel objet créé explicitement, différent de la chaîne littérale, même si leur contenu est identique. Pour comparer le contenu des chaînes, il faut utiliser equals() :

System.out.println(str1.equals(str3)); // true

En Java, les chaînes de caractères sont des objets particuliers : les chaînes littérales (comme “Java”) sont stockées dans une zone spéciale appelée « pool de chaînes ». Quand on écrit deux fois la même chaîne littérale dans le code, Java réutilise le même objet pour économiser de la mémoire. C’est pourquoi str1 == str2 retourne true : les deux variables pointent vers le même objet en mémoire.

En revanche, lorsque l’on crée une chaîne avec new String(“Java”), Java crée explicitement un nouvel objet, même si le contenu est identique à une chaîne littérale existante. Ainsi, str1 == str3 retourne false car les deux variables pointent vers des objets différents.

Pour comparer le contenu de deux chaînes (et non leur emplacement en mémoire), il faut utiliser la méthode equals(). Cette méthode vérifie caractère par caractère si les deux chaînes ont le même contenu, ce qui est généralement ce que l’on souhaite en pratique.

false, true

Le programme affiche 8, 55357, 128512 puis 7.

En Java, une String est une suite d'unités de code UTF-16, c'est-à-dire de valeurs de type char sur 16 bits. Les six premiers caractères (h, é, l, l, o et l'espace) occupent chacun un seul char, mais l'émoji 😀 (point de code U+1F600) n'entre pas dans 16 bits : il est représenté par une paire de substitution, soit deux char. La longueur est donc 6 + 2 = 8, alors que la chaîne ne contient que 7 caractères au sens de l'utilisateur.

charAt(6) retourne le premier élément de la paire (55357, soit U+D83D) : ce n'est pas un caractère utilisable seul. Pour obtenir le vrai point de code, il faut codePointAt(6), qui retourne 128512 (soit U+1F600). Enfin, codePointCount(0, s.length()) compte les points de code plutôt que les char et retourne 7.

Retenez que length() ne donne pas toujours le nombre de caractères perçus, et qu'une boucle for (int i = 0; i < s.length(); i++) s.charAt(i) peut couper un émoji en deux.

• s.substring(3) retourne "jour" : tout ce qui suit l'indice 3, celui-ci compris.
• s.substring(2, 5) retourne "njo" : les indices 2, 3 et 4. La borne de gauche est incluse, celle de droite est exclue. La longueur du résultat est donc simplement 5 - 2 = 3.
• s.substring(7) retourne la chaîne vide "". Ce n'est pas une erreur : demander la sous-chaîne qui commence juste après le dernier caractère est permis.
• s.substring(8) lève une exception StringIndexOutOfBoundsException, car 8 dépasse la longueur de la chaîne (7).

Notez que substring copie les caractères depuis Java 7 : son coût est proportionnel à la longueur de la sous-chaîne extraite, et non constant.

L'idée est de relancer la recherche à partir de la position qui suit l'occurrence trouvée, grâce à la variante indexOf(String, int depart).

static int compter(String texte, String motif) {
    int compte = 0;
    int position = texte.indexOf(motif);
    while (position != -1) {
        compte++;
        position = texte.indexOf(motif, position + motif.length());
    }
    return compte;
}

Avec compter("aaaa", "aa"), cette version retourne 2 : elle trouve l'occurrence en 0, puis repart de l'indice 2 et trouve celle en 2. Elle compte donc les occurrences sans chevauchement.

Si l'on souhaite plutôt compter les occurrences qui peuvent se chevaucher, il suffit de repartir de position + 1 :

position = texte.indexOf(motif, position + 1);

Cette seconde version retourne 3 pour "aaaa" : les occurrences commencent aux indices 0, 1 et 2. Il n'y a pas de bonne réponse dans l'absolu : il faut savoir laquelle des deux on veut. Attention aussi au cas où motif est la chaîne vide : la première version boucle indéfiniment, puisque motif.length() vaut alors 0.

• "pomme".compareTo("poire") retourne 4, une valeur positive : les deux chaînes commencent par po, puis on compare 'm' (109) et 'i' (105), d'où 109 - 105 = 4. La chaîne "pomme" vient donc après "poire".
• "Zèbre".compareTo("abeille") retourne -7, une valeur négative : on compare 'Z' (90) et 'a' (97). Les majuscules ont un code inférieur à celui des minuscules, donc "Zèbre" vient avant "abeille".
• "abc".compareTo("abcd") retourne -1 : quand une chaîne est le préfixe de l'autre, la méthode retourne la différence des longueurs, ici 3 - 4.

Le programme affiche [Abricot, Ananas, banane, cerise]. Ce n'est pas l'ordre du dictionnaire : compareTo compare les valeurs Unicode des caractères, si bien que toutes les majuscules précèdent toutes les minuscules. Les accents posent le même genre de problème. Pour un tri réellement alphabétique en français, il faut utiliser un Collator ou, plus simplement, trier avec String.CASE_INSENSITIVE_ORDER :

java.util.Arrays.sort(mots, String.CASE_INSENSITIVE_ORDER);

Le programme affiche 4 puis [a, b, , c].

On pourrait s'attendre à six éléments, puisque la chaîne contient cinq virgules. Mais split supprime les chaînes vides en fin de tableau. La chaîne vide entre b et c est conservée, car elle n'est pas en fin de tableau, mais les deux dernières disparaissent.

Pour conserver tous les champs, il faut passer une limite négative :

String[] t = "a,b,,c,,".split(",", -1);
System.out.println(t.length);              // 6
System.out.println(Arrays.toString(t));    // [a, b, , c, , ]

C'est un piège classique lorsqu'on lit un fichier au format CSV : les colonnes vides de la fin d'une ligne disparaissent silencieusement.

Le programme affiche :

3-14-15
-------
3-14-15

La différence est essentielle : replace travaille sur du texte littéral, alors que replaceAll attend une expression régulière. Or, dans une expression régulière, le point signifie « n'importe quel caractère ». Le deuxième appel remplace donc chacun des sept caractères de la chaîne par un tiret.

Pour désigner un vrai point dans une expression régulière, il faut le protéger avec une barre oblique inverse, qui doit elle-même être doublée dans une chaîne Java : on écrit "\\.".

En pratique, si vous n'avez pas besoin d'une expression régulière, préférez replace : c'est plus simple, plus rapide, et cela évite ce genre de surprise.

Le programme affiche [bonjour], true, 7, false puis true.

• trim() ne retire que les caractères dont le code est inférieur ou égal à celui de l'espace ordinaire (32). Il nettoie donc a, mais laisse b intact : b.trim().equals(b) vaut true.
• strip(), ajouté en Java 11, reconnaît les espaces au sens d'Unicode. Il retire les cadratins et b.strip() vaut "bonjour", de longueur 7.
• isEmpty() ne teste que la longueur : une chaîne de trois espaces n'est pas vide, donc false.
• isBlank(), également ajouté en Java 11, teste si la chaîne est vide ou ne contient que des espaces : il retourne true.

Il faut donc préférer strip() à trim() dès que le texte peut provenir de l'extérieur (page web, fichier, saisie de l'utilisateur).

On commence par nettoyer la chaîne, puis on la parcourt avec deux indices qui se rapprochent l'un de l'autre.

Le programme affiche true, false puis... false, ce qui est surprenant, car « Ésope reste ici et se repose » est un palindrome célèbre. L'explication tient à l'accent : notre filtre [^a-zA-Z0-9] supprime le É, qui n'est pas dans l'intervalle a-z. La chaîne nettoyée devient "soperesteicietserepose", qui n'est effectivement plus un palindrome.

Une solution consiste à conserver toutes les lettres au sens d'Unicode, avec Character.isLetterOrDigit, et à retirer les accents. C'est un bon rappel : dès qu'on traite du texte en français, les intervalles comme a-z sont insuffisants.

Notez enfin qu'il aurait été plus court d'écrire propre.equals(new StringBuilder(propre).reverse().toString()), mais cette version alloue une chaîne supplémentaire, alors que la boucle ci-dessus n'en alloue aucune et s'arrête dès le premier désaccord.

String[] lignes = new String[noms.length];
for (int i = 0; i < noms.length; i++) {
    lignes[i] = String.format("%-16s %8d", noms[i], population[i]);
}
System.out.println(String.join("\n", lignes));

Le résultat est :

Montréal          1762949
Québec             549459
Trois-Rivières     139163

Dans String.format, %-16s insère une chaîne sur 16 colonnes, alignée à gauche à cause du signe moins ; %8d insère un entier sur 8 colonnes, aligné à droite par défaut. La méthode String.join assemble ensuite les lignes en insérant un saut de ligne entre elles, en une seule allocation.

On aurait pu concaténer les lignes avec + dans la boucle, mais cela crée une nouvelle chaîne à chaque tour. Avec String.join — ou avec un StringBuilder — on ne construit la chaîne finale qu'une seule fois.

Le programme Java ci-dessus implémente le tri par insertion. La méthode insertionSort prend un tableau d’entiers, utilise une boucle pour parcourir les éléments, et insère chaque élément à la bonne position en décalant les éléments plus grands. Le programme affiche le tableau avant et après le tri.

Le programme Java ci-dessus implémente le tri à bulle. La méthode bubbleSort utilise deux boucles imbriquées pour comparer et échanger les éléments adjacents. Le programme affiche le tableau avant et après le tri.

Le programme Java implémente la recherche binaire. La méthode binarySearch prend un tableau trié et un élément cible, utilise une boucle pour ajuster les indices debut et fin, et retourne l’indice de l’élément ou -1 s’il n’est pas trouvé. Le programme affiche un message indiquant le résultat.