Jeu de devinette — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 3)

Jeu de devinette

Instructions de contrôle · niveau 2

Énoncé

Le programme choisit un nombre secret entre $1$ et $100$ . Le joueur propose des nombres ; le programme répond « Trop petit » ou « Trop grand », jusqu'à ce qu'il trouve, puis affiche le nombre d'essais. Quelle boucle convient ? Quelle stratégie garantit de trouver en au plus $7$ essais ?

Corrigé

On propose au moins une fois : boucle do … while.


import java.util.Scanner;

public class Devinette {
    public static void main(String[] args) {
        Scanner clavier = new Scanner(System.in);
        int secret = 37;           // en vrai : (int) (Math.random() * 100) + 1
        int essais = 0;
        int proposition;
        do {
            System.out.print("Votre proposition : ");
            proposition = clavier.nextInt();
            essais++;
            if (proposition < secret) {
                System.out.println("Trop petit");
            } else if (proposition > secret) {
                System.out.println("Trop grand");
            }
        } while (proposition != secret);
        System.out.println("Gagné en " + essais + " essais !");
    }
}

Avec les propositions $50$ , $25$ , $37$ :


Votre proposition : 50
Trop grand
Votre proposition : 25
Trop petit
Votre proposition : 37
Gagné en 3 essais !

La bonne stratégie propose toujours le milieu de l'intervalle encore possible : chaque réponse divise par deux le nombre de candidats. Il y en a $100$ , puis au plus $50$ , $25$ , $13$ , $7$ , $4$ , $2$ , $1$ : au septième essai, il ne reste qu'un candidat. C'est la recherche dichotomique, que le livre Algorithmique étudie en détail.