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

Description

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

Informations

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

Extrait

51IF2IK3 – Examen Session 2

23juin2009–dur ´ ee3h–bar ` 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 surlefildeuxs ´ 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 ˆ xe’lnema Programmerl’algorithmedebacktrackdupointpr ´ ece ´ dentend ´ efinissantune 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 classe Stack. affichequi affiche le contenu de la pile (donc qui permet d’afficher une solu tion). collierCorrect qui appelle la me´thode statiquetestCollierde la classeTestCollier dont le code binaire est disponible a` l’adresse /home/malben45/TestCollier.class . La me´thode testCollier¸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 ´ ementerd’autresme ´ thodesauxiliaires.

1

Question 4. (6p)L’objectif de ce point est d’obtenir un algorithme pour collierCorrect, sans utilisertestCollier. 1. L’allongement du collier d’un seul coˆte´ dans l’algorithme de backtracking conservelaproprie ´ t ´ ed’absencedese ´ 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(voirfigure):si ` auncolliercorrectcon ajoute une perlep, le colliercpest correct ssi les s ´ equencesadjacentesdontunecontientp sont diffe´rentes. (a)(1p)Montrerquecettepropri ´ et ´ eestvraiepourl’allongementavecla 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 indicesd 1 etd 2 (de fin de chaque sousse´quence), et une longueur de sousse´quence `; cet algorithme renvoie vrai ssi les se´quences t[d 1 −`+1]..t[d 1 ]ett[d 2 −`+1]..t[d 2 ]sont identiques. ´ (c) (2p) Ecrire l’algorithme pour le testcollierCorrectirquo¸ceti comme argument un vecteur d’entiers. Question 5. (4p)edtiarepttCete ˆ tiodnemaxe’lesouss ´ eeealirer ´ sp!ecEil 1. (1p)Pour programmer l’algorithme decollierCorrect , de´finir une classe Collier qui he´rite de la classe CollierBasee ´ nfirtde ´ mtetialhodee collierCorrect. 2. (3p) Programmer l’algorithme decollierCorrect sans faire appel a` testCollierasedixu ´ mseohted’ertrau ´ eplntmeopvuzemiio,novsu.Sibes liaires.Testercettem ´ ethodeenappellantlame ´ thode(h ´ erit ´ ee)traiter.

2