Théorie de la programmation - TDA et structures de données 2002 Génie Informatique Université de Technologie de Belfort Montbéliard

Crenaud

Description

Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Théorie de la programmation - TDA et structures de données 2002. Retrouvez le corrigé Théorie de la programmation - TDA et structures de données 2002 sur Bankexam.fr.

Sujets

• 2002

Informations

• Publié par: bankexam
• Publié le: 27 janvier 2008
• Nombre de lectures: 28
• Langue: Français

Extrait

UTBM le 18 novembre 2002

LO42 - médian A2002 - page1/1
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.