Exercices d'algorithmique

Résumé du document

Annale corrigée de programmation: Exercices d'algorithmique (4 pages)





Deux algorithmes cherchant un nombre dans un tableau (si l'element est present, on renvoie son indice, sinon on renvoie 1) sont presentes en parallele. Le premier cherche dans un tableau

non trie en parcourant tous les elements. On s'arr^ete si l'element a ete trouve ou si tous les elements ont ete parcourus. Le deuxieme cherche de facon dichotomique : g et d represente les

bornes gauche et droite du sous-tableau ou x est cherche. A chaque etape, on regarde le milieu de cet intervalle, en le comparant avec x on sait alors dans quelle partie du tableau chercher.





I) Suite de Fibonacci

II) Nombres binaires

III) Maximum et Tri

Extraits

[...] for i = 1 : pp = for j = + : n if T < T pp = j end end % pp est l'indice du plus petit % ´l´ment du tableau . e e T = echange(T, % le tableau . % est maintenant tri´. e end end 3 function T = echange(T, temp = T T = T T = temp; Deux algorithmes cherchant un nombre dans un tableau (si l'´l´ment est pr´sent, on renvoie ee e son indice, sinon on renvoie sont pr´sent´s en parall`le. [...]

[...] Le deuxi`me cherche de fa¸on dichotomique : g et d repr´sente les ee ee e c e bornes gauche et droite du sous-tableau x est cherch´. A chaque ´tape, on regarde le milieu u e e de cet intervalle, en le comparant avec x on sait alors dans quelle partie du tableau chercher. function p = present(T, function b = present tri(T, g = d = length(T i = f loor((g + while T = x g d p = else p = end i = while T = x i n p = else p = end Les tests ` la fin d´terminent de quelle fa¸on est-on sorti de la boucle while : dans un cas x a e c n'est pas pr´sent (on renvoie dans l'autre on connait son indice. [...]

[...] ) 2 + a3 ) 2 + a2 ) 2 + a1 Cela inspire un autre algorithme n'utilisant pas la fonction puissance : function d = bin to dec n = length(B); d = for i = n : 1 d = d 2 + end En d´veloppant la pr´c´dente on obtient e e e e e n = an + an + . + a3 22 + a2 21 + a1 20 et donc la formule voulue pour la d´composition en binaire de n. La suite de divisions euclie diennes par 2 nous donne donc une m´thode pour l'algorithme traduisant un nombre dans sa e repr´sentation binaire. [...]

[...] function T = div euclide(a, q = r = % commentaire ici while r b q = q + r = r % et ici aussi end T = T = 1 Cet algorithme renvoie bien le quotient et le reste de la division euclidienne de a par b. En effet, on peut prouver (par r´currence encore) qu'au niveau des commentaires, l'´quation e e a = b q + r est v´rifi´e. Or l'algorithme ne sort de la boucle while que si r est plus petit que e e la deuxi`me condition pour la division euclidienne est alors v´rifi´e. e e e Il existe plusieurs fa¸ons de traduire un nombre binaire d´crit par un tableau de 0 et de 1 c e en un nombre d´cimal. [...]

[...] e function m = max(T ) function j = max indice(T ) n = length(T n = length(T m = T j = for i = 2 : n for i = 2 : n if m < T if T < T m = T j=i end end end end La fonction de tri utilise une fonction qui ´change deux valeurs d'un tableau. L'algorithme e consiste ` trouver le plus nombre, et a l'´changer avec le premier ´l´ment du tableau, puis de a ` e ee recommencer sur le reste du tableau. [...]