UTBM theorie de la programmation tda et structures de donnees 2005 gi

Description

UTBM le 14 novembre 2005 Médian – LO42 Aucun document autorisé (la copie ou les idées du voisin pas plus). Le barème est indicatif. Le soin donné à la rédaction sera évalué. Toute réponse devra être claire et justifiée (toute ambiguïté sera mal interprétée). L’élégance de la solution sera jugée. ...

Informations

• Publié par: shura
• Nombre de lectures: 99
• Langue: Français

Extrait

UTBMle 14 novembre 2005 MÈdian –LO42 Aucun document autorisÈ(la copie ou les idÈes du voisin pas plus). Le barËme est indicatif. Le soin donnÈ ‡ la rÈdaction sera ÈvaluÈ. Toute rÈponse devra Ítre claire et justifiÈe (toute ambiguÔtÈ sera mal interprÈtÈe). L’ÈlÈgance de la solution sera jugÈe. Sauf indication contraire, dans le cas d’algorithmes les rÈponses doivent Ítre rÈdigÈes en pseudo code. 1) La rÈcursivitÈ, dominer et contourner, vous pourrez ! La question c est en bonus ! (‡ ne faire que si le (8p) traitement des 3 exercices vous laisse du temps) ProblËme de la somme d’un sousensemble: Soient un entier k et n entiers positifs a 1 , a 2 ,…, a n . Y atil un groupe de ces n entiers dont la somme vaut k ? a) On veut Ècrire une fonction rÈcursive permettant de rÈpondre ‡ la question. L’entÍte de notre fonction sera " fonction boolÈen sommePartie(int k, taille, pos ; entier tab[] )" o˘tailleest le nombre d’entiers positifs du tableautabetpos l’indice de l’entier ‡ traiter.  AprËsavoir dÈfini la (ou les) condition(s) d’arrÍt, prÈcisez votre dÈmarche pour rÈsoudre les autres cas. Enfin, Ècrivez la fonction rÈcursive. b) Ecrivez un programme utilisant la programmation dynamique selon l’idÈe cidessous Le tableau des solutions est un tableau de boolÈens. IdÈe : quel est l’effet d’un nombre supplÈmentaire A sur le tableau des solutions ?  Pourchaque somme X qu’on peut atteindre, X reste atteignable, et (X+A) devient atteignable ! Exemple : peuton faire la somme 17 avec {5, 8, 6, 2} ?Non Avec 00, 01, 02, 03, 04, 05,06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17{} 00, 01, 02, 03, 04,05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17{5} 00, 01, 02, 03, 04,05, 06, 07,08, 09, 10, 11, 12,13, 14, 15, 16, 17{5, 8} 00, 01, 02, 03, 04,05,06, 07,08, 09, 10,11, 12,13,14, 15, 16, 17{5, 8, 6} 00, 01,02, 03, 04,05,06,07,08, 09,10,11, 12,13,14,15,16{5, 8, 6, 2}, 17 c) Modifiez votre algorithme rÈcursif afin d’afficher le groupe des entiers dont la somme vaut k. On pourra introduire un tableau permettant de marquer les entiers inclus dans la somme. 2) Face ‡ l’adversitÈ, ensemble, la solution sera(8p) a) Etablissez la description syntaxique ou signature, puis la description axiomatique d’un TDA ensemble qui fournit les opÈrations qui travaillent sur des ensembles et des ÈlÈments de typeElÈmentconnu:  ensemblevide union  cardinal intersection  appartenance inclusion: le premier inclus dans le second  ajout diffÈrence: ÈlÈments qui appartiennent au premier et pas au second  suppression b) Ecrivez en Java l’interface correspondant au TDA. Si des choix sont ‡ faire, vous expliquerezceux que vous avez faits. 3) La cerise, dÈception Èvitera(4p) Soit le programme utilisant des variables entiËres : Tantque a<c Faire  b←2 * a + 1 + b ;  a←a + 1 ; ftq ; 2 Trouvez la plus petite prÈcondition de la boucle assurant au programme un Ètat mÈmoire final vÈrifiant b = a . En dÈduire les initialisations.

LO42  mÈdian A2005  page1/1