UNIVERSITE de la POLYNESIE FRANCAISE

Contrôle théorique N°1 Techni.Com – Algorithmique et C 02 Février 2001

Modalités

1.Le sujet est prévu pour une durée de 60 minutes,

2.vos documents personnels sont autorisés,

3.le barème est donné à titre indicatif et est susceptible d'être modifié,

4.les deux parties sont indépendantes (attention ce sujet est en recto/verso).

1 Le jeu de la moisson

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).

1.1 Ecrire en pseudo code l’algorithme permettant de construire un jeu de 52 cartes sans couleur (env. 2 pts)

1.2 Ecrire en pseudo code l’algorithme permettant de mélanger les cartes du paquet (env. 2 pts)

NB : Vous supposerez disposer d’un moyen de tirer un entier au hasard dans un intervalle donné.

1.3 Ecrire en pseudo code l’algorithme qui parcoure une fois tout le paquet de cartes avec moisson si possible (env. 3 pts)

1.4 Ecrire en pseudo code l’algorithme du jeu complet avec détection d’une fin gagnante ou perdante (env. 2 pt)

NB : Vous supposerez disposer de l’algorithme précédent.

1.5 Ecrire en C une procédure ou fonction une_fois qui parcoure le paquet une fois et moissonne lorsque c’est possible, c’est à dire qui code l’algorithme de la question 1.3 ci-dessus (env. 3 pts)

2 Palindromes

Un palindrome est une chaîne de caractères qui se lit de la même manière dans un sens et dans l’autre. Exemples :

• radar
• esoperesteicietserepose (« esope reste ici et se repose » sans les caractères blancs)
• engagelejeuquejelegagne (« engage le jeu que je le gagne » sans les caractères blancs)

2.1 Donner un algorithme itératif de détection d’un palindrome qui rendra 1 si c’est un palindrome et 0 sinon (2 pts)

2.2 Donner un algorithme récursif de détection d’un palindrome (3 pts)

2.3 Programmer l’algorithme récursif en C ( 3 pts)

NB : Les chaînes de caractères ne sont rien d’autre que des tableaux de char. Une variable de type chaîne de 50 caractères pourrait donc se déclarer : char chaine1[50], l’accès au premier caractère de chaine1 se fera alors de la manière standard en C : chaine1[0].