RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE
Page 1 sur 1
RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE
- Code:
' ******************************************************************************
' * RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE
' *
' * DICHOTOMIE.BAS par Papydall
' ******************************************************************************
' Exemple d'utilisation
' La recherche doit se faire sur un tableau trié
' Le tableau peut contenir n'importe quel type de données : entier, réel ,string
' La dichotomie consiste à couper le tableau en 2 et comparer la valeur du milieu
' avec celle à rechercher.
' si la valeur du milieu est supérieure à celle recherchée,on recherche alors
' dans la première moitié sinon dans la seconde.
' Cet algorithme est très rapide : sur un très grand tableau, il est très efficace
' ------------------------------------------------------------------------------
DIM dim% : dim% = 1000000 : ' Dimension du tableau pour notre exemple
DIM T%(dim%) : ' Un tableau d'entiers de dimension un million!
DIM i% : ' Variable compteur
DIM true,false : ' Déclaration des constantes booléènnes
true = 1 : false = 0 : ' Simulation du type booléen
caption 0,"Recherche dichotomique dans un tableau trié"
' ------------------------------------------------------------------------------
' Création d'un tableau d'entiers contenant les valeurs de 1 à 1000000
' (un million et plus si vous voulez!)
' Cette phase de création est assez longue!
' Lorsque vous validez le message "OK pour la recherche",le résultat de la
' recherche s'affiche instantanément : Appréciez la rapidité de l'algorithme !!
' ------------------------------------------------------------------------------
print_locate 100,100 : print " Veuillez patienter, je crée le tableau!"
print_locate 100,120 : print " Cette phase peut durer un certain temps!"
for i% = 1 to dim% : t%(i%) = i% : next i% : ' Remplissage du tableau
print_locate 100,160 : print " Le tableau a été créé : Validez le message"
message "Prêt pour la recherche"
cls
chercher(-10) : ' élément à rechercher ===> il n'est pas dans le tableau
chercher(3) : ' élément à rechercher ===> il est dans le tableau
chercher(999999) : ' élement à rechercher ===> il est dans le tableau
chercher(123456) : ' élément à rechercher ===> il est dans le tableau
chercher(1) : ' élément à rechercher ===> il est dans le tableau
chercher(0) : ' élémént à rechercher ===> il n'est pas dans le tableau
chercher(1000000) : ' élément à rechercher ===> il est dans le tableau
chercher(1110000) : ' élement à rechercher ===> il n'est pas dans le tableau
print_locate 100,100 : print "Terminé"
end
' *****************************************************************************
' Procédure de recherche par dichotomie
SUB chercher(element%)
dim_local premier%,milieu%,dernier%,trouve,position%,texte$
trouve = false : ' L'élément à rechercher n'est pas encore trouvé
premier% = 1 : ' On initialise les variables de debut
dernier% = dim% : ' et de fin du tableau
' Si le 1er élément du tableau est déjà plus grand que la valeur à rechercher,
' ( forcément cet élément n'appartient pas à la liste !)
' on affiche le message et on quitte la procédure
if t%(premier%) > element%
texte$ = str$(element%) + " : cet élément n'appartient pas à la liste"
message texte$ : EXIT_SUB
end_if
' C'est ici que commence la recherche
while (premier% <= dernier%) and trouve = false
milieu% = int((premier% + dernier%)/2)
if t%(milieu%) = element%
trouve = true : position% = milieu% : ' Si on a trouvé, on quitte au prochain WHILE
else : ' non, on n'a pas trouvé
if t%(milieu%) > element% : ' La valeur du milieu est supérieure à l'élément à rechercher ?
dernier% = milieu% : ' La recherche se fera donc dans la moitié gauche
else
premier% = milieu% + 1 : ' Sinon ça sera dans la moitié droite
end_if
end_if
end_while
if trouve = false : ' La recherche n'a pas aboutit ?
texte$ = str$(element%) + " : cet élément n'appartient pas à la liste"
else : ' La recherche est positive
texte$ = str$(element%) + " : cet élémént appartient à la liste "
texte$ = texte$ + chr$(13) + "il est en position: " + str$(position%)
end_if
message texte$ : ' On affiche le message et on quitte
END_SUB
' **************** FIN *********************************************************
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
Lun 1 Jan - 0:25 par Papydall-Admin
» A ceux qui célèbre Noël, bonnes fêtes
Dim 24 Déc - 10:49 par Papydall-Admin
» Joyeux Noël et Bonne Année
Ven 8 Déc - 1:34 par Papydall-Admin
» Planets of the Solar System : Tilts and Spins
Lun 20 Mar - 15:43 par Papydall-Admin
» Bonne Année 2023
Sam 31 Déc - 1:39 par Papydall-Admin
» Fractals - Mandelbrot
Ven 21 Aoû - 22:51 par Papydall-Admin
» Convertisseur Décimal ---> Binaire, Octal, Hexadécimal, ...
Mer 21 Nov - 1:08 par Papydall-Admin
» Balises {USER...}
Lun 19 Nov - 22:12 par Papydall-Admin
» Useful Dog
Ven 6 Avr - 14:25 par Papydall-Admin