Forum de Programmation en langage PANORAMIC
Rechercher
 
 

Résultats par :
 


Rechercher Recherche avancée

Mots-clés

fichiers  

Derniers sujets
» Useful Dog
Ven 6 Avr - 14:25 par Papydall-Admin

» Les Courbes de Bézier cubiques
Ven 30 Mar - 4:08 par Papydall-Admin

» Animation flash
Mer 14 Mar - 2:50 par Papydall-Admin

» Mega-Strip
Lun 12 Mar - 1:24 par Papydall-Admin

» Les oiseaux de mon jardin
Ven 9 Mar - 1:08 par Papydall-Admin

»  Création et gestion d’un livre
Jeu 8 Mar - 15:37 par Papydall-Admin

» Deux questions d’éthique
Mar 6 Mar - 1:56 par Papydall-Admin

»  La Blague Du Jour
Lun 5 Mar - 2:50 par Papydall-Admin

» Branle-Fesse
Lun 5 Mar - 2:46 par Papydall-Admin

Octobre 2018
LunMarMerJeuVenSamDim
1234567
891011121314
15161718192021
22232425262728
293031    

Calendrier Calendrier


RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE

Aller en bas

RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE

Message par Papydall-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
Papydall-Admin
Admin

Messages : 94
Réputation : 0
Date d'inscription : 08/09/2015
Age : 68
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