Corrigé du Contrôle d'Informatique INF 311




Promotion 2003




Sujet proposé par François Morain




7 juillet 2004




Les exercices qui suivent sont indépendants et peuvent être traités dans n'importe quel ordre. On attachera une grande importance à la clarté, à la précision et à la concision de la rédaction.
Exercice 1.

Que calcule la fonction f ci-dessous et qu'affiche le programme?

class Exo1{
    static long faux(long n, long x){
        if(n == 0) return x;
        else return faux(n-1, x*n);
    }
    static long f(long n){
        return faux(n, 1);
    }
    public static void main(String[] args){
        System.out.println(f(5));
    }
}
Corrigé. Il s'agit encore une fois du calcul de n!, ou plus rigoureusement du calcul de n!mod 264.
Exercice 2.

Parmi les trois fonctions données ci-dessous, lesquelles terminent pour toute valeur possible de l'entrée et pourquoi?

static int f(int z){
    if(z <= 0) return 0;
    else return f(z - 1) * f(z - 3);
}

static int g(int w){
    if(w == 1) return 1;
    else{
        if((w % 2) == 1) return g(w/2);
        else return g(w/3);
    }
}

static void h(int a){
    if(a <= 3) return 1;
    else{
        if(h(a/2) == 1) return 2;
        else return 3;
    }
}
Corrigé. La fonction f termine puisque l'argument d'appel décroît et qu'il deviendra donc forcément négatif.

La fonction g ne termine pas tout le temps, puisque par exemple, g(2) demande l'appel à g(0) (puisque 2/3=0), et le programme tourne indéfiniment.

La fonction h termine, puisque l'argument d'appel décroît.
Exercice 3.

Soit k≥ 1 un entier et n = 2k-1. Soit t un tableau de taille n+1=2k contenant des chaînes de caractères représentant un arbre généalogique, comme par exemple: On n'utilise pas t[0], et on met dans t[1] la chaîne Louis XIV, t[2] contient son père, t[3] sa mère, et que plus généralement, t[i] a pour père t[2*i] et mère t[2*i+1] si in/2. Rappelons que le i-ème élément se trouve au niveau l de l'arbre, 0≤ l < k.

On veut afficher cet arbre sous forme non graphique de la façon suivante. On veut que chaque élément de niveau l (0≤ l < k) soit affiché sur une ligne, précédé de 2l blancs sur la ligne. On veut également que chaque nom soit suivi de l'affichage du sous-arbre correspondant à son père, puis suivi de l'affichage du sous-arbre correspondant à la mère. Sur l'exemple donné, l'affichage sera:
Louis XIV
  Louis XIII
    Henri IV
    Marie de Médicis
  Anne d'Autriche
    Philippe III
    Marie-Marguerite d'Autriche
Réalisez cet affichage à l'aide de fonctions récursives.

Corrigé. L'idée est d'utiliser une fonction auxiliaire qui doit afficher le sous-arbre de sommet i, se trouvant au niveau niveau. Il suffit d'écrire t[i] précédé du nombre demandé de blancs, suivi par deux appels récursifs, l'un pour le sous-arbre correspondant au père, l'autre pour la mère.

    static void afficherRecAux(String[] t, int i, int niveau){
        if(i < t.length){
            for(int j = 0; j < niveau; j++)
                System.out.print("  ");
            System.out.println(t[i]);
            afficherRecAux(t, 2*i, niveau+1);
            afficherRecAux(t, 2*i+1, niveau+1);
        }
    }
    static void afficherRec(String[] t){
        afficherRecAux(t, 1, 0);
    }

Exercice 4.

