//img.uscri.be/pth/465132457becd5d10550d829de447c759400cf1e
Cette publication est accessible gratuitement
Lire

Projet de programmation 2009 Informatique Université Paris (Diderot) 7

2 pages
Examen du Supérieur Université Paris (Diderot) 7. Sujet de Projet de programmation 2009. Retrouvez le corrigé Projet de programmation 2009 sur Bankexam.fr.
Voir plus Voir moins
51IF2IK3 – Examen Session 2
23juin2009dur´ee3hbar`emeindicatif
Soit un fil sur lequel on de´sire enfiler des perles de trois couleurs qu’on de´note pour simplifier avec les nombres 0, 1 et 2. Pour constituer un collier, on pose une seule contrainte : il ne doit pas y avoir surleldeuxs´equencesadjacentesidentiques.Parexemple:lecollier0estcorrect, mais 00 est incorrect; 01 et 010 sont des colliers corrects, mais 0100 et 0101 sont incorrectscarpourlepremierlase´quence0estr´ep´ete´etandisquepourledeuxi`eme lase´quence01estre´pe´t´ee.Laseulepossibilit´epourrallongerlecollier010est d’ajouter la perle 2. Question 1. (1p)Cte´eplomillocelrop2010reurobteniruncollireocrrceatevc 6 perles. Combien de colliers corrects de 6 perles on peut obtenir en partant de 0102 ? Question 2. (2p)De´rouler a` la main un algorithme de backtrack permettant, en rangeant les entiers des colliers dans une pile, d’obtenirTOUSles colliers de lon gueur 5. On suppose qu’il existe un testcollierCorrectqui renvoie vrai si et seulement si le nouveau collier range´ dans la pile est correct. Question 3. (7p)iedepartetteClcpies!es´esEou´eerisaltiodrteˆxelnema Programmerlalgorithmedebacktrackdupointpr´ece´dentend´enissantune classeCollierBasesuivodes´ethlesmatnay:snaet traitererrqiuacebelntme´eplimdnegneruopkcartkTOUSles colliers de lon gueurL. La pile contiendra les entiers constituant le collier en cours de construction. Pour imple´menter la pile, vous utiliserez la classeStack. affichequi affiche le contenu de la pile (donc qui permet d’afficher une solu tion). collierCorrectqui appelle la me´thodestatiquetestCollierde la classeTestCollierdont le code binaire est disponible a` l’adresse /home/malben45/TestCollier.class. La me´thodetestCollier¸oitrec comme argument une pile d’entiers (Stack<Integer>) et renvoie un bool´een. mainqui permet de donner la longueurLavant de lancer le backtrack. Sibesoin,vouspouvezimpl´ementerdautresme´thodesauxiliaires.
1
Question 4. (6p)L’objectif de ce point est d’obtenir un algorithme pour collierCorrect, sans utilisertestCollier. 1. L’allongementdu collier d’un seul coˆte´ dans l’algorithme de backtracking conservelaproprie´t´edabsencedese´quencesadjacentesidentiquespour le de´but du collier. C’est pourquoi, a` l’ajout d’une perle a` la fin du col lier,uniquementless´equencescontenantcettederni`ereperledoiventˆetre conside´r´ees.Cefaitestformalis´eparlapropri´et´esuivante(voirgure):si `auncolliercorrectcon ajoute une perlep, le colliercpest correct ssi les s´equencesadjacentesdontunecontientpsont diffe´rentes. (a)(1p)Montrerquecettepropri´et´eestvraiepourlallongementavecla perle 2 du collier 010. (b) (1p)Prouver formellement cette proprie´te´.
2. Lefait cidessus permet de construire un algorithme pourcollierCorrect quiconsid`ereit´erativementless´equencesadjacentesdelongueur1,2,etc. telles qu’une des se´quences se termine par la perle ajoute´e (voir figure). (a) (1p)Pour un collier de longueurL, combien de se´quences adjacentes dontunecontientladerni`ereperleajoute´edoiventˆetreconsid´ere´es? ´ (b) (1p)Ecrire un algorithmeidentiquesvnceetruer¸ciout)quiab(taule d’entierst, deux indicesd1etd2(de fin de chaque sousse´quence), et une longueur de sousse´quence`; cet algorithme renvoie vrai ssi les se´quencest[d1`+1]..t[d1]ett[d2`+1]..t[d2]sont identiques. ´ (c) (2p) Ecrire l’algorithme pour le testcollierCorrectirquo¸ceti comme argument un vecteur d’entiers. Question 5. (4p)edtiarepttCeteˆtiodnemaxelesouss´eeealirer´sp!ecEil 1. (1p)Pour programmer l’algorithme decollierCorrect, de´finir une classe Collierqui he´rite de la classeCollierBasee´nrtde´mtetialhodee collierCorrect. 2. (3p) Programmer l’algorithme decollierCorrectsans faire appel a` testCollierasedixu´mseohtedertrau´eplntmeopvuzemiio,novsu.Sibes liaires.Testercettem´ethodeenappellantlame´thode(h´erit´ee)traiter.
2