Forum de Programmation en langage PANORAMIC
Rechercher
 
 

Résultats par :
 


Rechercher Recherche avancée

Mots-clés

Derniers sujets
»  Animations : Livres et leçons sur le français
Dim 21 Jan - 2:04 par Admin

» Animations FLASH
Lun 1 Jan - 13:01 par Admin

» Bonne Année 2018
Ven 29 Déc - 0:48 par Admin

» Automate cellulaire : simulation de feu de forêt
Sam 9 Déc - 2:56 par Admin

»  Exécution des fichiers CPL
Mar 28 Nov - 19:18 par Admin

» Quelques fonctions de la user32.dll
Sam 25 Nov - 1:43 par Admin

» Copier vers une FORM définie l’image de fond du bureau.
Ven 24 Nov - 2:38 par Admin

»  Capture d’écran de Windows
Ven 17 Nov - 0:27 par Admin

»  Courbes de Bézier cubiques
Mer 8 Nov - 2:28 par Admin

Février 2018
LunMarMerJeuVenSamDim
   1234
567891011
12131415161718
19202122232425
262728    

Calendrier Calendrier


RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE

Aller en bas

RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE

Message par Admin le Ven 23 Juin - 0:46

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 *********************************************************

_________________
Invité, merci d'être passé par ici.
avatar
Admin
Admin

Messages : 78
Date d'inscription : 08/09/2015
Age : 67
Localisation : MOKNINE (Tunisie)

Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com

Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum