|
|
Examen
final Deug MIAS 2 – Algo et prog. C 2000-2001 –
première session |
1. Vous disposez de trois heures,
2. seuls vos documents personnels sont autorisés,
3. le code C sera commenté,
4. le barème (sur 21 !) est donné à titre indicatif et est susceptible d'être modifié.
Le but est de programmer un jeu de cartes de type solitaire et dont le déroulement est entièrement déterminé par l’ordre initial des cartes dans le paquet. En clair, il n’y a aucune stratégie, il s’agit de suivre les règles du jeu jusqu’à arriver à une situation gagnante ou perdante.
Les 52 cartes d’un jeu seront représentées par de simples entiers avec la convention 1=As, 11=Valet, 12=Dame, 13=Roi. La couleur (Pique, Trèfle, …) n’a aucune importance dans ce jeu.
Le jeu se déroule comme suit : on pose les cartes du paquet une à une sur la table en une pile en disant « un » lorsque l’on pose la première carte, « deux » lorsque l’on pose la seconde, etc. Après avoir dit « treize » on dit « un » en posant la carte suivante. Si la carte posée est de valeur égale au nombre que l’on est en train de dire, elle est éliminée (ou moissonnée). Lorsque toutes les cartes du paquet ont été épuisées, on reprend la pile de la table et on recommence la moisson. Le jeu se termine lorsque toutes les cartes ont été moissonnées (Victoire) ou lorsque le paquet a été parcouru sans retirer aucune carte (Echec).
Remarque : vous supposerez disposer de la procédure une_fois ci-dessus.
On désire savoir si oui ou non un entier m est une puissance d'un autre entier n (m>n et m,n > 0). Par exemple m=2197 est une puissance de n=13 car 2197=133 ou m=16 est une puissance de n=2 car 16=24
On suppose dans toute cette partie que nous disposons d’une bibliothèque écrite en C contenant la définition de type et les procédures et fonctions dont les signatures suivent :
#define MAX 10
typedef struct matrix{
int
coldim;
int
rowdim;
double elts[MAX][MAX];} matrix;
void Identite(matrix *M, int n) /* Construction d'une matrice identite d'ordre n */
double trace(matrix m1); /* Trace d'une matrice */
void scalarmul(double x, matrix m1, matrix *m2); /* Multiplication par un scalaire */
void add(matrix m1, matrix m2, matrix *m3); /* Addition de deux matrices */
void mult(matrix m1, matrix m2, matrix* m3); /* Multiplication de deux matrices */
Soit une matrice carré A d’ordre n. On souhaite calculer les coefficients de son polynôme caractéristique P(l) = det(A-lId) = (-1)n [ln + q1ln-1 + ... + qn-1l + qn]
La méthode de Souriau consiste à construire les 3 suites ci-dessous (Id est la matrice Identité d’ordre n). On peut alors prouver que : tk = - qk pour k = 1 .. n.
|
C1 = A |
t1 = trace(C1) |
B1 = C1-t1Id |
|
C2 = B1A |
t2 = ½ trace(C2) |
B2 = C2-t2Id |
|
C3 = B2A |
t3 = 1/3 trace(C3) |
B3 = C3-t3Id |
|
... |
... |
... |
|
Cn
= Bn-1A |
tn = 1/n trace(Cn) |
Bn = Cn-tnId |