Devoir surveillé
durée 2h
jeudi 20 décembre 2012

A. Exercices

I. Listes

1. Soit w une liste d’entiers. Ecrire la fonction Periodique[w_,n_] qui engendre la liste de longueur n, périodique de période w

Periodique[w_,n_]:=Flatten[Join[Table[w,{Quotient[n,Length[w]]}],Take[w,Mod[n,Length[w]]]]]

Periodique[{1,1,2},7]

2. Ecrire une fonction qui retourne  la plus petite période d’une liste.

Periode[w_]:=Block[{IsPeriodQ,prefixes=Table[Take[w,i],{i,1,Length[w]-1}]},
IsPeriodQ[u_]:=w==Periodique[u,Length[w]];
First[Sort[Select[prefixes,IsPeriodQ],Length[#1]<Length[#2]&]]]

Periode[Periodique[{1,2,1,2,2},12]]

3. Ecrire une fonction qui intègre les polynomes en x.

Integre[a_/;FreeQ[a,x]]:=a x
Integre[a_+b_]:=Integre[a]+Integre[b]
Integre[x]:=x^2/2
Integre[x^n_]:=1/(n+1)x^(n+1)
Integre[Times[a_/;FreeQ[a,x], x]]:=a x^2/2
Integre[Times[a_/;FreeQ[a,x], x^n_]]:=a x^(n+1)/(n+1)

Integre[1+2/3 x+Pi x^2- 4 x^3]

B. Problème : Jeu de bataille navale

Sur une grille 10×10, on dispose 5 bateaux de types différents, 1 porte-avions (5 cases), 1 croiseur (4 cases), 1 contre-torpilleurs (3 cases), 1 torpilleurs (2 cases), 1 sous-marin (1 case). Pour simplifier,  les bateaux seront placés horizontalement et sur des lignes différentes. une table de jeu sera donc l’ensemble des 5 points de la grille qui sont aux extrémités gauche de chaque bateau, avec la convention que le (i^(ième )) point correspond au bateau de longueur i.  
Exemple.  La table de jeu   sera codée par la liste {{5,4},{4,5},{6,8},{6,9},{3,2}}

1) Génération d’une table de jeu : La fonction Jeu[] retourne les positions de chacun des 5 type de bateaux.

Jeu[]:=Block[{
ordonnées=RandomSample[Range[10],5],
abscisses=Table[1+RandomInteger[10-i],{i,1,5}]
},
Return[Table[{abscisses[[i]],ordonnées[[i]]},{i,1,5}]]]

jeu=Jeu[]

2) Etant donné un jeu, ecrire une fonction qui retourne la liste des cases occupées par les bateaux

CasesOccupées[joueur_]:=Block[{bateau,cases},
bateau[i_]:=NestList[#+{1,0}&,joueur[[i]],i-1];
cases=Flatten[Table[bateau[i],{i,1,5}],1];
Return[cases]]

Exemple.  La liste des cases occupées par la  table de jeu   est {{5,4},{4,5},{5,5},{6,8},{7,8},{8,8},{6,9},{7,9},{8,9},{9,9},{3,2},{4,2},{5,2},{6,2},{7,2}}

CasesOccupées[jeu]

2) Visualisation d’une table de jeu.

Visualiser[jeu_]:=Block[{h=.2},
Join[
Table[Line[{{i,1},{i,11}}],{i,1,11}],
Table[Line[{{1,i},{11,i}}],{i,1,11}],
Table[
Block[{x=jeu[[i]][[1]],y=jeu[[i]][[2]]},
{Hue[i/5-.1],Rectangle[{x+h,y+h},{x+i-h,y+1-h},RoundingRadius->h]}],
{i,1,5}]
]]

Graphics[Visualiser[jeu]]

3) Partie de bataille navale. On crée deux tables de jeu et chaque joueur (simulé par l’ordinateur) propose à tour de rôle une position dans la table de jeu de l’adversaire. Pour simplifier, tout bateau touché sera considéré comme coulé.

L’état de la connaissance qu’a un joueur sur le jeu de son adversaire est représenté par la liste Connaissance[joueur]={Inconnus,Coulés} où Inconnus est la liste des cases de son adversaire  encore non explorées et Coulés  est la liste des indices des lignes où un bateau de l’adversaire a été coulé. La connaissance d’un joueur en début de partie est donc engendrée par la fonction

Init[jeu_]:=Connaissance[jeu]={Tuples[Range[10],2],{}}

jeu
Init[jeu];
Connaissance[jeu]

a) En utilisant la variable connaissance[joueur], écrire la fonction Tirage[jeu_] qui génére une case aléatoire dans le territoire encore inconnue   de son adversaire.

