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

Publié par

Examen du Supérieur Université Paris (Diderot) 7. Sujet de Projet de Programmation 2008. Retrouvez le corrigé Projet de Programmation 2008 sur Bankexam.fr.
Publié le : mercredi 23 juin 2010
Lecture(s) : 47
Nombre de pages : 2
Voir plus Voir moins
51IF2IK3 – Examen
7novembre2008dure´e2haucundocumentautoris´e
Onsouhaiter´ealiserunprogrammepourr´esoudredesuqigamser´arcse. Uncarr´emagiquedetaillentedelliagenullirmpos´edeestcon×ndans laquelle on place les 2 22 npremiers nombres entiers non nuls (1,2,3, . . . , n1, nmmossem`aednei`a)requceesel desnombresdechaqueligneetdechaquecolonnedelagrillesoient´egales.Lagure1contient 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.1ELeprobl`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´traitementpourlalgorithmedebacktracking. 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`partirdunegrillepartiellementremplie.On ne demande pas une me´thodeJavamaisunalgorithme. Expliquercommentproce`delalgorithmesurlagrillesuivante: .9. . .7 . .6 5)el´mpIrlteenemtiroglacabedemhckinktraslafgsoudnuroemhtdomee´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´medohansrappurcomˆs(esemesicelesexpmelvssunecommedans pas dans la documentation fournie en annexe de la classeCarreM). 6)iqplExe?reotrvuereetilutspontˆeucxesitpeitasedno,lutilithode(s)els(m)e´oPruuqle choix. Choisirunedecesm´ethodesetexpliciterleschangements`afairedanslecodedesade´nition et de ses appels.
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.