Discussion :

[alexei46]

bonjour
je recherche deux autres façons de revercher un élément dans un vecteur non-trié? j'en ai trouver un mais je n'arrive pas à trouver les deux autres!
merci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
I=0 
TANT QUE NON FIN DE LISTE 
 SI ELEMENT[i] EST DIFFERENT DE ELEMENT_CHERCHE 
  ALORS INCREMENTER I 
 SINON AFFICHER TROUVE EN I 
 IS 
FIN TANT QUE

[Franck.H]

Salut, tu as la recherche Dichotomique: http://fr.wikipedia.org/wiki/Dichotomie

[nicolas.sitbon]

Logiquement la dichotomie c'est pour un vecteur trié.

[Franck.H]

Logiquement la dichotomie c'est pour un vecteur trié.

Arf oui c'est vrai il a un non-trié lui, pas d'bol

[aoyou]

Recherche aléatoire... Tu tires au hasard l'indice et tu fais confiance à ta chance mais c'est un peu lourd pour rechercher un élément dans un tableau.

[PsychoH13]

Personnellement, je ne vois pas d'autres techniques pour chercher dans un vecteur non trié... À part vérifier toutes les valeurs jusqu'à trouver la bonne...

[forthx]

cela doit etre fondemantalement differant?
sinon:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
I=FIN DE LISTE
TANT QUE (I >= DEBUT DE LISTE) ET (ELEMENT[i] EST DIFFERENT  ELEMENT_CHERCHE)
 DECREMENTER I 
FIN TANT QUE 
 
SI I >= DEBUT DE LISTE
 AFFICHER TROUVE EN I

une autre methode peut consister justement a trier ton vecteur et chercher ensuite (je voi pas trop l'interet vu que c'est plus long mais bon)

[sidahmed]

Bonjour,

Personnellement, je ne vois pas d'autres techniques pour chercher dans un vecteur non trié... À part vérifier toutes les valeurs jusqu'à trouver la bonne...

Si, il y a les méthodes de hachage !

Cordialement,
Sidahmed.

[PsychoH13]

Bonjour,

Si, il y a les méthodes de hachage !

Cordialement,
Sidahmed.

Disons que les méthodes de hachages impliquent une sorte de tri aussi...

[sidahmed]

Disons que les méthodes de hachages impliquent une sorte de tri aussi...

Je pense pas, pour gagner en temps d'accès on utilise la méthode dichotomique dans le cas d'un tableau trié et la méthode de hachage dans le cas d'un tableau non trié, voire trié ! Sans parler des arbres binaires de recherche, B-arbres, hachage dynamique...

[fremen167]

Mais pour pouvoir utiliser une méthode de hachage, il faut être capable de définir la fonction de hachage. Ce n'est pas à proprement parler un tri, mais dans l'énoncé, rien ne nous permet de savoir comment les données sont placées dans la liste.
Pour ce qui est des arbres, c'est un peu le même problème : il faut avoir inséré les données dans l'arbre avant d'y faire une recherche. Donc ce que tu proposes en gros, c'est de changer la structure des données, puis ensuite d'exploiter cette nouvelle structure. Je n'ai pas l'impression que ça répond à la question, je rejoins PsychoH13.

Peut-être que la question n'est pas de trouver un autre algorithme, mais une autre manière de l'implémenter ? Par exemple, récursivement :
Recherche :
Si fin liste, pas trouvé
Si 1er élement = recherché, trouvé
Sinon, recherche (suite).

[sidahmed]

Bonjour,

Mais pour pouvoir utiliser une méthode de hachage, il faut être capable de définir la fonction de hachage. Ce n'est pas à proprement parler un tri, mais dans l'énoncé, rien ne nous permet de savoir comment les données sont placées dans la liste.

J'ai pas dit que les méthodes de hachage s'appliquent dans le cas des tableaux (fichiers) ordonnés, tu peux insérer des éléments dans n'importe quel ordre, ensuite la recherche d'un élément se fait en 2 accès au plus.

[PRomu@ld]

Le problème avec la méthode de hachage est qu'elle suppose une connaissance du tableau d'origine (et donc avoir potentiellement recherché l'élément que l'on veut chercher ...). Autre problème, si la fonction de hachage est mal choisie, il peut y avoir des collisions ce qui entraîne une gestion un peu plus délicate.

La méthode aléatoire n'est vraiment pas une bonne méthode, puisque si on veut rechercher l'élément, il faudra tout de même tester toutes les positions du tableau. Tu rajoutes donc le tirage aléatoire (sans remise et uniforme), sans rien ajouter.

Sinon, pour en revenir au PO, a vrai dire, si tu ne sais rien sur ton tableau, la méthode brute est la seule. Ensuite qu'elle soit récursive ou non, c'est une question de paradigme de programmation, mais ça reste fondamentalement la même chose.

[sidahmed]

Bonjour,

Autre problème, si la fonction de hachage est mal choisie, il peut y avoir des collisions ce qui entraîne une gestion un peu plus délicate.

C'est pour ça qu'on parle de hachage dynamique et en particulier le hachage linéaire !

Cordialement,
Sidahmed.

[PRomu@ld]

C'est pour ça qu'on parle de hachage dynamique et en particulier le hachage linéaire !

C'est bien ce que j'entendais par gestion plus délicate.

Comme l'a dit fremen167, ça revient à changer la structure de donnée, ce qui n'est pas forcément ce que veut alexei46.