On se propose de reprendre le jeu de bataille entre Alice et Bob, pour programmer le jeu tel qu'on le joue dans la réalité. Rappelons qu'il s'agit d'un jeu qui se joue avec 52 cartes, celles-ci étant réparties en quatre couleurs (trèfle, carreau, coeur, pique) de 13 cartes chacune. On compare les cartes entre elles à l'aide de leur valeur numérique selon la règle suivante: l'ordre sur les cartes est 1 > 13 > 12> 11> ⋯ > 3 > 2. Ainsi le 1 de trèfle l'emporte sur le 3 de pique, etc.

Au début du jeu, Alice et Bob ont chacun un paquet de 26 cartes et, à chaque tour, ils retournent la carte au-dessus de leur paquet et ils comparent les deux cartes. Si la carte d'Alice (cA) est plus forte que celle de Bob (cB), elle prend les deux cartes et les rajoute en dessous de son paquet, en commençant par cA, puis cB. Si c'est cB qui est la plus forte, Bob ajoute en dessous de son paquet, d'abord cB, puis cA. En cas d'égalité, Alice et Bob retournent la carte suivante. Si une décision peut être prise, le vainqueur prend toutes les cartes, sa pile d'abord, celle du perdant ensuite, et les met en-dessous de son paquet. Le jeu s'arrête (éventuellement) quand un des deux joueurs a toutes les cartes.

Pour préciser les choses, considérons le début de partie suivant1 (les colonnes de nombres à gauche et à droite seront expliquées plus loin):

Le premier duel voit s'affronter C1 et T2:
Alice gagne, l'état du jeu est alors
Au coup suivant, Alice retourne P2 et Bob C2:
Il y a bataille, et le coup suivant:
provoque encore une bataille. Viennent ensuite K5 pour Alice et P6 pour Bob:
Celui-ci empoche donc les cartes, ce qui fait que le jeu devient:

Le but de l'exercice est de programmer ces règles. Chaque joueur a besoin de deux objets: un paquet qui contient les cartes à jouer, et une pile de jeu qui contient les cartes en train d'être jouées.

Les questions qui suivent sont relativement indépendantes. En particulier, on peut utiliser les fonctions décrites pour les classes Pile et Paquet dans la programmation du jeu, même si l'implantation de celles-ci n'a pas été donnée.

On donne la classe Carte qui permet de modéliser les cartes:

class Carte{
    String couleur;
    int valeur; // entre 1 et 13

    static Carte creer(String coul, int val){
        Carte c = new Carte();

        c.couleur = coul;
        c.valeur = val;
        return c;
    }
}
Question 2.
En s'aidant du cours, on veut écrire une classe Pile qui permet de gérer les piles de jeu, les cartes étant posées les unes sur les autres en sommet de pile. Dans les fonctions demandées, on prendra soin de mettre à jour les différents champs.
a) Définir la classe en Java. La pile sera constituée d'un tableau t de Carte et d'un entier (hauteur), notée h.
b) Écrire une fonction
    static Pile creer(int nmax){ ... }
qui crée une pile de taille maximale nmax.
c) Écrire une fonction
    static void empiler(Pile p, Carte c){ ... }
qui rajoute une carte au sommet de la pile. On fera l'hypothèse que la pile n'est jamais pleine.
d) Écrire une fonction
    static boolean estVide(Pile p){ ... }
qui retourne true si la pile est vide, et false sinon.
e) Écrire une fonction
    static Carte depiler(Pile p){ ... }
qui enlève la carte au sommet de la pile et la renvoie. On supposera que cette fonction n'est jamais appelée sur une pile vide.
f) Écrire une fonction
    static void vider(Pile p){ ... }
qui remet la pile à sa valeur initiale.

Corrigé.
class Pile{
    Carte[] t;
    int h; // hauteur de la pile

    static Pile creer(int nmax){
        Pile p = new Pile();

        p.t = new Carte[nmax];
        p.h = -1;
        return p;
    }

    static boolean estVide(Pile p){
        return p.h == -1;
    }

    static void empiler(Pile p, Carte c){
        p.t[++p.h] = c;
    }

    static Carte depiler(Pile p){
        return p.t[p.h--];
    }

