Forum de Programmation en langage PANORAMIC
Rechercher
 
 

Résultats par :
 


Rechercher Recherche avancée

Mots-clés

Derniers sujets
» Les bienfaits du rire
Ven 7 Juil - 0:04 par Admin

» Derrière chaque beau parleur se cache un magnifique menteur
Ven 7 Juil - 0:01 par Admin

» Carré magique d’ordre 3 à 99 et plus si affinité !
Mer 5 Juil - 3:21 par Admin

» Dessine-moi une étoile
Mar 4 Juil - 17:32 par Admin

»  Equation paramétrique de la super-ellipse
Mar 4 Juil - 17:29 par Admin

»  Exécution des fichiers CPL
Sam 1 Juil - 14:01 par Admin

» Un papa à la page.
Ven 30 Juin - 15:01 par Admin

»  Exemple de menu
Lun 26 Juin - 22:36 par Admin

» Utilisation du caractère Ampersand (&) dans un caption
Lun 26 Juin - 22:32 par Admin

Juillet 2017
LunMarMerJeuVenSamDim
     12
3456789
10111213141516
17181920212223
24252627282930
31      

Calendrier Calendrier


RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE

Voir le sujet précédent Voir le sujet suivant 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 : 65
Date d'inscription : 08/09/2015
Age : 66
Localisation : MOKNINE (Tunisie)

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

Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

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