12 mar 2013 · 3 RECHERCHE DICHOTOMIQUE Algorithme recherche_dichotomique { Recherche le premier indice où se trouve la valeur val en utilisant la
Previous PDF | Next PDF |
[PDF] Recherche dichotomique dans un tableau dentiers - LAMSADE
13 sept 2000 · LANGAGE C - EXEMPLES DE PROGRAMMES Programm int main() e de recherche dichotomique d'un élément dans une liste d'entiers */
[PDF] Algorithmes de Tris
Recherche dans un tableau, dichotomie 7 de 47 Recherche dichotomique itérative Remarque : La recherche dichotomique est récursive terminale Algorithme
[PDF] Algorithmique et Recherche Dichotomique
Peut-on éviter de parcourir tout le tableau pour rechercher le maximum d'un tableau d'entiers non trié ? Exercice 2 Recherche séquentielle dans un annuaire On
[PDF] PLAN DU COURS ALGORITHME DE RECHERCHE
12 mar 2013 · 3 RECHERCHE DICHOTOMIQUE Algorithme recherche_dichotomique { Recherche le premier indice où se trouve la valeur val en utilisant la
[PDF] Recherche dichotomique dans un tableau [re04] Exercice - Unisciel
Soit une structure tabulaire A[1 n] triée en ordre croissant On effectue une recherche dichotomique d'une valeur x comme suit Soient : • g l'indice de gauche
[PDF] Méthodes de programmation Algorithmes de recherche, tri et sélection
(résultat légérement meilleur que pour un vecteur non-ordonné) Opérations sur tableaux ordonnés : – recherche sequentielle O(N) – suppression, insertion : O( N)
[PDF] 4 slides par page - Montefiore Institute ULg
23 déc 2019 · Consolider et étendre vos connaissances d'un langage de programmation (le Recherche dichotomique : 256000 vérifications par seconde
[PDF] Recherche et dénombrement dans des tableaux - Licence 1 - LISIC
28 avr 2013 · Recherche dichotomique d'un élément dans un tableau 3 Dénombrement Dénombrement Recherche itérative : langage algorithmique
[PDF] Récursion Récursivité - Pages Perso
factorielle, Fibonaci, exponenÄaÄon rapide, recherche dichotomique, tri fusion gérée par le langage de programmaÄon : une pile LIFO de taille préfixée
[PDF] exemple de manuel de procedure informatique
[PDF] organisation d une dsi type
[PDF] manuel de procédures informatiques
[PDF] cyberlux 8
[PDF] organisation d'un service informatique dans une entreprise
[PDF] cyberlux 8 crack
[PDF] exemple dossier exploitation informatique
[PDF] cyberlux 8 full
[PDF] bibliographie de max weber
[PDF] max weber pdf
[PDF] max weber économie et société tome 2 pdf
[PDF] max weber le savant et le politique pdf
[PDF] max weber économie et société fiche de lecture
[PDF] max weber économie et société tome 1 résumé
![[PDF] PLAN DU COURS ALGORITHME DE RECHERCHE [PDF] PLAN DU COURS ALGORITHME DE RECHERCHE](https://pdfprof.com/Listes/18/2504-18C5_APIAlgoRechercheTriFusion.pdf.pdf.jpg)
PLAN DU COURS
•Introduction au langage C •Notions de compilation •Variables, types, constantes, •Tableaux, opérateurs •Entrées sorties de base •Structures de contrôle •Algorithmes de recherche •Algorithmes de Tri -Insertion-Fusion •Les pointeurs •Procédures et fonctions •les types composés •Allocation dynamique •Listes Chaînées101MAP - UNS
ALGORITHME DE RECHERCHE
•Objectif : Rechercher une information dans un tableau •Méthode : séquentielle •Soit Tun tableau de N éléments et val l"élément cherché •parcours du tableau à partir du premier élément (T[0]) •Arrêt quand élément trouvé ou si fin de tableau (T[n-1]) •Complexité : •linéaire de l"ordre de n. •Pire cas : parcourt de tout le tableauMAP - UNS102
RECHERCHE SÉQUENTIELLE
Algorithme recherche_sequentielle
{Recherche le premier indice où se trouve la valeur val parmi les N données du tableau tab; affiche l'indicesi la valeur est trouvée. }
variables : T [0, N-1], val entier n, val, indice : entierDébutindice ←0
tant que ( val <> T[indice] && indice < N-1) faire indice ←indice + 1 ftq siT[indice] = val alors
afficher( "l"élément se trouve en : » indice); sinon afficher( " Elément non présent " ); fsi FinMAP - UNS103
7 1 15 8 2
ALGORITHME DE RECHERCHE
•Objectif : Rechercher une information dans un tableau trié •Méthode : dichotomique ou " diviser pour régner » •Soit Tun tableau de N éléments et val l"élément cherché •T est trié •Sinon effectuer un prétraitement de tri. •Comparer valavec l"élément u milieu du tableau T. •Si c"est le même => trouvé •sinon on recommence sur la première moitié ou la seconde selon que val est valmidou val > valmid •Arrêt quand élément trouvé ou si fin de tableau (T[indice-1]) •Complexité : •T(n) nombre d"opérations sur un tableau de taille n •T(n) satisfait l"équation de récurrence T(n) = T(n/2)+1MAP - UNS104
RECHERCHE DICHOTOMIQUE
Algorithme recherche_dichotomique
{Recherche le premier indice où se trouve la valeur val en utilisant la stratégie diviser pour régner }
variables T [0, N-1] , val entier lnf, Sup, N, Mi : entierDébut
Saisir(val)
Inf ← 0
Sup ← N-1
Mi ← (Inf + Sup)/2
tant que ( val <> T[Mi] && Inf <= Sup) faire si val < T[Mi] alorsSup = Mid - 1
sinonInf = Mid + 1
fsiMi ← (Inf + Sup)/2
ftq siT[Mi] = val alors
afficher( " l"élément se trouve en : » Mi); sinon afficher( " Elément non présent " ); fsi FinMAP - UNS105
PLAN DU COURS
•Introduction au langage C •Notions de compilation •Variables, types, constantes, •Tableaux, opérateurs •Entrées sorties de base •Structures de contrôle •Algorithmes de recherche •Algorithmes de Tri -Insertion-Fusion •Les pointeurs •Procédures et fonctions •les types composés •Allocation dynamique •Listes Chaînées106MAP - UNS
ALGORITHMES DE TRI
•Objectif : Etant donné une suite de Nnombres de la ranger par ordre croissant (ou décroissant) •Différents algorithmes •Tri par sélection •Tri se fait en espace constant •Peu économe en temps (2 boucles for imbriquées ) •Boucle interne fait N-1 opérations •Boucle externe fait N-1 à itération 1, N-2 (itération 2) ... •Complexité 2*(N-1)+(N-2) +(N-3) ...+ 1 = (N+1)*N+N! ≈ N2 •Tri à bulles •Peu économe en temps (2 boucles for imbriquées ) •Complexité ≈ N2 •Tri rapide •Econome en temps •Complexité ≈ N*Log(N) •Algorithme récursifMAP - UNS107
ALGORITHME DE TRI
•Objectif : Etant donné une suite de Nnombres de la ranger par ordre croissant (ou décroissant) •Méthode : Tri par sélection •Soit Tun tableau de N éléments •Rechercher le plus petit élément parmi les Net on l"échange à la fin avec le 1er •Puis recherche du plus petit parmi les N-1éléments restant et échange avec le2ème
•... parmi N-k+1éléments restants échange avec le KièmeMAP - UNS108
7 8 9 2 0
0 8 9 2 7
0 2 9 8 70 2 7 8 9
TRI PAR SELECTION
Algorithme tri_selection
{ Ranger par ordre croissant(ou décroissant) une suite de Nnombres rangés dans un tableau T. } variables tab : tableau [0, N-1] de entierN, i, j, indiceMin, ValMin : entier
Début
pour i = 0 àN-2 faire indiceMin ← iValMin ← T[i]
pourj = i +1 àN-1 faire siT[j] < ValMinalors
indiceMin ← jValMin ← T[j]
fsi fpour T[indiceMin] ← T[i] { Echange des deux valeurs }T[i] ← ValMin
fpourFinMAP - UNS109
7 8 9 2 0
7 8 9 2 0
i=0 j=1j=2j=3j=4 indiceMin=0 ValMin=7 indiceMin=3 ValMin=2IndiceMin=4 ValMin=0
T[0]=0
T[4]=7
i=1ALGORITHME DE TRI
•Objectif : faire remonter les plus grandes valeurs en haut de tableau •Méthode : Tri à bulle •Soit Tun tableau de N éléments •Comparer 1erélément avec 2ème. Si 1er>2ème, échanger les deux éléments•Comparer 2èmeélément avec 3ème. Si 2er>3ème, échanger les deux éléments
•... comparer N-2ièmeavec N-1 ième. Si N-2 ième> N-1ième,échanger les deux éléments.
•Recommencer à partir du début tant que vous avez opéré au moins à un échange
MAP - UNS110
5 1 4 2 8
1 5 4 2 8
1 4 2 5 8
TRI À BULLE
Algorithme tri_à_bulle
{ faire remonter les plus grandes valeurs en haut d"un tableau T de Néléments. } variables tab : tableau [0, N-1] de entierN, i, j, temp : entier
nouvel_echange : booleenDébut
répéter nouvel_echange ←faux pouri = 0 àN-1 faire siT[ i ] > T[i+1] alors
temp ← T[ i +1]T[i+1 ] ← T[ i ]
T[ i ] ← temp
nouvel_echange ← vrai fsi fpour tant que nouvel_echange ==vrai FinMAP - UNS111
ALGORITHME D"INSERTION POSITION P
•Objectif : Ajouter un élément dans un tableau trié ou pas. Insertion n"est possible que si il reste de la place dans le tableau. L"Insertion est un décalage à droite des éléments du tableau •Méthode : Insertion Soit Tun tableau de taille de N éléments, On insère unélément
Và un position p
•Variable k positionnée en fin de tableau •Copie de T[k] dans T[k+1] tant que k>=P •Qdk=pranger la valeur ven T[k] •Incrémenter N5 1 4 2 8
pk5 1 4 2 8 8
pk5 1 4 2 2 8
pk5 1 4 4 2 8
p k5 1 v 4 2 8
p112MAP - UNSINSERTION À UNE POSITION P
Algorithme INSERTION_POSITION_P
{ Insérer une valeur và une position pdans un tableau T de Néléments et de taille S}Constantes S= 20
variables T : tableau [0, S-1] de entierN, p , v, : entier
Début
{ Code d'initialisation des N éléments du tableau } Afficher(" entrez val à insérer et position p}Saisir(p); Saisir(v);
si N < S alors pour k= N-1 àp pas-1 faireT[k+1] ← T[k]
fpourT[p] ← v
N ← N+1
sinonAfficher ("Insertion impossible »)
fsiFinMAP - UNS113
ALGORITHME D"INSERTION DANS
TABLEAU TRIÉ
•Objectif: Ajouter un élément dans un tableau trié ou pas. Insertion n"est possible que si il reste de la place dans le tableau. L"Insertion est un décalage à droite des éléments du tableau
•Méthode : Insertion Soit Tun tableau de taille de N éléments triés , On insère un élément V
•Variable k positionnée en fin de tableau •Copie de T[k] dans T[k+1] •tant que k>=0 && V>T[k] •QdT[k]1 2 4 5 8 8
k1 2 4 5 5 8
k1 2 4 4 5 8
k1 2 v 4 5 8
114MAP - UNSk
INSERTION DANS UN TABLEAU TRIÉ
Algorithme INSERTION_V_dans_Tableau-Trié
{ Insérer une valeur và une position pdans un tableau T de Néléments et de taille Srangé
par ordre croissant}