ALGORITHME DE RECHERCHE DICHOTOMIQUE

Signaler
Messages postés
700
Date d'inscription
mardi 30 décembre 2003
Statut
Membre
Dernière intervention
27 janvier 2009
-
Messages postés
109
Date d'inscription
jeudi 21 octobre 2004
Statut
Membre
Dernière intervention
7 mars 2010
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/32909-algorithme-de-recherche-dichotomique

Messages postés
109
Date d'inscription
jeudi 21 octobre 2004
Statut
Membre
Dernière intervention
7 mars 2010

bien moi j'ai essayé d'utiliser une méthode de recherche dichotomique sur mon problème(celui qui suit) et je me suis cassé les dents(pas toute) apparemment la dichotomie çà marche que pour la recherche de valeurs distinctes dans une liste et pas pour comparer des intervalles.
Bon, soit voilà le problémo:


je cherche à faire correspondre des intervalles entre eux, je m'explique:

- soit dans un premier fichier texte, disons file1.txt une suite d'intervalles de la forme:

id1 3455 3463
id2 3535 3544
id3 3601 3608
id4 3622 3630
id5 3631 3913
id6 3631 3759
id7 3631 5899
id8 3760 3913
id9 3760 5630
id10 3996 4276
id11 4486 4605
id12 4706 5095
id13 5174 5326
.../...

- dans un second fichier texte, disons file2.txt une aure suite d'intervalles de la forme:

acc_2419732 3268 3285
acc_3041065 3565 3583
acc_362358 3640 3656
acc_3279485 3793 3813
acc_3091017 3794 3811
acc_2807380 3832 3848
acc_3105138 3832 3848
acc_3105139 3832 3848
acc_3105140 3832 3848
acc_3116450 3832 3848
acc_86708 3832 3848
acc_1987802 3922 3938
acc_1679660 4113 4129
acc_891489 4113 4129
acc_2829973 4299 4318
acc_298381 4603 4619
.../...

la question est la suivante: quels sont les intervalles de mon fichier 2 (file2.txt) qui se retrouvent inclus parmi ceux du fichier 1 (file1.txt) ?
en écrivant un simple script en awk (pour les vieux pervers comme moi c sympa le awk):

#!/usr/bin/awk -f
#usage: myprog.awk file2.txt

BEGIN {
while((getline < "file1.txt") > 0){
cpt++
descr[cpt]=$1
start[cpt]=$2
end[cpt]=$3
}
close("file1.txt")
}
{
j=1
while(start[j]<=$2 && j<=cpt){
if(end[j]>=$3){print $1,$2,$3,descr[j],start[j],end[j];j++}
else{j++}
}
}

on obtient comme résultat:

acc_362358 3640 3656 id5 3631 3913
acc_362358 3640 3656 id6 3631 3759
acc_362358 3640 3656 id7 3631 5899
acc_3279485 3793 3813 id5 3631 3913
acc_3279485 3793 3813 id7 3631 5899
acc_3279485 3793 3813 id8 3760 3913
acc_3279485 3793 3813 id9 3760 5630
acc_3091017 3794 3811 id5 3631 3913
acc_3091017 3794 3811 id7 3631 5899
acc_3091017 3794 3811 id8 3760 3913
acc_3091017 3794 3811 id9 3760 5630
acc_2807380 3832 3848 id5 3631 3913
acc_2807380 3832 3848 id7 3631 5899
acc_2807380 3832 3848 id8 3760 3913
acc_2807380 3832 3848 id9 3760 5630
acc_3105138 3832 3848 id5 3631 3913
acc_3105138 3832 3848 id7 3631 5899
acc_3105138 3832 3848 id8 3760 3913
acc_3105138 3832 3848 id9 3760 5630
acc_3105139 3832 3848 id5 3631 3913
acc_3105139 3832 3848 id7 3631 5899
acc_3105139 3832 3848 id8 3760 3913
acc_3105139 3832 3848 id9 3760 5630
acc_3105140 3832 3848 id5 3631 3913
acc_3105140 3832 3848 id7 3631 5899
acc_3105140 3832 3848 id8 3760 3913
acc_3105140 3832 3848 id9 3760 5630
acc_3116450 3832 3848 id5 3631 3913
acc_3116450 3832 3848 id7 3631 5899
acc_3116450 3832 3848 id8 3760 3913
acc_3116450 3832 3848 id9 3760 5630
acc_86708 3832 3848 id5 3631 3913
acc_86708 3832 3848 id7 3631 5899
acc_86708 3832 3848 id8 3760 3913
acc_86708 3832 3848 id9 3760 5630
acc_1987802 3922 3938 id7 3631 5899
acc_1987802 3922 3938 id9 3760 5630
acc_1679660 4113 4129 id7 3631 5899
acc_1679660 4113 4129 id9 3760 5630
acc_1679660 4113 4129 id10 3996 4276
acc_891489 4113 4129 id7 3631 5899
acc_891489 4113 4129 id9 3760 5630à
acc_891489 4113 4129 id10 3996 4276
acc_2829973 4299 4318 id7 3631 5899
acc_2829973 4299 4318 id9 3760 5630
acc_298381 4603 4619 id7 3631 5899.
acc_298381 4603 4619 id9 3760 5630

voili, voilo, bon courage à tous ceux qui n'ont pas encore de dentiers
Messages postés
4
Date d'inscription
vendredi 25 juillet 2003
Statut
Membre
Dernière intervention
21 décembre 2007

Deck_bsd, tu peux au moins dire merci à Mathy (prof d'algorithmique qui a donné cette exercice début 2005)...

(Pour ceux qui n'aurait pas compris, on est dans le même établissement scolaire...)

A+ Deck ;)
Messages postés
220
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
7 avril 2007

Justement, Deck_Bsd l'a écrite, c'est la fonction de prototype int rechDich (int D_intt[], int D_intvaleurRecherchee, int D_intborneInf, int D_intborneSup) ;
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Mais à part des paroles, on pourrait avoir la fonction en C qui fait ce que tu dis ???
Messages postés
220
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
7 avril 2007

RD n'est rien de plus qu'une recherche dicothomique sur le modèle proposé par DECK_BSD, mais dans une écriture plus formelle.
Afficher les 41 commentaires