Problème#
La bataille navale est un jeu à deux joueurs où chacun place des bateaux sur une grille secrète et cherche à couler ceux de l’autre. À tour de rôle, chacun choisit une position sur la grille adverse. Si cette position correspond à un bateau adverse, ce bateau est touché. Si toutes les cases d’un bateau sont touchées, celui-ci est coulé. Le gagnant est le premier qui coule tous les bateaux adverses.
On se propose d’implanter une variante de la bataille navale, la bataille fluviale, prenant place non pas sur une mer en deux dimensions mais sur une rivière en une dimension. Un unique joueur attaque les bateaux placés secrètement par l’ordinateur, et cherche à les couler tous le plus vite possible. Une rivière est représentée par un tableau d’entiers de taille 15. Dans ce tableau, l’entier \(0\) symbolise une position vide, et un entier \(i\) non nul représente une case du bateau \(i\). Par simplicité, on considère trois bateaux de tailles \(2\), \(3\) et \(4\) nommés respectivement \(2\), \(3\) et \(4\). Par exemple, le tableau ci-dessous représente une rivière où le bateau \(4\) commence à la position \(1\), le bateau \(2\) à la position \(5\) et le bateau \(3\) à la position \(12\):
On souhaite définir une fonction tirDansHistorique vérifiant si une
position a déjà été attaquée par le joueur. Pour cela, on représente
l’historique des tirs du joueur par un tableau d’entiers contenant les
positions qu’il a attaquées précédemment. Observez les tests suivants,
déduisez-en la documentation de la fonction, puis complétez sa
définition.
CHECK( tirDansHistorique(0, {3, 0, 5, 2}) );
CHECK( tirDansHistorique(2, {3, 0, 5, 2}) );
CHECK( not tirDansHistorique(1, {3, 0, 5, 2}) );
CHECK( not tirDansHistorique(4, {3, 0, 5, 2}) );
/// BEGIN SOLUTION
/** Vérifie si une position a déjà été attaquée par le joueur
* @param position un entier
* @param historiqueTirs l'historique des positions attaquées par le joueur
* @return un booléen, vrai si et seulement si la position figure dans l'historique
**/
/// END SOLUTION
bool tirDansHistorique(int position, vector<int> historiqueTirs) {
/// BEGIN SOLUTION
for ( int i = 0; i < historiqueTirs.size(); i++ )
if ( historiqueTirs[i] == position )
return true;
return false;
/// END SOLUTION
}
Pour suivre d’avancement de la partie, on souhaite définir deux
fonctions, afficheRiviere qui affiche les bateaux attaqués par le
joueur, et victoire qui vérifie si la partie est gagnée par le
joueur.
Complétez la définition de la fonction afficheRivière ci-dessous :
/** Affiche la rivière et les bateaux attaqués par le joueur.
* Les positions non attaquées sont représentées par le symbole ~,
* les cases vides attaquées sont représentées par la lettre x,
* et les bateaux attaqués sont représentés par leur numéro.
* @param rivière une rivière
* @param historique l'historique des positions attaquées par le joueur
**/
void afficheRiviere(vector<int> riviere, vector<int> historiqueTirs) {
for ( int i = 0; i < riviere.size(); i++ )
/// BEGIN SOLUTION
if ( tirDansHistorique(i, historiqueTirs) )
if ( riviere[i] == 0 )
/// END SOLUTION
cout << "x";
else
cout << riviere[i];
else
cout << "~";
cout << endl;
}
Définissez la fonction victoire documentée ci-dessous :
/** Vérifie si le joueur a gagné la partie
* @param riviere une rivière
* @param historiqueTirs l'historique des positions attaquées par le joueur
* @return un booléen, vrai si et seulement si toutes les positions de
* bateaux ont été attaquées par le joueur
**/
/// BEGIN SOLUTION
bool victoire(vector<int> riviere, vector<int> historiqueTirs) {
for ( int i = 0; i < riviere.size(); i++ )
if ( riviere[i] != 0 and not tirDansHistorique(i, historiqueTirs) )
return false;
return true;
}
/// END SOLUTION
On s’intéresse au placement aléatoire de bateaux dans la rivière.
Complétez la définition de la fonction positionBateauValide ci-dessous :
/** Vérifie si il est possible d'ajouter dans la rivière un bateau
* d'une certaine longueur à une certaine position
* @param rivière une rivière
* @param debut un entier représentant une position de la rivière
* @param longueur un entier représentant la longueur du bateau
* @return un booléen indiquant si l'ajout est possible ou non
**/
bool positionBateauValide(vector<int> riviere, int debut, int longueur) {
if ( debut + longueur > riviere.size() )
/// BEGIN SOLUTION
return false;
/// END SOLUTION
for ( int i = debut; i < debut + longueur; i++ )
if ( riviere[i] != 0 )
/// BEGIN SOLUTION
return false;
return true;
/// END SOLUTION
}
On suppose que l’on a déjà défini une fonction aleaint(a, b)
qui renvoie un entier aléatoire compris entre a et b inclus.
Complétez la définition de la fonction ci-dessous :
/** Génère aléatoirement un placement de bateaux de taille 2, 3
* et 4 dans une rivière de taille 15
* @return un tableau d'entiers représentant la rivière
**/
vector<int> genereRiviere() {
vector<int> riviere;
riviere = vector<int>(15);
for ( int bateau = 2; bateau <= 4; bateau++ ) {
int position;
// Répète le tirage aléatoire d'une position entre 0 et 14
// jusqu'à ce qu'elle soit valide pour le bateau
/// BEGIN SOLUTION
do {
position = aleaint(0, 14);
} while ( not positionBateauValide(riviere, position, bateau) )
/// END SOLUTION
// Inscrit le bateau dans la rivière en cette position et suivantes
/// BEGIN SOLUTION
for ( int i = position; i < position + bateau; i++ )
riviere[j] = bateau;
/// END SOLUTION
}
return riviere;
}
On suppose déjà définies les deux fonctions suivantes :
/** Demande au joueur où il souhaite tirer dans la rivière
* @return un entier représentant une position valide de la rivière
**/
int entrerPositionTir();
/** Affiche le résultat du tir: dans l'eau, touché, coulé, ...
* @param tir un entier, la position du dernier tir
* @param riviere une rivière
* @param historiqueTirs l'historique des positions attaquées par le joueur
**/
void resultatTir(int tir, vector<int> riviere, vector<int> historiqueTirs);
Complétez le code suivant, qui réalise le programme principal du jeu :
// Construit une rivière et un historique de tirs et affiche la rivière
/// BEGIN SOLUTION
vector<int> riviere = genereRiviere();
vector<int> historiqueTirs = {};
afficheRiviere(riviere, historiqueTirs);
/// END SOLUTION
// À chaque tour de jeu jusqu'à la victoire, demande la position où tirer,
// affiche le résultat de ce tir, met à jour l'historique et affiche la rivière
/// BEGIN SOLUTION
while ( not victoire(riviere, historiqueTirs) ) {
int tir = entrerPositionTir();
resultatTir(tir, riviere, historiqueTirs);
historiqueTirs.push_back(tir);
afficheRiviere(riviere, historiqueTirs);
}
/// END SOLUTION
cout << "Bravo, vous avez gagné en " << historiqueTirs.size() << " coups!" << endl;