juin 2003 i3

Université d'Aix-Marseille 3

DEUG Sciences - Mention MIAS

I3 - Informatique - juin 2003

Avant propos. Toutes les réponses de programmation devront impérativement être rédigées dans le langage C. Les problèmes 1 , 2 et 3 peuvent être traités indépendamment.

Problème 1. - Fonctions et récursivité - (4 points)

Question 1 Définissez une fonction récursive prenant en entrée un entier strictement positif n et calculant la valeur de u_n où u₀=3 et u_n=4*u_n-1-1 pour n>0.

Question 2 Définissez une fonction C récursive prenant en entrée un entier strictement positif n et calculant la valeur de u_n où
u₀=1, u₁=3 et u_n=3 * u_n-1 - 4 * u_n-2 pour n>1. Dessinez l'arborescence des appels recursifs pour n=4.

Problème 2 - Conception et exploitation de fonctions - (7 points)

Dans ce problème, nous nous intéressons à la programmationdu jeu de Darnes. L'objectif de ce problème n'est pas de réaliser l'intégralité d'un programme qui permettrait à ordinateur de jouer aux Dames, mais de programmer quelques fonctions, qui sont à priori nécessaires pour réaliser un tel programme. Tout d'abord quelques éléments de base sur le jeu. Ce jeu se déroule sur un damier qui corresponde à une grille 10 x 10, indicée de A à J pour les colonnes et de 1 à 10 pour les rangées, et dont les cases sont soit blanches, soit noires. Il existe deux camps, le camp blanc et le camp noir.
1e camp blanc possède en début de partie 20 pions, répartis sur les cases blanches en bas de damier ; il en est de même pour le camp noir sur le haut du damier comme schématisé ci-dessous :

Notons que dans ce problème, nous ne considèrerons jamais le cas des dames, mais uniquement celui des pions. Selon les règles du jeu, les pions de chaque camp sont déplacés alternativement par chaque camp. D'abord le camp blanc, puis le camp noir. Nous considèrerons, dans le cadre de ce problème, 2 types de déplacement des pions.

Tout d'abord, le"déplacement simple " qui est régi par les règles suivantes :

