|
Université
de la Polynésie Française |
Examen
Algo/Prog Deug MIAS 2 Année
2003-04 Mercredi 14
Janvier 2004 |
0. Modalités
1.Vous disposez de trois heures,
2.vos documents personnels sont autorisés,
3.le code C sera commenté,
4.le barème est donné à titre indicatif et est susceptible d'être modifié,
1. Ecrire l’algorithme du tri fusion (env. 3 pts)
Le tri fusion est construit suivant la stratégie "diviser pour régner", en anglais "divide and conquer" dont nous avons déjà parlé à plusieurs reprises. La méthode de ce tri consiste donc à trier deux sous tableaux de taille égale, puis à fusionner les deux sous tableaux résultats.
L'algorithme demandé ici est récursif. En effet, les deux sous tableaux seront eux même triés à l'aide de l'algorithme de tri fusion. Un tableau ne comportant qu'un seul élément sera considéré comme trié : c'est la condition sine qua non sans laquelle l'algorithme n'aurait pas de conditions d'arrêt.
Etapes de l'algorithme :
- Division de l'ensemble de valeurs en sous-listes
- Tri en place de chacune des deux sous-listes
- Fusion en place des deux sous-listes triées
Ecrire en pseudo-code l’algorithme récursif demandé (quelques lignes très simples) tout en supposant disposer (il ne faut pas l’écrire !!) d’un sous-programme fusion (L, i, j, k) capable de fusionner les deux sous listes définies respectivement par L[i]..L[j] et L[j+1]..L[k].
2. Ecrire en C le tri bulle d’un jeu de cartes
Un jeu de cartes est représenté par les types C suivants :
#define
NB_CARTES 52
typedef
struct carte {
char couleur;
int niveau;} carte;
typedef carte lcartes[NB_CARTES];
La couleur est l'un des identificateurs A(cArreau), C(Coeur), P(Pique), T(Trèfle) avec la relation d'ordre A > C > P > T.
Le niveau sera un entier entre 1 et 13 avec la relation d'ordre classique (le 1 est donc plus petit que toutes les autres cartes de sa couleur).
2.1. Ecrire en C un prédicat de comparaison de deux cartes (env. 3 pts)
2.2. Ecrire en C le tri bulle d’un paquet de cartes (env. 3 pts)
3. Jeu de « FreeCell »
Le FreeCell est un jeu de cartes de type réussite se jouant seul(e) avec un jeu de 52 cartes. Le jeu se joue sur une « grille » de 8 colonnes sur un maximum de 13 lignes.
La position de départ consiste à remplir la « grille » de 8 colonnes jusqu’à épuisement des 52 cartes (cf. image ci-dessous).
Nous supposerons :
- qu’une carte et un paquet de cartes sont représentés par les types C de l’exercice précédant ;
- que le paquet de 52 cartes est déjà construit et mélangé ;
- que nous disposons d’une procédure d’affichage d’UNE carte affiche_carte(carte c) ;
3.1. Définir une structure de données permettant de représenter le tapis de FreeCell (cartes disposés sur des lignes et des colonnes) (env. 1 pt)
3.2. Ecrire en C une procédure/fonction permettant de remplir le champs de jeu avant de démarrer une partie (env. 3 pts)
3.3. Ecrire en C une procédure/fonction permettant d’afficher correctement le champs de jeu avec ses cartes (env. 2 pts)
4. Comprendre et expliquer ce que fait le code C suivant (env. 5 pts)
Remarque : la réponse peut tenir en une ligne !
#define MAX
15
typedef
struct liste {
int taille;
int elts[MAX];
}liste;
void mystere(liste *tableau, int deb1, int fin1, int fin2)
{ liste table1;
int
deb2, compt1, compt2, i;
deb2=fin1+1;
compt1=deb1;
compt2=deb2;
for(i=deb1;i<=fin1;i++)
{ table1.elts[i-deb1]=tableau->elts[i]; }
for(i=deb1;i<=fin2;i++)
{
if (compt1==deb2)
else if (compt2==(fin2+1))
{
tableau->elts[i]=table1.elts[compt1-deb1];
compt1++;
}
else if
(table1.elts[compt1-deb1]<tableau->elts[compt2])
{
tableau->elts[i]=table1.elts[compt1-deb1];
compt1++;
}
else
{
tableau->elts[i]=tableau->elts[compt2];
compt2++;
}
}
}