[PDF] Correction TD 8 : Algorithmes de tri

Licence 1 MASS semestre 2, 2007/2008 Exercice 1 : Tester On consid`ere que le tri devrait être selon l'ordre croissant a- Algorithme Test(T : tableau d'entiers;

Correction du T D 2 Les tableaux 1 Exercice 1 Ecrire les algorithmes permettant : 1 Le calcul du nombre d'occurences d'un élément donné dans un tableau

[PDF] Tableaux - CORRIGE - grug

Algorithmique et programmation procédurale - TD No 3 Tableaux - CORRIGE Exercice 1 Ecrire une procédure qui permet de retourner le plus grand et le plus

[PDF] Exercices avec Solutions

Exercices Corrigés d'Algorithmique – 1ére Année MI 23 EXERCICE 1 Soit un vecteur T (tableau à une dimension) contenant N nombres entiers (N≤100)

[PDF] Correction TD 8 : Algorithmes de tri - LISIC

Licence 1 MASS semestre 2, 2007/2008 Exercice 1 : Tester On consid`ere que le tri devrait être selon l'ordre croissant a- Algorithme Test(T : tableau d'entiers;

[PDF] Algorithmique - Correction du TD3

18 déc 2012 · Exercice 14 Ecrire un algorithme permettant de saisir 100 valeurs et qui les range au fur et à mesure dans un tableau Algorithme 14: Tri à la

[PDF] Algorithmes - Cours, examens et exercices gratuits et corrigés

Ecrire un algorithme qui déclare un tableau de 9 notes, dont on fait ensuite saisir les valeurs par l'utilisateur Exercice 6 4 Que produit l'algorithme suivant ?

[PDF] exercices corrigés algorithmepdf

Exercice 5 2 Ecrire un algorithme qui demande un nombre compris entre 10 et 20, jusqu'à ce que la réponse convienne En cas de réponse supérieure à 20,

[PDF] Corrigé des exercices sur les tableaux - Cnam

Corrigé des exercices sur les tableaux Exercice 5 1 1 tableau d'entiers Dans cet exercice, on va travailler avec un tableau d'entiers initialisé : int[] tab = {12, 15,

[PDF] SUJET + CORRIGE

retourner nb; Exercice 2 : Algorithmes de rang (14 points) Le probl`eme de la sélection consiste `a trouver dans un tableau de nombres l'élément dit de rang i

[PDF] Algorithmes et structures de données : TD 2 Corrigé - LaBRI

Algorithmes et structures de données : TD 2 Corrigé Tableaux Exercice 2 1 Ce tableaux occupe 4*1+4*4=20 octets car il y a 4 élements dans le tableau et

Correction TD 8 : Algorithmes de tri

Licence 1 MASS semestre 2, 2007/2008

Exercice 1 : Tester

On consid`ere que le tri devrait ˆetre selon l"ordre croissant. a-AlgorithmeTest(T: tableau d"entiers;n: entier) : bool´een d´ebut variablei: entier i←0 i←i+ 1 fin tant que retourneri≥n-1 fin b-AlgorithmeCompter(T: tableau d"entiers;n: entier) : entier d´ebut variablei,c: entier c←0 pouride0`an-2faire siT[i]> T[i+ 1]alors c←c+ 1 fin si fin pour retournerc fin

Exercice 2 : Nombre d"op´erations

a- Pour effectuerkrecherches dans un tableau non tri´e de taillenil faut compter en moyenne kn

2op´erations.

b- Trier le tableau se fait ennlog2nauquel il faut ajouter la recherche di- chotomique qui se fait en log

2net qu"on doit fairekfois : (n+k)log2n.

c- En moyenne il est donc plus int´eressant de trier le tableau et de faire une recherche dichotomique des quek≥log2n. 1

Exercice 3 : Suppressions

a- On commence par chercher l"´el´ements`a supprimer et ensuite on d´ecale les suivants. Algorithmesuppression(T: tableau d"entiers,s,k: entier) : entier d´ebut variablei,r: entier r←0 r←r+ 1 fin tant que sir > k-1alors retournerk sinon pourider`ak-2faire

T[i]←T[i+ 1]

fin pour retournerk-1 fin si fin b-AlgorithmesuppressionOrdonn´ee(T: tableau d"entiers,s,k: entier) : entier d´ebut variablei,r,d: entier r←0 siT[r] =salors d←d+ 1 fin si r←r+ 1 fin tant que sir > k-1etd= 0alors retournerk sinon pourider-d`ak-2faire

T[i]←T[i+d]

fin pour retournerk-d fin si fin

Exercice 4 : Ordre d´ecroissant

a-AlgorithmetriS´election(T: tableau d"entiers,n: entier) : rien d´ebut 2 variablei,jMax: entier pouride0`an-2faire jMax←indiceMax(T,n,i)

Permuter(T,i,jMax)

fin pour fin AlgorithmePermuter(T: tableau d"entiers,i,j: entier) : rien d´ebut variablex: entier x←T[i]

T[i]←T[j]

T[j]←x

fin AlgorithmeindiceMax(T: tableau d"entiers,n,k: entier) : entier d´ebut variablei,iMax : entier iMax←k pouridek+ 1`an-1faire siT[i]> T[iMax]alors iMax←i fin si fin pour retourneriMax fin b-AlgorithmetriInsertion(T: tableau d"entiers,n: entier) : rien d´ebut variablei: entier pouride1`an-1faire

Ins´erer(T,i)

fin pour fin Algorithmeins´erer(T: tableau d"entiers,i: entier) : rien d´ebut variablej,x: entier x←T[i] j←i-1

T[j+ 1]←T[j]

j←j-1 fin tant que

T[j+ 1]←x

fin 3quotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] Correction TD 8 : Algorithmes de tri - LISIC

[PDF] Les tableaux 1 Exercice 1 - LIPN