    static void vider(Pile p){
        p.h = -1;
    }
}
Question 4.
On veut maintenant écrire la classe Paquet qui permet de modéliser un paquet de cartes prêtes à jouer. Un tel objet sera constitué d'un tableau de Carte, appelé t, et de trois entiers h, b, n. L'indice n sera le nombre de cartes présentes dans t; l'indice h sera celui de la prochaine carte à jouer, et b le prochain indice de stockage. On supposera que toutes les fonctions opérant sur des paquets supposent que 0 ≤ h, b < t.length en entrée, et vérifient cette propriété en sortie (voir question 1d ci-dessous).

Pour reprendre l'exemple précédent, le jeu d'Alice sera stocké ainsi:

0 C1
1 P2
2 T3
3 K5
4 C6
25 K12
26 --
51 --
Dans cette configuration, n vaut 26, h vaut 0, b vaut 26.
a) Écrire la définition de la classe Paquet en Java.
b) Écrire une fonction de création d'un Paquet
    static Paquet creer(int nmax){ ... }
qui contiendra au plus nmax cartes. On prendra soin d'initialiser tous les champs avec des valeurs cohérentes.
c) Écrire une fonction
    static boolean estVide(Paquet p){ ... }
qui retourne true si p est vide, false sinon.
d) Écrire une fonction
    static void ajouterEnDessous(Paquet p, Carte c){ ... }
qui ajoute une carte à la fin du paquet et met à jour les champs de p. Comme p.b < p.t.length, il n'y a pas de problème, on peut ranger c à la place p.b. La place suivante est logiquement p.b+1. Si cette valeur est < p.t.length, pas de problème, sinon, on met la valeur de p.b à zéro, ce qui revient à gérer le tableau p.t de façon circulaire. Ainsi, si le paquet d'Alice devait prendre la valeur:
0 --
24  
25 K12
50 C2
51 --
avec p.h = 25, p.b = 51, l'ajout de C1 causerait:
0 --
24  
25 K12
50 C2
51 C1
p.b à prendre la valeur 0, ce qui fait que la carte suivante, P1, prendrait la place 0:
0 P1
24  
25 K12
50 C2
51 C1

e) Écrire une fonction
    static Carte enleverDuDessus(Paquet p){ ... }
qui retourne la prochaine carte à jouer du paquet. On supposera que cette fonction n'est pas appelée sur un paquet vide. On mettra à jour les différents champs, et on n'oubliera pas de gérer circulairement l'indice p.h.
f) Écrire une fonction d'affichage du paquet
    static void afficher(Paquet p){ ... }
On supposera qu'on n'affiche jamais un paquet vide.

Corrigé.
class Paquet{
    Carte[] t;
    int h; // h est l'indice du haut
    int b; // b est le prochain indice à utiliser
    int n; // nombre de cartes

    // on stocke entre les indices h et b, gérés de façon circulaire
    static Paquet creer(int nmax){
        Paquet p = new Paquet();

        p.t = new Carte[nmax];
        p.h = 0;
        p.b = 0;
        p.n = 0;
        return p;
    }

    static boolean estVide(Paquet p){
        return p.n == 0;
    }

    static void ajouterEnDessous(Paquet p, Carte c){
        p.t[p.b] = c;
        p.n++;
        p.b++;
        if(p.b == p.t.length)
            p.b = 0;
    }

    static Carte enleverDuDessus(Paquet p){
        Carte c = p.t[p.h];

        p.h++;
        if(p.h == p.t.length)
            p.h = 0;
        p.n--;
        return c;
    }

    static String chaineCourte(Carte c){
        String s = "";

        if(c.couleur.equals("trèfle")) s = "T";
        else if(c.couleur.equals("carreau")) s = "K";
        else if(c.couleur.equals("coeur")) s = "C";
        else if(c.couleur.equals("pique")) s = "P";
        return s + c.valeur;
    }

    static void afficher(Paquet p){
        int i;

        i = p.h;
        do{
            System.out.println(i+" "+chaineCourte(p.t[i]));
            i++;
            if(i == p.t.length)
                i = 0;
        } while(i != p.b);
    }
}
Question 6.
Écrire une fonction
    static void transferer(Paquet pG, Pile pile){ ... }
qui transfère le contenu de la pile pile en dessous du paquet pG.

Corrigé.
    static void transferer(Paquet pG, Pile pile){
        while(!Pile.estVide(pile))
            Paquet.ajouterEnDessous(pG, Pile.depiler(pile));
    }
Question 8.
Nous disposons maintenant des outils nécessaires à la programmation du jeu.

La fonction que l'on demande de programmer dans la classe Bataille est:
    static int jouerAB26(Paquet pA, Paquet pB){ ... }
pA et pB sont les paquets d'Alice et Bob, déjà distribués et prêts à être joués.

Nous rappelons qu'il existe une fonction (dans la classe Bataille):
    static int comparerCartes(Carte cA, Carte cB){ ... }
qui retourne -1 si cA est plus faible que cB, +1 si c'est le contraire, et 0 en cas d'égalité.

Dans cette question, on suppose qu'on ne joue que 26 duels, comme fait en cours. Alice et Bob auront besoin chacun d'une pile de jeu, vide au commencement du jeu. À chaque étape, Alice prend la carte cA du dessus de son paquet, et la met sur sa pile de jeu. Bob fait de même avec sa carte cB sur sa pile. Si cA est plus forte que cB, alors Alice met sa pile de jeu en dessous de son paquet, suivie de la pile de jeu de Bob. Réciproquement, si cB est plus forte que cA, Bob met sa pile en dessous de son paquet, suivie de celle d'Alice. En cas de bataille, les piles de jeu restent en l'état et sont enrichies par le coup qui suit.

À la fin de ces 26 duels, on renvoie le gain d'Alice, c'est-à-dire le nombre de cartes restant dans son paquet, moins le nombre de cartes restant dans le paquet de Bob. On ne tiendra pas compte d'une éventuelle bataille en cours. Programmer le jeu.

Corrigé.
    static int jouerAB26(Paquet pA, Paquet pB){
        Pile pjeuA = Pile.creer(NCARTES), pjeuB = Pile.creer(NCARTES);
        Carte cA, cB;
        int cmp, gainA = 0;

        while(!Paquet.estVide(pA)){
            cA = Paquet.enleverDuDessus(pA);
            Pile.empiler(pjeuA, cA);
            cB = Paquet.enleverDuDessus(pB);
            Pile.empiler(pjeuB, cB);
            cmp = comparerCartes(cA, cB);
            if(cmp == +1){
                gainA += 2 * (pjeuA.h+1);
                // on n'oublie pas de vider les piles
                Pile.vider(pjeuA);
                Pile.vider(pjeuB);
            }
            else if(cmp == -1){
                gainA -= 2 * (pjeuA.h+1);
                // on n'oublie pas de vider les piles
                Pile.vider(pjeuA);
                Pile.vider(pjeuB);
            }
            else{ // cas d'égalité : bataille!
                System.out.println(" -> BATAILLE "+pjeuA.h);
            }
        }
        return gainA;
    }
Question 10.
(Variante "Guerre éternelle"2) Cette fois, nous autorisons le jeu à se prolonger jusqu'à la défaite totale d'un adversaire. Autrement dit, on continue le jeu jusqu'à ce qu'un des paquets soit vide. Si les deux paquets sont vides, on retourne 0, les deux joueurs sont ex-æquo.

a) Modifier la fonction précédente en conséquence.

Corrigé.
    static int jouerAB(Paquet pA, Paquet pB){
        Pile pjeuA = Pile.creer(NCARTES), pjeuB = Pile.creer(NCARTES);
        Carte cA, cB;
        int cmp; 

        while((pA.n != 0) && (pB.n != 0)){
            cA = Paquet.enleverDuDessus(pA);
            Pile.empiler(pjeuA, cA);
            cB = Paquet.enleverDuDessus(pB);
            Pile.empiler(pjeuB, cB);
            cmp = comparerCartes(cA, cB);
            if(cmp == +1){
                // on ajoute la pile de jeu de A, puis celle de B
                transferer(pA, pjeuA);
                transferer(pA, pjeuB);
            }
            else if(cmp == -1){
                // on ajoute la pile de jeu de B, puis celle de A
                transferer(pB, pjeuB);
                transferer(pB, pjeuA);
            }
            else{ // cas d'égalité : bataille!
                // on n'a rien à faire, car on a des piles de jeu
            }
        }
        return (pA.n - pB.n);
    }
b) Comment peut-on faire pour tester le programme ? Quel cas limite serait-il intéressant de tester?

Corrigé. Il est prudent de se fabriquer la pire partie possible, celle où Alice et Bob ont le même jeu, c'est-à-dire par exemple Alice a les trèfles et carreaux classés dans l'ordre 1 à 13, et Bob les coeurs et piques dans le même ordre, de façon à provoquer 26 batailles.

Question 12.
On maintient la prolongation du jeu indiquée à la question précédente. Toutefois, on modifie la règle en cas de bataille. Si deux cartes sont trouvées égales, chacun met en gage sur sa pile de jeu la carte suivante de son paquet (si c'est impossible, le jeu se termine). Le sort de ces cartes est déterminé par le duel entre les cartes suivantes. Ainsi, dans le cas où Alice a pour paquet:
C1
T2
P3
et Bob
P1
K3
K4
Les piles de jeu consécutives à la première bataille seraient
T2    K3
C1    P1
et le sort des 6 cartes déterminé par le duel suivant
P3    K4
T2    K3
C1    P1
que Bob emporte dans ce cas.

a) Écrire la fonction jouerAB en modifiant la fonction jouerAB26 pour tenir compte de cette nouvelle règle.

Corrigé.
    static int jouerAB(Paquet pA, Paquet pB){
        Pile pjeuA = Pile.creer(NCARTES), pjeuB = Pile.creer(NCARTES);
        Carte cA, cB;
        int cmp; 

        while((pA.n != 0) && (pB.n != 0)){
            cA = Paquet.enleverDuDessus(pA);
            Pile.empiler(pjeuA, cA);
            cB = Paquet.enleverDuDessus(pB);
            Pile.empiler(pjeuB, cB);
            cmp = comparerCartes(cA, cB);
            if(cmp == +1){
                // on ajoute la pile de jeu de A, puis celle de B
                transferer(pA, pjeuA);
                transferer(pA, pjeuB);
            }
            else if(cmp == -1){
                // on ajoute la pile de jeu de B, puis celle de A
                transferer(pB, pjeuB);
                transferer(pB, pjeuA);
            }
            else{ // cas d'égalité : bataille!
                // c'est là qu'on rajoute des choses
                if(Paquet.estVide(pA) || Paquet.estVide(pB)){
                    System.out.println("A ou B est vide!");
                    break;
                }
                Pile.empiler(pjeuA, Paquet.enleverDuDessus(pA));
                Pile.empiler(pjeuB, Paquet.enleverDuDessus(pB));
            }
        }
        return (pA.n - pB.n);
    }
b) Quel est l'effet recherché avec cette variante ?

Corrigé. On cherche à permettre une meilleure répartition des cartes, en particulier éviter que les 4 as n'entraînent la victoire inéluctable de celui ou celle qui les détient.


1
On a noté en abrégé T pour trèfle, K pour carreau, C pour coeur, et P pour pique.
2
Joe Haldeman, prix Hugo et Nébula 1976

Ce document a été traduit de LATEX par HEVEA.