A voir également:
- Recherche trichotomique python
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Citizen code python avis - Accueil - Outils
- Rechercher ou entrer l'adresse mm - recherche google - Guide
- Recherche photo - Guide
- Je recherche une chanson - Guide
c'est le genre d'exercice qui amuse mes profs de programmation apparemment.
Je ne men sort toujours pas, est ce que quelqu'un aurait une idée de comment résoudre çà???
Je dois le rendre lundi :(
on regarde en fait à chaque fois en supposant que ta liste est dans l'ordre, si l'élément qu'on cherche est dans la première moitié ou la deuxième moitié. Pour ça on regarde l'élément qui sépare en deux (c-à-d l'élément du milieu, ou presque car des fois il n'y a pas exactement de milieu, peu importe si tu prend un peu après le milieu ou avant).
On regarde donc cet élément, s'il est avant ce qu'on cherche et bien il faut contineur à chercher (récursivement) dans la deuxième moitié, sinon dans la première.
Ici c'est pareil, sauf qu'à chaque "étape", il faut décider si on va chercher dans le premier tiers, le deuxième tiers ou le troisième.
Il faut donc prendre les deux éléments qui séparent ta liste à peu près en 3. (c-à-d, à peu près, taille du tableau/3 et deux fois taille du tableau / 3. La comparaison est un peu plus ch**** car tu dois décider : est-ce que l'élément que je cherche est :
1) avant la première borne
2)entre la première et la deuxième borne
3) après la troisième
c'est juste cette décision qui change, le reste est la même chose...
Oui j'ai compris le principe de la recherche par dichotomie.
Je sais que la recherche trichotomique consiste a diviser le tableau en 3 partie (a peu près égales)
Mais comment faire sa?
Comment déterminer le premier tiers le deuxième et le troisième??
En fait j'ai pas compris ceci: "taille du tableau/3 et deux fois taille du tableau / 3"
Pourquoi deux fois taille du tableau/3 ???
Imagine tu cherches quelqu'un dans une liste. Tu cherches "Johnny". Ta liste a 20 noms, numérotés de 1 à 20.
Par recherche dichotomique, on regarderait où ?
Et bien au milieu.
Oui mais c'est quoi le milieu ?
Et bien c'est l'indice numéro... 10.5 ! (le milieu entre 1 et 20 c'est (1+20)/2 )il n'y a pas d'indice 4.5 alors on arrondi, à 4 ou à 5 peu importe, c'est toi qui choisi. disons qu'on arrondi au dessous, donc on prend le 10ème indice.
et on regarde ce que c'est : c'est Marc par exemple. Donc on doit rechercher dans la première moitié. On recrée un tableau en éliminant Marc et tous les noms après (on ne prend que ceux qui sont avant Marc, avant l'indice 10)
A quel indice tu dois prendre pour faire la moitié de cette première partie ?
Cette fois le tableau restant est numéroté de 1 à 9. son milieu c'est (1+9)/2 c'est 5... alors on regarde le 5ème nom.
Imagine que c'est bernard. Alors Johnny dois se trouver après. Donc on refait un tableau avec tous ceux après Bernard, donc après le 5ème indice. Il reste donc 3 éléments, qu'on va numéroter de 1 à 3. Le milieu c'est 2 (là c'est très facile à voir... mais ça marche toujours avec ma "formule" (1+3)/2.
etc...
Si à un moment le tableau qu'il reste est vide alors il faut arrêter la récursion (et renvoyer une valeur impossible comme -1 etc... enfin tu dois connaitre ).
La bonne nouvelle c'est que comme les indices de ton tableau commencent surement à 0, il suffit de faire le numéro du dernier élément divisé par 2 pour trouver le milieu, pas besoin du "+ 1" (car moi je commençais à un). (Le numéro du dernier élément c'est taille-1)
Si t as compris mon gros blabla précédent, alors tout le problème est de trouver le bon endroit qui va être "le tiers" et "les deux tiers" de ta liste. (au lieu "du milieu" avant).
voici clairement en gras le milieu de 11 éléments
0 1 2 3 4 5 6 7 8 9 10
(le tableau est de taille 13, c'est bien (13-1)/2, c-à-d (taille-1)/2 )
voici clairement en gras les "tiers" et "deux tiers" de ces 11 éléments
0 1 2 3 4 5 6 7 8 9 10
comment trouver le 3 par calcul à l'aide de la taille ? en faisant (taille-2)/3
et comment trouver le 2ème ? et bien c'est juste le double du premier ! c-à-d 2*(taille-2)/3
Note que ce calcul est valable si taille est au moins 2. Et c'est logique... tu ne peux pas trouver 2 endroits où couper si ton tableau n'a qu'un élément.
Ouf as-tu compris ?
Désolé du long blabla...
Merci pacorabanix.
Je vais essayer de transformer tout ça en algorithme et voir si ça marche :)
Encore merci. :D
(P.S: Pour la recherche dichotomique ce n'était pas nécessaire mais merci quand même :) )
++