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
[...] 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. [...]
avec notre liseuse dédiée !
En cliquant sur OK, vous acceptez que Pimido.com utilise des cookies ou une technologie équivalente pour stocker et/ou accéder à des informations sur votre appareil. Ces informations personnelles peuvent être utilisées pour mesurer la performance publicitaire et du contenu ; en apprendre plus sur votre utilisation du site ; ou pour vous permettre d'interagir avec les réseaux sociaux. Vous pouvez paramétrer vos choix pour accepter les cookies ou non. Vous pourrez également modifier vos préférences à tout moment en cliquant sur le lien "Paramètres des cookies" en bas de page de ce site. Pour en savoir plus, consultez notre Politique de confidentialité