ALGORITHME DE RECHERCHE DICHOTOMIQUE
cosmobob
Messages postés
700
Date d'inscription
mardi 30 décembre 2003
Statut
Membre
Dernière intervention
27 janvier 2009
-
27 juil. 2005 à 10:17
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010 - 31 mars 2009 à 22:09
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010 - 31 mars 2009 à 22:09
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
https://codes-sources.commentcamarche.net/source/32909-algorithme-de-recherche-dichotomique
31 mars 2009 à 22:09
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
26 sept. 2005 à 18:58
(Pour ceux qui n'aurait pas compris, on est dans le même établissement scolaire...)
A+ Deck ;)
10 août 2005 à 23:53
7 août 2005 à 15:00
7 août 2005 à 14:41
7 août 2005 à 14:38
le "2" en résultat représentait bien sûr l'indice où se trouve le un cherché.
L'exemple que je vous ai montré est ce qu'il y a de plus simple.
5 août 2005 à 19:39
2 août 2005 à 17:47
2 août 2005 à 08:59
++All
2 août 2005 à 08:37
2 août 2005 à 00:52
tu peux pas le deduire de la valeur des extrémités de ton sous tableau si le tableau est pas ordonné
1 août 2005 à 19:28
[1,2,5,4,3,7,6,8]=[1, 2, 5, 4] [3, 7, 6, 8]
Je vois que 2 est dans la partie gauche donc je prend celle ci
[1, 2, 5, 4] = [1, 2], [5, 4] idem
[1, 2] = [1], [2] je vois que 2 est à droite
1 août 2005 à 11:42
ca n'explique pas pourquoi tu t'orientes vers la sous partie gauche du tableau plutot que vers la droite ce que tu racontes...
29 juil. 2005 à 19:52
29 juil. 2005 à 19:27
RD(#(2,1,2,3,2,3,4,5),1,plancher(1+8/2)) RD(#(2,1,2,3),1,plancher(1+4/2)) 2
où #() est un tableau en Scheme.
Essayez le avec mon interpreteur de langage "K" (c'est mon script que personne ne regarde)
28 juil. 2005 à 16:07
28 juil. 2005 à 15:16
Pour le coup du surjectif, tu parle de l'application x->T[x]? Celle la a l'air plutot injective non? j'ai un peu oublié tout ca...
27 juil. 2005 à 20:23
27 juil. 2005 à 20:21
Quand on varie de un ou de zéro en croissant ou en décroissant, prendre un plus petit intervalle implique que la valeur se trouve dedans. Or nécessairement elle y est puisque on a par hypothèse soit que la valeur n'y est pas (et dans ce cas pas dans le tableau tout entier) soit elle y est au moins une fois car T[inf]<x et T[sup]>x ou alors T[inf]<x et T[sup]>x. Comme les valeurs de T sont "surjectives" (pour vous l'imager bien que T ne soit pas une fonction), x figure obligatoirement dans le sous ensemble. Donc la recherche dicothomique marche.
Un doute ? Demandez le à votre professeur d'informatique (même s'il est à la plage ça peut bouillonner)
27 juil. 2005 à 16:07
27 juil. 2005 à 15:37
27 juil. 2005 à 15:33
/* dicho: cherche x dans v[0..n], avec (0 <= i < j < n) => v[i] < v[j]
int dicho(int x, int v[], int n)
{
int droite n - 1, gauche 0;
while(gauche <= droite)
{
int milieu = (gauche + droite) / 2;
if(x < v[milieu]) droite = milieu - 1;
else if(x > v[milieu]) gauche = milieu + 1;
else return milieu;
}
return -1;
}
27 juil. 2005 à 14:44
27 juil. 2005 à 14:36
27 juil. 2005 à 14:30
Cela signifie que le tableau varie d'amplitude maximale un de proche en proche ; exemple :
la suite 8 7 7 6 5 4 5 6 7 8 9 9 8 7 6 5 4 3
Aucun ordre total ne régit deux éléments isolés.
27 juil. 2005 à 14:20
27 juil. 2005 à 13:49
int __stdcall RechDicho(const int *parray, int nelem, int val)
{
int pos, n, i;
if((n = nelem) <= 0) goto notFOUND;
if(val == parray[0]) return 0;
pos = 1;
while(n >= pos) {
i = (pos + n) / 2;
if(val < parray[i]) n = i - 1;
else pos = i + 1;
if(val == parray[i]) return i;
}
notFOUND: return -1;
}
27 juil. 2005 à 13:48
27 juil. 2005 à 13:45
27 juil. 2005 à 13:42
27 juil. 2005 à 13:37
Pour ce qui est dut 2ième, je doit avouer que ca me parait bizar, je doit prouver en faite que pour tout i, si on fait la valeur pointée par l'indice i + 1 - cette mm valeur on doit aboutir a une résultat plus petit ou égale a 1?
27 juil. 2005 à 12:55
J'y ai repensé après avoir posté, je revois la question dès que possible.
27 juil. 2005 à 12:37
Est ce que la recherche dicothomique marche sur un tableau tel que pour tout i, |T[i+1]-T[i]|<=1 ?
Essaie et conclue avec un exemple.
S'il est vrai que tu ne t'es jamais posé de telles questions, reflechir dessus te fera prendre de l'avance si tu veux faire de l'informatique ton metier.
27 juil. 2005 à 12:27
- La solution que tu m'a proposé ensuite est un parcours sequentiel donc ce n'est pas de la dicotomie.
L'idée est de tester si T[n] est inferieur ou superieur à la valeur cherchée. En fonction de ce test, soit on effectue une recherche dicotomique entre n/2 et n (car T[n/2]<x et T[n]>x), soit on multiplie n par deux.
27 juil. 2005 à 11:49
Comme le dit mon profs de concept, il est parfois préfèrable de ne pas optimiser au maximum un code , car il se pourrai que après celui-ci ne sois plus très compréhensible. Donc je préfères 100fois utilisé un peu plus de mémoire et que mon code soit compréhensible que de tout rétressir lol, surtout que maintenant la mémoire n'est plus une denrée rare comme dans le temps. Mais c'est vrai qu'il faut optimiser sont code, mais pas jusqu'a le rendre incompréhensible. Mais tu a raison que pour la recherche dico on aurai pus prendre l'itératif.
PS: j'ai mis cette source dans initié car, un débutant ds la programmation en générale ne sais pas ce qu'est un algorithme ou alors en à une idée très vague.
++All
27 juil. 2005 à 11:42
27 juil. 2005 à 11:35
Lui fournir un exemple itératif sera plus profitable (enlevez les goto s'ils vous font mal aux yeux):
int __stdcall RechDicho(const int *parray, int nelem, int val)
{
int i, n; // i = PIVOT CENTRAL
if(nelem <= 0) goto notFOUND;
i = nelem / 2;
if(parray[i] == val) goto okFOUND;
if(parray[i] < val) {
while(++i < nelem) {
n = parray[i];
if(n == val) goto okFOUND;
if(n > val) break; // ON SORT ILLICO
}
}
else {
while(--i >= 0) {
n = parray[i];
if(n == val) goto okFOUND;
if(n < val) break; // ON SORT ILLICO
}
}
notFOUND: return -1;
okFOUND: return i;
}
27 juil. 2005 à 10:57
Penche toi plutôt sur cet exemple : comment trouver une valeur dans un tableau trié de longueur inconnue (sans chercher à la connaître) ?
On part du predicat que l'on ne cherche pas le maximum.
(c'est aussi de la dicotomie)
A méditer...
27 juil. 2005 à 10:37
Quel besoin de la récursivité ??? On fait idem en itératif et c'est nettement plus rapide, on supprime en plus un param en ne donnant que le nbr d'élements du tableau.
27 juil. 2005 à 10:28
Merci pour le rapelle.
27 juil. 2005 à 10:17
t'as oublié de dire qu'il fallait que ton tableau soit trié pour que ca marche bien, ce qui est une condition très forte.
a+