Université Ibn Zohr
Faculté des Sciences d’Agadir
Département d’Informatique
Année : 2014 / 2015
Examen d’Algorithmique 2
Filière : SMI-3
Durée : 1 h 30 min - Documents non autorisés
Important :
• Lire tout l’énoncé de l’examen avant de commencer à répondre.
• L’ordre de difficulté des exercices n’est pas nécessairement croissant.
• Le prêt de tout matériel entre étudiants est formellement interdit.
Exercice 1(chevauchement de deux intervalles) :
Ecrire un algorithme qui :
• Lit quatre entier a,b,c et d
• Vérifie si les intervalles [a,b] et [c,d] se chevauchent ou pas
• Affiche le résultat
Exemples : les intervalles [4,6] et [5,12] se chevauchent tandis que les intervalles [-4,-1] et [2,10] ne se
chevauchent pas.
Exercice 2 (nombre parfait) :
Un nombre parfait est un entier positif supérieur à 1, égal à la somme de ses diviseurs ;
On compte 1 comme diviseur, mais on ne compte pas le nombre lui-même comme diviseur.
Exemple : 6 est un nombre parfait puisque : 6 = 3 + 2 + 1.
Ecrire une fonction nbr_parfait qui prend comme paramètre un nombre entier n et retourne 1 si n
est un entier parfait et 0 sinon.
Exercice 3 :
1. Parmi les nombres suivant le(s)quel(s) est (sont) parfait(s) ? justifier votre réponse en
écrivant chaque nombre parfait sous forme de sommes.(voir définition exercice 2)
28 42 108 305 496 501
2. Sachant qu’au départ x=7 et y=3, quelles sont les valeurs de x et y après cette séquence :
x y
y x
x y-x
3. Quel est le résultat de l’initialisation du Tableau 2D suivante :
T [4][4] { { 1, 2, 3,0 }, { 5, 6,7 }, { 8, 9 } }
1 2 3 0 1 2 3 0 1 5 8 0 1 2 3 0
5 6 7 8 5 6 7 0 2 6 9 0 5 6 7 8
9 0 0 0 8 9 0 0 3 7 0 0 9 10 11 12
0 0 0 0 0 0 0 0 0 0 0 0 13 14 15 16
Examen d’Algorithmique 2 – Filière SMI 3 Page 1 / 2
Université Ibn Zohr
Faculté des Sciences d’Agadir
Département d’Informatique
Année : 2014 / 2015
Exercice 4 :
Soit A un tableau d’entier de taille maximale N.
1. Ecrire un programme qui lit n la taille effective de A (n <= N) puis remplit le tableau
élément par élément.
2. Supposons que le tableau A est trié dans un ordre croissant. Ecrire une fonction inser_trie
qui a comme paramètres le tableau A et un entier x. Elle insère l’entier x dans le tableau A
de sorte que A reste trié.
3. Quelle est la complexité de cette opération (notation en grand O) ? Justifier votre réponse.
4. Expliquer pourquoi on fait passer le tableau A par valeur dans la fonction inser_trie malgré
qu’on modifie son contenu (insertion d’un nouvel élément).
Exercice 5 (Multiplication par SHIFTs de 2 naturels) :
Voici un algorithme qui réalise l'exploit de multiplier 2 nombres entiers N et M en n'utilisant que
des multiplications/divisions par 2 selon la conception suivante :
A chaque étape, N est divisé par 2 (division entière) et M est multiplié par 2.
Si N est impair, la valeur de M est ajoutée au futur résultat. Si N est
strictement positif, on s’arrête à N = 1.
Exemple: 321 * 457
N M
321 457 N est impair donc futur résultat=457
160 914 N est pair donc on n'ajoute pas 914
80 1828 N est pair donc on n'ajoute pas 1828
40 3656 N est pair donc on n'ajoute pas 3656
20 7312 N est pair donc on n'ajoute pas 7312
10 14624 N est pair donc on n'ajoute pas 14624
5 29248 N est impair donc futur résultat=457+29248=29705
2 58496 N est pair donc on n'ajoute pas 58496
1 116992 N est impair donc résultat=29705+116992=146697
1. Ecrire une fonction itérative prod_shift_iter qui prend en paramètres deux entiers, respectivement,
N et M et retourne leur produit (de type Entier Double)
2. Quelle est la complexité de cette solution (notation en grand O) ? Justifier votre réponse.
3. Ecrire une fonction récursive prod_shift_rec qui fournit le même résultat que prod_shift_iter.
4. Ecrire un programme qui lit deux entiers positifs N et M puis, pour calculer leur produit, fait appel à
la fonction itérative prod_shift_iter de sorte à ce que le nombre d’itérations soit minimal.
Exercice 6 :
Ecrire une fonction récursive long_rec qui prend en paramètre une chaine de caractère ch et qui retourne sa
longueur.
Examen d’Algorithmique 2 – Filière SMI 3 Page 2 / 2
