Version imprimable
bonjour,
le prof nous a demander de resoudre un exo qui sera noté par la suite sur la methode de dichotomie.
en effet, il nous a demander de rediger l'algorithme et faire l'organigramme de la methode de dichotomie ; pour cela je demande de l'aide:? y a t 'il quelqu'un qui maitrise cette methode et qui pourra m'aider ou m'orienter vers des sites important.
je vous remercie d'avance
le problème c'est qu'il y a plusieurs "dichotomie".
Il y a la "recherche par dichotomie", faisable sur des listes *triées* au départ.
En fait tu connais la taille du tableau, donc tu peux regarder au milieu.
Si ce que tu vois au milieu du tableau est ce que tu cherches, alors c'est bon.
Si ce que tu vois est plus grand que ce que tu cherches, alors il fallait aller avant -> tu iras à la moitié de la partie précédente (c'est à dire au quart du tableau...).
Si ce que tu vois est plus petit que ce que tu cherches, il fallait aller après -> tu iras à la moitié de la partie suivante (donc aux 3/4 du tableau)
Un bon exemple avec un annuaire -> Tu l'ouvres au milieu pour chercher le nom d'un ami. Tu as séparé l'annuaire en 2 -> la première moitié et la deuxième moitié. Si ton ami s'appelle "M. Fred" et que tu es arrivé dans les M, tu iras maintenant faire ta recherche (prendre le milieu) sur la première moitié. Si ton ami dont tu cherches le numéro s'appelle M. X, tu iras sur la deuxième moitié
Sinon il y a aussi la méthode de dichotomie pour trouver les racines d'une fonction mathématique continue. Il y a aussi ce principe de "couper en 2" a chaque fois la zone de recherche.
sur un intervale [a;b] où f(a) et f(b) n'ont pas le même signe, et où f est continue , on sait qu'il existe une valeur entre a et b qui passe par "0" (c-à-d un certain nombre c où f(c)=0 ).
On la cherche "au bol" en prenant au milieu de a et b : m=(a+b)/2
Ensuite on continue la recherche sur un interval deux-fois plus petit : [a; m] ou [m;b], selon le signe de f(m) (c-à-d si on constate que la racine de la fonction est entre a et m ou entre b et m).
On continue ainsi en boucle, en vérifiant que m n'est pas deja la bonne solution bien sur :) .
Par contre on ne peut pas etre sur de tomber ainsi sur la vraie solution, car elle peut etre irrationelle. Il faut donc se fixer une "marge d'erreur" e telle que si |f(m)| < e alors on considère qu'on a trouvé la bonne solution.
Bonjour,
Cet algorothme est extrêmement connu et le web regorge de renseignements la concernant => Fais une recherche sur :google: avant de poser la question.Citation:
Envoyé par fati21
Dis nous alors si tu ne comprends pas quelques chose et nous t'orienterons.
merci paco d'avoir repondu à mon message, en fait je cherche a faire un algorithme et un organigramme de la methode de dichotomie pour chercher un maximum, vous savez j'ai pas pas fait d'algorithme auparavant et la meilleur c'est que notre prof nous a encore demander de faire un programme en fortran , je suis vraiment perdue.
Une recherche sur google te donnera plein de chose :evilred: :evilred: :evilred:
Mais bon regarde ce lien:
http://fr.wikipedia.org/wiki/Dichotomie
De plus le fichier joint ;););)
salut nabil
Tout d'abord je vous remercie pour votre réponse mais sincèrement ce n'est pas ce que je cherche
Vous savez j'ai cherché sur internet et je n'ai pas trouvé ; en fait je cherche a faire un algorithme et un organigramme avec la méthode de dichotomie mais en cherchant l'optimum c'est à dire optimisation (chercher le Xmax).
Voici les étapes données par le prof
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Aider moi je suis perdue:(:(
Moi je dirais plutot:
Code:
2
3
4
5
6
7
8
9
10
11x1 x2 ----|----+--|--+----|----> a m b m = (a+b)/2 x1 = m – ε/2 x2 = m + ε/2 si f(x1) < f(x2) le max se trouve dans l'intervalle [m,b] si f(x1) > f(x2) le max se trouve dans l'intervalle [a,m]
je pense que ton algorithme sera comme suit :
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
je te remercie nabil pour ta reponse :lol: