Correction TD n°9

Correction du TD n°9

Bataille navale

Structure de données: Deux tableaux permettront de stocker les informations nécessaires à la gestion d'un joueur:

un tableau de booléens pour mémoriser les cellules où un bateau du joueur est placé (vrai si un morceau de bateau occupe la cellule, faux sinon),
un tableau d'entiers pour mémoriser les cellules qui ont été testées par le joueur (1 si la cellule a été testée et un bateau y est présent, 0 si la cellule a été testée et aucun bateau n'y est présent, -1 si la cellule n'a pas été testée).

001  fonction testJeuFiniBatailleNavale(tBateaux,tTests) : booléen
002    Données tBateaux : Tableau [N][N] de booléen
003            tTests : Tableau [N][N] de entier
004    Locales i,j : entier      { Indices de parcours des tableaux }
005            res : booléen     { Resultat fonction }
006    res := vrai
007    i := 0
008    tant que (res) et (i < N) faire
009      j := 0
010      tant que (res) et (j < N) faire
011        si (tBateaux[i][j]) et (tTests[i][j] = -1) alors
012          res := faux
013        j := j+1
014      fait
015      i := i+1
016    fait
017    Resultat : res
018  fin fonction

Bataille navale

Exercice 2

Josephus Flavius

Structure de données: Un tableau de booléens de taille identique au nombre de soldat (à vrai le soldat est vivant, à faux le soldat est mort). Des "trous" (booléens à faux) apparaitront et seront de plus en plus nombreux dans le tableau à mesure de l'exécution de l'algorithme.

Autre structure de données possible: Une liste chainée de booléens permettra de gérér plus facilement la suppression des soldats qu'ils représentent pour "récupérer" la place et faciliter les parcours à la recherche du prochain soldat à éliminer.

001  fonction josephusFlavius(n,k) : entier
002    Données n : entier
003            k : entier
004    Locales i : entier                  { Indice de boucle pour }
005            pos : entier                { Indice de parcours }
006            cpt : entier                { Compteur de soldats non elimines }
007            t : Tableau [n] de booléen  { Tableau de gestion du parcours }
008                                        { et des eliminations }
009    { Initialisation du tableau t }
010    { Le soldat 0 est elimine }
011    t[0] := vrai
012    { Les autres soldats ne le sont pas }
013    pour i de 1 à n-1 faire
014      t[0] := faux
015    fait
016    { Le parcours a la recherche du prochain }
017    { soldat a eliminer commence a l'indice 0 }
018    pos := 0
019    { Il reste n-1 soldats a eliminer }
020    pour i de 1 à n-1 faire
021    { Initialisation du compteur de soldats }
022    { non elimines a parcourir }
023      cpt := 0
024    { Parcours jusqu'a avoir trouve le kieme soldat non elimine }
025      faire
026    { On avance de 1 soldat en revenant a l'indice 0 }
027    { quand on avance depuis l'indice n-1 }
028        pos := (pos+1) modulo n
029    { Si le soldat en position pos n'est pas elimine }
030        si t[pos] = faux alors
031    { Le compteur de soldats non elimines est incremente de 1 }
032          cpt := cpt+1
033        fsi
034      tant que cpt != k
035    { pos est sur le kieme soldat non elimine }
036    { -> on l'elimine }
037      t[pos] := vrai
038    fait
039    { Resultat fonction : Dernier soldat elimine }
040    Resultat : pos
041  fin fonction

Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr