1. Tableaux
Cette section illustre l'utilisation de tableaux en langage C.
Exercice 1.1.
Ecrire un programme tp4-ex11.c contenant une fonction void affiche(int t[], unsigned int n) qui affiche le tableau t de taille n passé en argument sur la sortie standard. La forme de l’affichage doit être : [ t[0], t[1], …, t[n] ]. Si le tableau est vide, la fonction affiche simplement [ ]. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur un tableau de 5 éléments et l’affiche ensuite dans la bonne forme.
Exemple d’exécution
Element 1/5: 2
Element 2/5: 3
Element 3/5: 4
Element 4/5: 5
Element 5/5: 6
Tableau saisi: [ 2, 3, 4, 5, 6 ]
Exercice 1.2.
Ecrire un programme tp4-ex12.c contenant une fonction int somme(int t[], unsigned n) qui calcule et retourne la somme des éléments d’un tableau t de taille n. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur un tableau de 5 éléments et en affiche la somme.
Exemple d’exécution
Element 1/5: 2
Element 2/5: 3
Element 3/5: 4
Element 4/5: 1
Element 5/5: 1
Somme: 11
Exercice 1.3.
Ecrire un programme tp4-ex13.c contenant une fonction void extremum(int t[], unsigned int n, int* min, int*max) qui calcule les extremum (valeurs minimum et maximum) d’un tableau t de taille n et qui les stocke respectivement dans les variables min et max. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur un tableau de 6 éléments et en affiche les extremum.
Exemple d’exécution
Element 1/6: 2
Element 2/6: 3
Element 3/6: 4
Element 4/6: 1
Element 5/6: 7
Element 6/6: 5
Minimum tableau: 1
Maximum tableau: 7
Exercice 1.4.
Ecrire un programme tp4-ex14.c contenant une fonction void inverse(int t[], unsigned int n) qui inverse le tableau t de taille n passé en argument. L’inverse d’un tableau $t$ de taille $n$ est un tableau $t’$ tel que $t^\prime\left[i\right]=t\left[n-i\right],\ 0\le i<n$. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur un tableau de 7 éléments et en afficher l’inverse.
Exemple d’exécution
Element 1/7: 1
Element 2/7: 2
Element 3/7: 3
Element 4/7: 4
Element 5/7: 5
Element 6/7: 6
Element 7/7: 7
Tableau original: [ 1, 2, 3, 4, 5, 6, 7 ]
Tableau inverse: [ 7, 6, 5, 4, 3, 2, 1 ]
2. Tri de tableaux
Il existe de nombreux algorithmes de tri pour ordonner les éléments d'un tableau. Chacun ayant ses avantages et ses inconvénients.
2.1. Tri sélection
le tri sélection est un un algorithme de tri utilisant la comparaison d'éléments 2 à 2. Cet algorithme est simple mais est relativement inefficace car pour un tableau de taille $n$ il s'exécute en temps quadratique $O(n^2)$. L'algorithme du tri sélection est le suivant:
algorithme tri_selection(tableau t)
variable n entier
variable i entier
n $\leftarrow$ longueur(t)
i $\leftarrow$ 0
tanque i < n - 1 faire
min $\leftarrow$ i
j $\leftarrow$ i + 1
tantque j < n faire
si t[j] < t[min] alors
min $\leftarrow$ j
finsi
j $\leftarrow$ j + 1
fintq
si min $\neq$ i alors
échanger(t[i], t[min])
finsi
i $\leftarrow$ i + 1
fintq
fin
Exercice 2.1.
Ecrire un programme tp4-ex21.c contenant une fonction void tri_selection(int t[], unsigned int n) qui trie le tableau t de taille n passé en argument en utilisant l’algorithme de tri par sélection. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur un tableau de 5 éléments et d’afficher le tableau une fois trié.
Exemple d’exécution
Element 1/5: 3
Element 2/5: 2
Element 3/5: 5
Element 4/5: 4
Element 5/5: 1
Tableau original: [ 3, 2, 5, 4, 1 ]
Tableau trie: [ 1, 2, 3, 4, 5 ]
2.2. Tri à bulles
Le tri à bulles est un algorithme permettant de trier un tableau en comparant répétitivement ses éléments consécutifs et en les permutant lorsqu'ils sont mal triés. Cet algorithme doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide. Tout comme le tri sélection, pour un tableau de taille $n$ le tri à bulles s'exécute en temps quadratique $O(n^2)$.
L'algorithme du tri à bulles est le suivant:
algorithme tri_a_bulles(tableau t)
variable n entier
variable i entier
n $\leftarrow$ longueur(t)
i $\leftarrow$ n - 1
tantque i $\geq$ 1 faire
j $\leftarrow$ 0
tantque j $\leq$ i - 1 faire
si t[j+1] < t[j] alors
echanger(t[j], t[j+1])
finsi
j $\leftarrow$ j + 1
fintq
i $\leftarrow$ i - 1
fintq
fin
Exercice 2.2.
Ecrire un programme tp4-ex22.c contenant une fonction void tri_bulle(int t[], unsigned int n) qui trie le tableau t de taille n passé en argument en utilisant l’algorithme de tri à bulle. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur un tableau de 6 éléments et d’afficher le tableau une fois trié.
Exemple d’exécution
Element 1/6: 4
Element 2/6: 6
Element 3/6: 7
Element 4/6: 2
Element 5/6: 1
Element 6/6: 3
Tableau original: [ 4, 6, 7, 2, 1, 3 ]
Tableau trie: [ 1, 2, 3, 4, 6, 7 ]
3. Jeu du Morpion
Le but de cette partie du TP est de réaliser un jeu de morpion en C
Le jeu de morpion repose sur un plateau qui sera représenté par un tableau d’unsigned char à deux dimensions de taille 3x3. Chaque case du tableau peut contenir une valeur parmi :
- ' ' le caractère espace.
- 'X' le caractère X qui est le symbole du joueur 1.
- 'O' le caractère O qui est le symbole du joueur 2.
Un exemple de plateau en cours de partie est le suivant :
[ X ]
[ O X ]
[ O O ]
Le déroulement de la partie est le suivant :
- Le plateau de jeu est initialisé avec des espaces ' '
- Le joueur 1 place un symbole 'X' sur une case vide
- Si 3 symboles du joueur 1 sont alignés, il gagne la partie
- Le joueur 2 place un symbole 'O' sur une case vide
- Si 3 symboles du joueur 2 sont alignés, il gagne la partie
- Si aucun des 2 joueurs n’a gagné et s’il reste au moins une case libre, on reprend on point 2
Exercice 3.1.
Créer un fichier tp4-morpion.c. C'est dans celui-ci que seront ajoutées toutes les fonctions nécessaires à la programmation du jeu. Ajouter à tp4-morpion.c une fonction main qui déclare une variable plateau comme un tableau de char à deux dimensions de taille 3 x 3 et initialise chacune de ses cases avec le caractère espace ' '.
Exercice 3.2.
Dans le fichier tp4-morpion.c, ajouter une fonction void affiche(char plateau[][3]) qui affiche le plateau de jeu dans la console sous la forme :
[ X ]
[ O X ]
[ O O ]
Modifier la fonction main du programme pour tester l'affichage du tableau {{' ', 'X', ' '}, {'O', ' ', 'X'}, {'O', ' ', ' O'}}
Remarque: Dans le cadre du langage C, lors du passage d'un tableau à 2 dimensions à une fonction, seule la taille de la seconde dimension est nécessaire. Ceci est du au fait qu'un tableau est toujours stocké en mémoire sous forme d'un tableau à 1 dimension.
Exercice 3.3.
Dans le fichier tp4-morpion.c, ajouter une fonction char case_valide(int ligne, int colonne, char plateau[][3]) qui retourne 1 si la case (ligne, colonne) du plateau est valide et 0 sinon. Une case est valide si elle satisfait toutes les conditions suivantes :
- ligne est positive et strictement inférieure à 3.
- colonne est positive et strictement inférieure à 3.
- la case plateau[ligne][colonne] contient le caractère espace ' '.
Modifier la fonction main du programme pour créer un plateau avec les valeurs: {{' ', 'X', ' '}, {'O', ' ', 'X'}, {'O', ' ', ' O'}}. et tester ensuite la fonction case_valide sur différentes cases en affichant sur la console si elles sont valides ou non.
Exemple d'exécution:
case (0, 0) valide.
case (0, 1) invalide.
case (0, 2) valide.
case (1, 0) invalide.
case (1, 1) valide.
case (1, 2) invalide.
case (2, 0) invalide.
case (2, 1) valide.
case (2, 2) invalide.
Exercice 3.4.
Dans le fichier tp4-morpion.c, ajouter une fonction char case_libre(char plateau[][3]) qui retourne 1 si le plateau contient au moins une case vide et 0 sinon. Une case est considérée comme libre si elle contient le caractère espace ' '. Modifier ensuite la fonction main du programme pour tester le retour de la fonction case_vide avec différentes configurations de plateau.
Exercice 3.5.
Dans le fichier tp4-morpion.c, ajouter une fonction char aligne(char symbole, char plateau[][3]) qui retourne 1 si pour le symbole donné ('X' ou 'O') une ligne existe sur le plateau et 0 sinon. Une ligne peut être horizontale, verticale ou diagonale. Modifier la fonction main du programme pour créer un plateau avec les valeurs: {{'X', 'O', ' '}, {'O', 'X', ' '}, {'O', ' ', 'X'}} et tester ensuite la fonction aligne. Essayer ensuite plusieurs configurations de plateau.
Exercice 3.6.
Dans le fichier tp4-morpion.c, compléter la fonction main afin de faire se dérouler une partie de morpion. L’utilisation des fonctions implantées précédemment est obligatoire.
Rappel: Le déroulement de la partie est le suivant :
- Le plateau de jeu est initialisé avec des espaces ' '
- Le joueur 1 place un symbole 'X' sur une case vide
- Si 3 symboles du joueur 1 sont alignés, il gagne la partie
- Le joueur 2 place un symbole 'O' sur une case vide
- Si 3 symboles du joueur 2 sont alignés, il gagne la partie
- Si aucun des 2 joueurs n’a gagné et s’il reste au moins une case libre, on reprend on point 2