Ubuntu-fr

nurdys

dichotomie

quelle peut bien m'expliquer le principe en programation c  et des liste chaine  ou me donner un bon lien

LR

Re : dichotomie

Pendant mes cours d'algorithmie, j'ai appris l'algorithme de recherche dichotomique.

C'est un algoritme qui te permet de rechercher dans une liste ordonnée.

Par exemple, si tu as une liste :
0 : 3
1 : 5
2 : 6
3 : 7
4 : 9
5 : 15
6 : 16
7 : 19
8 : 21
9 : 32

et que tu veux trouver la position correspondante au chiffre 16, tu peux

parcourir toute la liste dans l'ordre jusqu'à trouver le 16 et retourner 6.

Ou tu peux prendre la taille de la liste (10),
la diviser par 2 (5),
voir quel chiffre se trouve à la position 5 (15).

Le chiffre que tu cherches est plus grand.

Alors tu prends la deuxième moitié de la liste (à partir de 6),
tu la divises par deux (7)
et tu regardes si le chiffre se trouve à la position 7 (19).

Le chiffre que tu cherches est plus petit. Alors tu prends la première moitié de la deuxième moitié etc etc etc. et finalement tu tombes sur le 16 et tu peux retourner 6.

Enfin c'est ce dont je me souviens

---

La goutte d'eau de pluie

Gou

Re : dichotomie

Tu as un excellent article la-dessus dans wikipedia avec des exemples...

Et pour les listes chainees, tu as ce site: http://www.commentcamarche.net/c/cliste.php3... t'as meme les exemples en C

PS: j'ai tape "listes chainees" dans Google et c'est le premier lien que ca me renvoit donc peut etre que tu l'as deja?

Dernière modification par Gou (Le 29/11/2005, à 14:47)

---

"Un clavier azerty en vaut deux..."
Ubuntu Dapper Drake sur un portable Sony Vaio SZ1M/B
mon blog

nurdys

Re : dichotomie

merci pour wiki mais j'avais deja vu
sauf que jai du mal a aplliker a ma fonction  ax^4+bx^3+cx^2+dx+e=0

Gou

Re : dichotomie

Pour trouver les racines de ton polynome, l'idee est la suivante:

tu te places sur un intervalle [a,b] pour le quel tu sais que ta fonction f ne s'annule qu'une seule fois dans l'intervalle (tu as une encadrement de ta racine: a < r < b). Tu alors (par exemple):

f(a) > 0 et f(b) < 0

Apres, (c'est la que commence ta dichotomie) , tu prend le milieu de ton segment: c = (a+b)/2 et tu regarde le signe de f(c). 2 cas:

1/ Si f(c) est positif, alors, ta fonction etant continue et ne s'annulant qu'une seule fois sur l'intervalle [a,b], tu peux restreindre ton intervalle de recherche de ta racine a [c,b]

2/ Si f(c) est negatif, tu te restreins a [a,c].

Dans les deux cas, tu obtiens un encadrement plus precis de ta racine: tu as reduis l'intervalle de recherche par deux... Apres ca, il ne te reste plus qu'a recommencer pour ton nouvel intervalle et ce jusqu'a ce que l'encadrement te donne une approximation suffisamment fine de ta racine...

Ca c'est pour le principe... apres ca, il faut que tu fasses une etude des variations de ta fonction pour trouver l'intervalle inital...

---

"Un clavier azerty en vaut deux..."
Ubuntu Dapper Drake sur un portable Sony Vaio SZ1M/B
mon blog

nurdys

Re : dichotomie

merci merci