Correction du TD n°9

Exercice 1

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