TD-6, arbres
Programmes Prenom.Nom.c à déposer par ftp sur poly en /users/profs/maranget/TD-6.
1 Jeu des allumettes simplifié
Au début de ce jeu il y a n allumettes sur la
table.
Puis, chaque joueur à tour de rôle ôte une ou deux
allumettes, selon son choix, et les garde.
Le jeu se termine lorsqu'il n'y a plus d'allumettes sur la table, le joueur
qui a enlevé la dernière allumette ayant perdu.
En outre, le perdant doit
payer au gagnant une somme proportionnelle au nombre d'allumettes
détenues par le gagnant.
1.1 Arbre de jeu
On demande de créer un arbre qui représente toutes les parties
possibles, pour n donné. Les noeuds de cet arbre contiennent un
entier qui est le nombre d'allumettes détenues par celui qui va jouer.
De ce noeud partent au plus deux fils, chaque fils correspondant à
la prise de une ou deux allumettes.
Voici par exemple l'arbre de jeu pour n=4, le joueur gris étant le
premier à jouer.
On utilisera le type des cellules d'arbres et la fonction de
construction suivantes :
typedef struct cell {
int val;
struct cell *un,*deux;
} *Tree;
Tree cons_cell(int val, Tree un,Tree deux)
{
Tree r;
r = (Tree )malloc(sizeof(struct cell));
if ( r == NULL) {
fprintf(stderr,"Plus de memoire\n");
exit(-1);
}
r->val = val;
r->un = un;
r->deux = deux;
return r;
}
Une fois l'arbre construit, l'afficher sous forme préfixe. Dans le cas
n=4, on a :
0 0 1 1 2 1 1 2 0 2 1 2
1.2 Espérance des gains
Observez qu'une feuille de l'arbre termine une partie qui est gagnante
pour le joueur qui devrait jouer. Par conséquent les feuilles contiennent le
gain du gagnant (ou la perte du perdant, selon le point de vue).
Le jeu a quatre allumettes a la propriété que l'espérance des gains
est nulle. En effet, en calculant le solde des gains et pertes sur
toutes les parties possibles pour le
joueur gris, on trouve 2+(-1)+(-2)+(-1)+2 = 0.
On demande de calculer le solde des gains et des pertes du joueur gris
pour d'autres valeurs de n.
La solution apparaîtra ici.
2 Morse
Voici l'alphabet morse, donné comme un tableau de 26 chaînes :
char *morse[] = {
".-", "-...", "-.-.", "-..", ".", ".-..", "--.", "....", "..", ".---",
"-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...",
"-", "..-", "...-", ".---", "-..-", "-.--", "--.."
};
Étant donné un caractère c, compris entre 'a' et
'z', on accède donc au code morse de c par l'expression
``morse[c - 'a']''.
2.1 Encodage
On demande d'abord d'encoder un message lu au clavier.
Rappelons qu'en code morse, deux lettres d'un même mot sont séparées
par ``/'' et deux mots par ``//''.
On lit un caractère au clavier par la fonction getchar(), qui
retourne le caractère lu.
Voici un exemple d'encodage :
Entrez une ligne en clair : bonne annee
/-.../---/-./-././/.-/-./-./././
2.2 Arbre de décodage
Pour décoder les messages en morse, on construit tout d'abord un
arbre, dans l'esprit de l'arbre de décodage de Huffman.
Dans le cas du morse, cet arbre est le suivant :
On décode un caractère morse en descendant dans l'arbre : un point
signifie prendre le fils gauche, un trait prendre le fils droit,
lorsque l'on a mangé tous les points et les traits, le contenu du
noeud courant de l'arbre de décodage donne la signification du caractère
décodé. Par exemple, soit le caractère morse, ``.--''. En
descendant une fois à gauche, puis deux fois à droite dans l'arbre, on
trouve son décodage : ``w''.
On demande de construire l'arbre de décodage par insertion successive
de toutes les lettres de l'alphabet. Autrement dit,
votre programme doit engendrer l'arbre ci-dessus, mais surtout pas en
contenir une bête copie. Vous aurez cette fois ci à définir vous-même
le type des cellules d'arbres et à écrire le constructeur.
2.3 Décodage
Utiliser l'arbre de décodage pour
décoder un message en morse lu au clavier :
Entrez une ligne en code : /-.../---/-./-././/.-/-./-./././
bonne annee
La solution de cet exercice apparaîtra ici.
Ce document a été traduit de LATEX par
HEVEA.
