Projet de Programmation 2008 Informatique Université Paris (Diderot) 7

Description

Examen du Supérieur Université Paris (Diderot) 7. Sujet de Projet de Programmation 2008. Retrouvez le corrigé Projet de Programmation 2008 sur Bankexam.fr.

Informations

• Publié par: bankexam
• Publié le: 23 juin 2010
• Nombre de lectures: 49
• Langue: Français

Extrait

51IF2IK3 – Examen

7novembre2008–dure´e2h–aucundocumentautoris´e

Onsouhaiter´ealiserunprogrammepourr´esoudredesuqigamser´arcse. Uncarr´emagiquedetaillentedelliagenullirmpos´ed’eestcon×ndans laquelle on place les 2 22 npremiers nombres entiers non nuls (1,2,3, . . . , n−1, nmmossem`aednei`a)requceesel desnombresdechaqueligneetdechaquecolonnedelagrillesoient´egales.Lafigure1contient deuxexemplesdecarre´magique,undetaille3(chaqueligneetchaquecolonneaunesomme ´egalea`15)etundetaille4(chaqueligneetchaquecolonneaunesomme´egalea`34). 16 3 2 13 4 9 2 5 1011 8 3 5 7 9 67 12 8 1 6 4 1514 1 Fig.delempxesm´errcadseuqiga3elliateet4.1E– Leprobl`emedcura´rmegaqieuconsiste,´anetontdee´ngenullirrapetnelemitle remplievertrou,`atouseuqigamse´rracsetlennnientcouisqlisinitlaseavelruille.esdelagr Onvare´soudreceproble`meavecunalgorithmedebacktrackingite´ratif. On utilisera les classesCarreM,CaseetChoixn´eesenatnenoitnossnodtntdosdleumoc annexe. 1)oMtnerqreuopruotellaietdeuqigame´rractun, la somme de chaque ligne et de chaque 2 n(n+ 1) colonneesttoujourse´galea`. 2 (Onpourrautilisersanslad´emontrerlaformuledonnantlasommedeskpremiers nombres entiers.) Ecrire le constructeur de la classeCarreMapardnnepieruq,certienunreetm`enutiurtsno grillevidedetailleceparam`etreetinitialiselechamppoidsrpe´nOerreaestnnces´onueeqe.nc une case vide par la valeur 0. 2)A partir de la grille ci-dessous, expliquer comment on peut obtenir directement la valeur delacaseenhauta`droite,puislesvaleursdesdeuxautrescasesvides.

1

.9. 8 1 6 .5 7 Ende´duireunalgorithmedepre´traitementpourl’algorithmedebacktracking. 3)L’algorithme de backtracking devra tester si une valeurvest possible ou non pour une casec: Ecrireunem´ethodeestCompatible(Case c,int v)de la classeCarreMqui renvoietruesi et seulement si le choix devpourcvaceelvslauesrn´’destpasincoh´erentsn`aejisexnttadaes grilleet avec le poids. 4)robl`emeuordlepearti´rseneutocmmrotianglrireD´ecare´ti(gruop)fitacebedhminckrakt descarr´esmagiquesa`partird’unegrillepartiellementremplie.On ne demande pas une me´thodeJavamaisunalgorithme. Expliquercommentproce`del’algorithmesurlagrillesuivante: .9. . .7 . .6 5)el´mpIrlteenemtirogla’cabedemhckinktraslafgsou’dnuroemhtdomee´resoudrede la classeCarreM. On utilisera une pile Java (java.util.Stackatnemucodenutnodsteelliertpaontine´eeodnn annexe) pour stocker des objets de la classeChoix`sedohteaouajursˆm´esrdtenOop.ibneruar la classeCarreMnetiasste´medoha’nsrappurcomˆs(esemesicelesexpmelvssunecommedans pas dans la documentation fournie en annexe de la classeCarreM). 6)iqplExe?reotrvuereetilutspontˆeucxesitpeitasedno,l’utilithode(s)els(m)e´oPruuqle choix. Choisirunedecesm´ethodesetexpliciterleschangements`afairedanslecodedesade´finition et de ses appels.

2