CC Algo 2015-2016
Transféré par
sidikiensiasCC Algo 2015-2016
Transféré par
sidikiensiasUniversité Abou Bekr Belkaid – Tlemcen Année Universitaire 2015 - 2016
L2 Licence Informatique
Faculté des Sciences UEI-72
M.BENAZZOUZ
Département d’Informatique Durée : 1 h
Partiel d’Algorithmique
Exercice 1 : Recherche dichotomique (10 pts)
Dichotomie veut dire en grec "couper en deux".
La recherche dichotomique impose que les éléments de l'espace de recherche soient ordonnés.
Cette méthode consiste à diviser l'espace en deux parties égales ; un test (comparer la valeur
recherchée avec la valeur du milieu du tableau) permet de déterminer la partie dans laquelle
sera effectuée la recherche (éliminer l’autre moitié du tableau).
On considère un tableau T contenant n entiers déjà triés par ordre croissant, écrire une fonction
permettant de vérifier l’existence d’une valeur v dans le tableau T.
a. Version dichotomique itérative.
b. Version dichotomique récursive.
Exercice 2 : Supprimer les doubles ( 5 pts)
On considère un tableau T de taille L composé d’un ensemble d’entiers.
On veut écrire un programme qui permet de supprimer tous les éléments redondants. La taille
du tableau T devient M.
⎯ Le programme ne doit pas utiliser de tableau intermédiaire.
⎯ On suppose que le tableau n'est pas trié.
⎯ L'ordre des éléments reste celui de la séquence de départ.
Exemple : si T = [15, 4, 19, 4, 8, 11, 11, 3, 4, 19] et L = 10 alors
T = [15, 4, 19, 8, 11, 3] et M = 6.
