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

Informations

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

Extrait

UTBM le 18 novembre 2002 Médian – LO42 Les documents de cours et TD sont autorisés (la copie ou les idées du voisin non). 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é, effacer, vous pourrez ! (9p) a) Voici un schéma de récursivité : Procédure P(x) Début Tantque Cx faire Ex ; P(fx) ; Rx ; Ftq ; Sx ; Fin ; Donnez un schéma itératif équivalent. b) Voici la définition d’une fonction de MacCarthy. M(n) = n-10 si n > 100 M( M(n+11)) sinon b.1 Ecrivez une fonction récursive implantant cette définition. b.2 Modifiez ce code pour éliminer la récursivité. 2) Les deux candidats, évaluer, il est important ! (4p) Voici un extrait de programme : Fonction fact(n : entier) Var f, i : entier ; Début f ‹ 1; i ‹ n; Tantque (i>0) Faire i--; f ‹ f *(n-i); Ftq fact f; Fin ; Pour cet extrait de programme nous proposons deux expressions pour définir l’invariant de boucle. n! = f * (i!) f = (n-i)! Déterminer si les expressions sont des invariants de la boucle. Vous devez justifier votre réponse. 3) Fusionner les deux, je souhaite ! (7p) Ecrivez une procédure recevant deux paramètres de type Liste. Les deux listes étant triées en ordre croissant vous devez fusionner les deux listes pour retourner une liste triée en ordre croissant par l’intermédiaire du premier paramètre. Remarques : Vous devez optimiser le temps d’exécution et minimiser le code en respectant la première contrainte. Le type Liste correspond à une liste dynamique d’entiers. LO42 - médian A2002 - page1/1