les pions se déplacent en diagonale d'une case seulement
les pions blancs doivent "monter" tandis que les pions noirs doivent "descendre" (en fait chaque camp doit avancer vers le camp de l'adversaire)
un pion ne peut se déplacer sur une case que si celle-ci est inoccupée

L'autre type de déplacernent sera pour nous "la prise simple" :

les pions se déplacent en diagonale de deux cases exactement
les pions peuvent avancer ou reculer
un pion ne peut se déplacer sur une case que si celle-ci est inoccupée
un pionne peut passer sur une case que si celle-ci est occupée par un pion du camp adverse ; le pion adverse est alors pris, la case qu'il occupait devient alors vide.
par exemple, si un pion blanc est situé sur la cas A4, et qu'un pion noir est situé sur la case B5, et que 1a case C6 est vide, alors le pion blanc "prend" le pion noir (il est enlevé du damier) en se positionnant sur la case C6.

Ceux qui connaissent précisement les règles du jeu peuvent constater que nous ne prenons pas et compte ici 1'obligation faite de poursuivre, lors de l'exécution d'un coup, une prise si celle-ci est possible à partir de la case d'arrivée. Nous prenons cette liberté avec les règles officielles du jeu afin de simplifier notre problème.

Pour représenter les informations qui nous seront nécessaires dans ce problème, nous utiliserons te types C fournis ci-dessous :

/* piece : 'P' pour pion ou ' ' */
typedef char Tpiece;

/* couleur du pion occupant éventuellement une case : */
/* 'B' pour Blanc, 'N' pour Noir ou 'V' pour vide */
typedef char couleur;

/* contenu d'une case */
typedef struct { Tcouleur coul;
Tpiece piece;
Tcase; }

/* damier : la case d'indice [0][0] désigne la case (1,A) */
/* c'est à dire la case sur la colonne A et la rangée 1 */
typedef Tcase Tdamier [10][10];

/* coordonnees de case ans le damier */
typedef struct { int r,c;) Tcoord;

Notons que dans la représentation du damier fournie ci-dessus, les rangées sont indicées de 1 à 10 tandis que les colonnes le sont de 'A' à 'J'. Dans les structures de données, il est clair que ces indices vont varier dans l'intervalle entier [0][9].

Question 1 Définissez une fonction C qui prenden entrée les coordonnées d'une case et une variable dm de type Tdamier et fournit en résultat 1 si la case considérée dans le damier dm est vide et 0 sinon.

Question 2 Définissez la procédure C appelée init_ damier spécifiée ci-dessous et qui permet d'initialiser pour le début de la partie, un damier dm de type Tdamier.

void init_damier (Tdamier dm)
/* spécifications : réalise l'initialisation du damier dm avec un remplisage des cases en position de début de partie*/

Question 3 Définissez la fonction C appelée pdavg spécifiée ci-dessous et qui permet de savoir si un Pion peut se Déplacer en AVant vers la Gauche. Nous précisons qu'avancer veut dire progresser vers le camp adverse, à savoir monter pour les blancs, et descendre pour les noirs.

int pdavg(Tdamier dm, Tcoord pos)
/* spécifications : a pour résultat 1 ssi le pion en pos peut se déplacer en avançant vers la gauche.*/

Question 4 Définissez la fonction C appelée ppavd spécifiée ci-dessous et qui permet de savoir si un Pion peut Prendre un pion adverse en AVançant vers la Droite.

int ppavd (Tdamier dm, Tcoord pos)
/* spécifications : a pour résultat 1 ssi le pion en pos peut prendre en avançant vers la droite.*/

Question 5 Définissez la procédure C appelée coups_possibles et spécifiée ci-dessous qui affiche la liste des coups possibles pour un camp donné dans une position donnée. Dans cette version, nous ne ferons pas de distinction entre prises simples et déplacements. !afin de faciliter votre programmation, nous supposeont que les fonctions pdavg, pdavd, et ppavg, ppavd, pparg, ppard (ar pour ARrière), sont déjà définies. Elles correspondent aux différents tests de déplacement possibles (pour les 2 premières) et de prises possibles (pour les 4 dernières).

void coups_possibles (Tdamier dm, Tcouleur coul)
/* spécifications : étant donné le camp de couleur coul et le damier dm, cette procédure affiche tous les coups possibles, prises simples et déplacements, */
/* pour le camp considéré en indiquant à chaque fois la case de départ et celle d'arrivée. */

Question 6 Quelle structure de données serait la mieux adaptée pour mémoriser les coups possibles pour un camp donné ?

Problème 3 - Pointeurs et listes simplement chaînées - (9 points)

L'objectif de ce problème est d'étudier la manipulation de séquences de caractères représents par des listes simplemnt chaînées. Vous utiliserez le type C donné ci-dessous :

struct chainon { char info;
struct chainon *suiv; };
typedef struct chainon cellule;
typedef struct chainon *liste;

Question 1 Représentez schématiquement l'état de la mémoire à l'issue de l'exécution des lignes d'instructions données ci-desous. L'état lors des étapes intermédiaires n'est pas demandé. Indiquez ensuite les valeurs affichées.

liste a,b,c;
a = (liste) malloc (sizeof(cellule));
a ^_ > info = 'b';
a ^_>suiv = NULL;
b ^_ > info = 'c';
b^_>suiv = NULL;
c ^_ > info = 'a';
c ^_>suiv = NULL;
printf("%c", a ^_ > info); printf("%c", b ^_ > info); printf("%c", c ^_ > info);

Question 2 Ecrivez les lignes d'instructions C permetant de construire, à la suite de l'execution des lignes d'instruction de la question 1, une liste simplement chaînée contenant dans l'ordre les caractères 'a','b' et 'c'.

Question 3 Ecrivez les lignes d'instructions C permetant d'insérer à la fin de la liste construite dans la question 2, un nouvel élément dont la valeur sera le caractère 'z'. L'accès à la liste devra être identique à ce qu'il était à l'issue de l'exécution des lignes d'instructions de la question 2, c'est à dire que la liste devra toujours être pointée par le même pointeur.

Question 4 Définissez une fonction C prenant en entrée une variable car de type char et une variable seq de type liste, pointant sur une liste contenant au moins un élément, et fournissant en résultat 1 si la liste contient le caractère car, et 0 dans le cas contraire.

Question 5 Définissez une fonction C prenant en entrée une variable seq de type liste pointant sur une liste, et fournissant en résultat le nombre de caractères contenus dans la liste.

Question 6 Définissez une fonction C prenant en entrée une variable seq de type liste pointant sur une liste, et fournissant en résultat le nombre de voyelles contenus dans la liste.

Question 7 Définissez une fonction C prenant en entrée une variable seq de type liste pointant sur une liste, et supprimant de cette liste toutes les voyelles qu'elle contient.

Question 8 Définissez une fonction C prenant en entrée une variable seq de type liste pointant sur une liste, et fournissant en résultat 1 si les caractères apparaissent dans l'ordre alphabétique dans la liste.