PureBasic Forums - English

Code: Select all

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Nom du projet : Prototype de fouille Dichotomique
; Fichier : Code Expérimental
; Version : 0.0.0
; Programmation : En progression
; Programmé par : Guimauve
; Date : 25-08-2005
; Mise à jour : 25-08-2005
; Codé pour PureBasic V3.94
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; PRINCIPE DE FONCTIONNEMENT :
;
; On regarde l'element du milieu. S'il est trop petit,
; On recommence dans la partie de droite restante, sinon
; On recommence dans la partie de gauche restante.
; Ainsi, l'espace de recherche diminue de moitié a chaque
; fois.
;
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<<<<<< ! ! ! TRÈS TRÈS TRÈS IMPORTANT ! ! ! <<<<<<<<<<
;
; LE TABLEAU SUR LEQUEL LA FOUILLE EST EFFECTUÉE DOIT ÊTRE
; TRIÉ AVANT DE COMMENCER LA FOUILLE. SI NON LA FOUILLE NE
; FONCTIONNE PAS CORRECTEMENT.
;
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

#Nb_Element = 5
#Max_Random = 5000

Global Dim Tableau.l(#Nb_Element)


Procedure.l DichotomicSearch(ValeurRecherchee.l)
  
  Position.l = -1
  
  Debut.l = 0
  Fin.l = #Nb_Element ; La grandeur du tableau
  
  While Debut <= Fin
    
    ; On trouve le milieu de l'espace de recherche. 
    Milieu = Round((Debut + Fin) / 2,0)
    
    ; On conserve la moitie de droite ou de gauche de l'espace de
    ; recherche
    If ValeurRecherchee < Tableau(Milieu)
      Fin = Milieu - 1
      
    ElseIf ValeurRecherchee > Tableau(Milieu)
      Debut = Milieu + 1
      
      ;Si c'est égal, nous avons trouvé et on retourne la position du milieu    
    Else    
      Debut = Fin + 1
      Position = Milieu                
      
    EndIf 
    
  Wend
  
  ProcedureReturn Position
EndProcedure 

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; On met en place 6 valeurs aléatoire entre 0 et 100 dans le tableau

For index = 0 To #Nb_Element
  Tableau(index) = Random(#Max_Random)
Next 

; On trie le tableau pour que les plus petites valeurs se retrouve au début
SortArray(Tableau(),0)

Debug "On affiche le tableau"
For index = 0 To #Nb_Element
  Debug Tableau(index)
Next 

Debug "On commence à Fouiller dans le tableau"

; on passe toute les valeurs de 0 à 100 pour voir si elle se trouve dans le tableau

For index = 0 To #Max_Random
  
  ;StartTime = ElapsedMilliseconds() 
  Position = DichotomicSearch(index)
  ;ElapsedTime = ElapsedMilliseconds()-StartTime
  
 ; Debug "Temps de Fouille : " + Str(ElapsedTime)
  If Position <> -1
    Debug Str(index) + " trouvé à la position : " + Str(Position)
    Debug "La valeur dans le tableau à cet index " + Str(Position) + " : " + Str(Tableau(Position))
  EndIf 
  
Next 

Code: Select all

function [present, position] = fouille_dichotomique(tableau, valeur)
% FOUILLE_DICHOTOMIQUE retourne true si valeur est dans tableau, false sinon.
% La fonction retourne en plus l'indice de valeur si elle est presente.
% Pour poouvoir fonctionner, le tableau doit etre ordonne en suivant
% l'indice absolu.
%
% PARAMETRES : tableau : Le tableau de donnees trie ou l'on recherche.
%              valeur  : La valeur recherchee.
%
% ATTENTION : - La fonction doit recevoir deux parametres, sinon elle leve
%               l'erreur suivante :
%               'La fonction doit recevoir deux parametres'
%             - tableau doit etre une matrice de nombre reels triee, sinon
%               la fonction leve l'erreur suivante :
%               'Le parametre tableau doit etre une matrice de nombres reels'
%             - valeur doit etre un nombre reel, sinon la fonction leve
%               l'erreur suivante :
%               'Le parametre valeur doit etre un nombre reel'
%
% APPEL :
%           present = fouille_dichotomique([1 2 3 4 5 7 9 12], 3);
%           ou
%           [present position] = fouille_dichotomique([1 2 3 4 5 7 9 12], 3);
%--------------------------------------------------------------------------

    % STRATEGIE : On regarde l'element du milieu. S'il est trop petit,
    %             on recommence dans la partie de droite restante, sinon
    %             on recommence dans la partie de gauche restante.
    %             Ainsi, l'espace de recherche diminue de moitie a chaque
    %             fois.

    % Validation des parametres recus.
    if (nargin ~= 2)
        error('La fonction doit recevoir deux parametres');
    elseif (~isnumeric(tableau) | ~isreal(tableau))
        error('Le parametre tableau doit etre une matrice de nombres reels');
    elseif (~est_un_reel(valeur))
        error('Le parametre valeur doit etre un nombre reel');
    end;
        
    % Fouille dichotomique dans le tableau.
    % Au debut, l'espace de recherche va de 1 a numel(tableau).
    debut = 1;
    fin = numel(tableau);
    present = false;
    position = 0;
    
    while (debut <= fin)
        % On trouve le milieu de l'espace de recherche. (on peut utiliser
        % FIX aussi)
        milieu = round((debut + fin) / 2)
        
        % On conserve la moitie de droite ou de gauche de l'espace de
        % recherche
        if (valeur < tableau(milieu))
            fin = milieu - 1;
            
        elseif (valeur > tableau(milieu))
            debut = milieu + 1;
            
        %Si c'est égal, nous avons trouvé et on retourne la position du milieu    
        else    
            debut = fin + 1;
            position = milieu;                
            present = true;
        end;
    end;
    
return;

Code: Select all

For Index = 0 to 1 000 000
   If ValueSearched = Array(Index)
      Index_of_searched_Value = Index
      Break
   EndIf
Next