Forum programmation
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 recherches

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: recherches   Mer 28 Fév - 19:20

On a souvent besoin de rechercher, dans un grand tableau, la position d'un élément donné. Tous les algorithmes est le traitement du cas où l'élément cherché n'est pas dans le tableau. Une autre caractéristique importante d'un algorithme de recherche est son comportement désiré en cas d'éléments identiques (doit-il donner le premier, le dernier, tous ?).

la recherche séquentielle


Il suffit de lire le tableau progressivement du début vers la fin. Si le tableau n'est pas trié, arriver en fin du tableau signifie que l'élément n'existe pas, dans un tableau trié le premier élément trouvé supérieur à l'élément recherché permet d'arrêter la recherche, de plus cette position correspond à celle où il faudrait insérer l'élément cherché pour garder un tableau trié. Une recherche sur un tableau trié nécessitera en moyenne N/2 lectures, mais on se rapprochera de N pour un fichier non trié avec beaucoup de recherches d'éléments inexistants.


la dichotomie


Dans le cas d'un tableau trié, on peut limiter le nombre de lectures à log(N)+1, en cherchant à limiter l'espace de recherche. On compare la valeur cherchée à l'élément central du tableau, si ce n'est pas la bonne, un test permet de trouver dans quelle moitié du tableau on trouvera la valeur. On continue récursivement jusqu'à un sous-tableau de taille 1. Il vaut bien mieux implanter cet algorithme de manière itérative, car la fonction se rappelle jusqu'à trouver la position désirée, puis seulement on effectue les dépilages, alors que l'on n'a plus besoin des états intermédiaires qui ont été mémorisés par la récursivité puisque le problème est résolu.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: recherches   Mer 28 Fév - 21:47

merci Mohamed Very Happy

mais il faudrait ajouter des exemples concrés c.a.d des algorithmes
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: recherches   Mer 28 Fév - 22:12

chakerbh a écrit:
merci Mohamed Very Happy

mais il faudrait ajouter des exemples concrés c.a.d des algorithmes

pas de quoi mon ami;
La recherche séquentielle:

specification de la fonction Recherche_Seq:
Code:


Résultat  : vérifier l'éxistance de l'élément recherché dans le tableau
Traitement :
      *) On va utiliser une boucle répéter pour parcourir le tableau
      *) Le traitement qui se répéte : i <-- i+1
      *) La condition d'arrêt de la boucle : (i=n) OU ( T[i]=valeur)
Donnée : aucune

algorithme:

Code:
0/ fonction recherche (t:vect; n,valeur:entier):booleen

1/ [i <- 0]  {on met entre croché pour dire que c'est une initialisation }
  repeter
  i<- i +1 { ou inc(i) }
  jusqu'à (t[i] = valeur) ou (i = n)

2/ Recherche <- t[i] = valeur

3/ fin recherche
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: recherches   Mer 28 Fév - 22:20

mais Mohamed quel est la différence entre la spécification et l'algorithme ??
à par la numérotaion RIEN !!
moi je crois qu'il faut écrire en français sans utiliser le language algorithmique dans la spécification !!
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: recherches   Mer 28 Fév - 22:28

tu sais chaker bien sûr qu'il ya 2 type de resoudre un probleme informatique, l'analyse ascendente et l'analyse descendent, cette année on utilise l'analyse descendent
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: recherches   Mer 28 Fév - 22:41

mais ce n'est pas le probléme !!
ce que je veux dir c'est de faire la spécification et non l'algorithme dans la premiére partie !!
donc il faut faire des phrases complétes avec des verbes des sujets etc ...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: recherches   Mer 28 Fév - 23:02

Traitement :
*) On va utiliser une boucle répéter pour parcourir le tableau
*) Le traitement qui se répéte : i <-- i+1
*) La condition d'arrêt de la boucle : (i>=n) OU ( T[i]=valeur)
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: recherches   Mer 28 Fév - 23:05

oui c mieu
je vai la mettre dans ton message qui traite de l'algorithme
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: recherches   Mer 28 Fév - 23:24

merci moderateur
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: recherches   Jeu 1 Mar - 0:10

mtcs a écrit:
merci moderateur

de rien Mohamed Very Happy
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Contenu sponsorisé




MessageSujet: Re: recherches   

Revenir en haut Aller en bas
 
recherches
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum programmation :: Programmation :: Delphi & Pascal :: Pascal :: Cours-
Sauter vers: