Algorithme de recherche dichotomique

Soyez le premier à donner votre avis sur cette source.

Vue 44 122 fois - Téléchargée 542 fois

Description

Bonjour,

Voila, beaucoup sur ce site cherche souvent des méthodes pour recherche une variable dans un tableau ou autre. Je me susi dit pourquoi pas mettre cet algorithme bien pratique et surtout TRES éfficace; Ici il est programmer pour la recherche d'un entier dans un tableau. La fonction de test est aussi programée. Il n'y a pas de commentaire car le code est simple. Mais si il y à quand mm des questions, n'hésité pas.

++All

Source / Exemple :


#include "entete.h"

int rechDich (int D_intt[], int D_intvaleurRecherchee, int D_intborneInf, int D_intborneSup)
{
	
	int D_intmilieu; /* milieu */
	/*int x; valeur de la borne du milieu (facultatif) */

	if (D_intborneSup<D_intborneInf)
	{
		return -1;
	}
	else
	{
		D_intmilieu = ((D_intborneInf + D_intborneSup)/2);
		/*x = t[milieu]; (facultatif)*/
			if (D_intvaleurRecherchee==D_intt[D_intmilieu])
			{
				return D_intmilieu;
			}

			else 
			{
				if (D_intvaleurRecherchee<D_intt[D_intmilieu])
				{
					return(rechDich(D_intt,D_intvaleurRecherchee,D_intborneInf,D_intmilieu-1));
				}
				else
				{	
					return(rechDich(D_intt,D_intvaleurRecherchee,D_intmilieu+1, D_intborneSup));
				}

			}
	}
}

void main()
{
	
	short int D_intchoix = -1, test = 0;
	int D_intt[15]={-2,0,1,2,5,9,11,45,56,100,101,205,236,360,1001};
	int D_intborneInf = 0;
	int D_intborneSup =14;
	int D_intvaleurRecherchee;
	char D_chrep='o';

	do
	{
		D_intborneSup = 14;
		clrscr();
		textcolor(4);
		cprintf("\n Tableau paire ou impaire? (1/2) :");scanf ("%d", &D_intchoix);
      if (D_intchoix==2)
      {
      	D_intborneSup -= 1;
      }
      if (D_intchoix <= 2)
      {
      	textcolor(4);
         cprintf("\nintroduisez une valeur a rechercher :"); scanf ("%d",&D_intvaleurRecherchee);
         if (rechDich (D_intt,D_intvaleurRecherchee,D_intborneInf,D_intborneSup) == -1)
         {
         	textcolor(1);
            cprintf("\n\n\t\a !! La valeur ne se trouve pas dans le tableau !!");
         }
         else
         {
         	textcolor(2);
            printf("\n\n\tindice de la valeur dans le tableau : %d" , rechDich(D_intt,D_intvaleurRecherchee,D_intborneInf,D_intborneSup));
         }
			textcolor(4);
			fflush(stdin);
			printf("\n\n voulez-vous introduire une nouvelle valeur? (o/n) :");scanf("%c", &D_chrep);
      }
      else
      {
			textcolor(1);
			cprintf("\n\t!! vous avez introduit un choix non conforme !!");
			getch();
			D_chrep='o';
      }

	}while (D_chrep=='o');
}

Conclusion :


Ya t-il des questions? ;)

Codes Sources

A voir également

Ajouter un commentaire Commentaires
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
29
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

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.