Tirage[jeu_]:=RandomSample[Connaissance[jeu][[1]],1][[1]]

Tirage[jeu]

b) Ecrire le prédicat TouchéQ[jeu_,case_] qui répond True ou False selon qu’un bateau occupe ou non la case en paramètre.

TouchéQ[jeu_,case_]:=MemberQ[CasesOccupées[jeu],case]

TouchéQ[jeu,{10,8}]
TouchéQ[jeu,{7,3}]

c) Ecrire la fonction MettreAJour[jeu1_,jeu2_,case_] qui met à jour la variable Connaissance[jeu1] en supposant que la case en paramètre est occupée ou non par un bateau du jeu2.

MettreAJour[jeu1_,jeu2_,case_]:=Block[{y=case[[2]],inconnu=Connaissance[jeu1][[1]],touchés=Connaissance[jeu1][[2]]},
If[TouchéQ[jeu2,case],
touchés=Append[touchés,y];
inconnu=DeleteCases[inconnu,{_,y}];
Connaissance[jeu1]={inconnu,touchés},
Connaissance[jeu1]={DeleteCases[inconnu,case],touchés}]]

d) Ecrire une fonction GagnéQ[jeu] qui teste si un joueur a reconnu les 5 bateaux de son adversaire

GagnéQ[jeu_]:=Length[Connaissance[jeu][[2]]]==5

e)Ecrire la fonction Partie[jeu1_,jeu2_] qui simule une partie.

Partie[jeu1_,jeu2_]:=Block[{case},
Init[jeu1];
Init[jeu2];
While[1>0,
case=Tirage[jeu1];
MettreAJour[jeu1,jeu2,case];
If[GagnéQ[jeu1],Print["Le joueur 1 a gagné"];Break[]];

case=Tirage[jeu2];
MettreAJour[jeu1,jeu2,case];
If[GagnéQ[jeu2],Print["Le joueur 2 a gagné"];Break[]];]]

Partie[Jeu[],Jeu[]]

f) Modifier votre code pour permettre de réaliser une animation de la partie. On enregistrera chaque image de la partie dans une liste et la fonction jeu retournera la liste de ces images que l’on fera défiler à l’aide de la fonction ListAnimate.

Partie[jeu1_,jeu2_]:=Block[
{
case,
J1=Visualiser[jeu1],
J2=Visualiser[jeu2],
jeu
},

jeu={GraphicsGrid[{{Graphics[J1],Graphics[J2]}}]};
Init[jeu1];
Init[jeu2];


While[Not[GagnéQ[jeu1]||GagnéQ[jeu2]],

case=Tirage[jeu1];
If[TouchéQ[jeu2,case],
J2=Append[J2,{Red,Rectangle[case]}],
J2=Append[J2,{Gray,Opacity[0.3],Rectangle[case]}]];
MettreAJour[jeu1,jeu2,case];

case=Tirage[jeu2];
If[TouchéQ[jeu1,case],
J1=Append[J1,{Red,Rectangle[case]}],
J1=Append[J1,{Gray,Opacity[0.3],Rectangle[case]}]];
MettreAJour[jeu2,jeu1,case];

jeu=Append[jeu,GraphicsGrid[{{Graphics[J1],Graphics[J2]}}]]];

If[GagnéQ[jeu1],Print["Le joueur 1 a gagné"],Print["Le joueur 2 a gagné"]];
Return[jeu]]

partie=Partie[Jeu[],Jeu[]];

ListAnimate[partie,AnimationRepetitions->1,AnimationRate->4,AnimationRunning->False]

4)** Comment faire si l’on  peut placer les bateaux horizontalement ou verticalement. On peut aussi demander que les bateaux 3 et 4 nécessitent deux tir pour être coulés !