Python algorithme de dichotomie
[Il n'est pas correct d'effacer le message initial de la discussion dès lors que quelqu'un s'est donné la peine d'y répondre. Je le rétablis. AD]
Bonjour, je sais que j'avais la solution de ce problème dans le livre de Jean-Philippe PRÉAUX Informatique MP, PC, PT, PSI, sur la différence entre l'utilisation d'un <= ou d'un < lors d'une dichotomie, mais je ne m'en souviens plus.
Voici le code :
Comprenez vous pourquoi ?
Merci bienMerci bien.
[Pour afficher du code python, IL FAUT utiliser le bouton "Code" (5ème par la droite au dessus de la fenêtre d'édition. AD]
Bonjour, je sais que j'avais la solution de ce problème dans le livre de Jean-Philippe PRÉAUX Informatique MP, PC, PT, PSI, sur la différence entre l'utilisation d'un <= ou d'un < lors d'une dichotomie, mais je ne m'en souviens plus.
Voici le code :
from matplotlib.pyplot import * from numpy import * from random import * x = arange(0,10,0.5) def fonction(x): return x-3 def dichotomie1(f,a,b): if(f(a)*f(b) >= 0): return None while(abs(b-a)>10**(-2)): m = (a+b)/2 if(f(a)*f(m)<=0): b = m else : a = m return (a+b)/2 def dichotomie2(f,a,b): if(f(a)*f(b) > 0): return None while(abs(b-a)>10**(-2)): m = (a+b)/2 print(" a = ", a ," b = ",b) print(" f(a) = ", f(a) ," f(b) = ",f(b)," f(m) = ",f(m)) print("f(a)*f(m) = ",f(a)*f(m)) if(f(a)*f(m) < 0): b = m else : a = m return (a+b)/2 def dichotomie3(f,a,b): if(f(a)*f(b) > 0): return None while(abs(b-a)>10**(-2)): m = (a+b)/2 print(" a = ", a ," b = ",b) print(" f(a) = ", f(a) ," f(b) = ",f(b)," f(m) = ",f(m)) print("f(a)*f(m) = ",f(a)*f(m)) if(f(a)*f(m) > 0): a = m else : b = m return (a+b)/2Dicho 1 et 3 fonctionnent, mais pas la 2.
Comprenez vous pourquoi ?
Merci bienMerci bien.
[Pour afficher du code python, IL FAUT utiliser le bouton "Code" (5ème par la droite au dessus de la fenêtre d'édition. AD]
Cette discussion a été fermée.
Réponses
dans ce test très limité , les 3 versions fonctionnent et donnent le même résultat :
Python 3.8.6 (tags/v3.8.6:db45529, Sep 23 2020, 15:52:53) [MSC v.1927 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>>
===== RESTART: C:/Users/feclm/Documents/Fernand/python/dicotomie_exemple.py ====
resul 1: -1.9970703125
resul 2: -1.9970703125
resul 3: -1.9970703125
>>>
Cordialement
Le problème est lorsque f(m) = 0, il y a un -0 qui apparait. C'est très rare mais cela peut arriver.
Vous n'utilisez pas ma fonction, vous modifiez l'algorithme.
Par exemple : C'est dommage quand même de ne pas pouvoir effectuer une dichotomie correctement sur une simple fonction affine ? Même si le but est d'étudier les racines de fonctions un peu plus compliquées... mais bon, on peut au moins essayer de comprendre pourquoi cela ne fonctionne pas.
Ta méthode est douteuse car tu méconnais la bonne réponse. Même si tu la trouves, tu vas continuer à chercher. Si tu coupes ton intervalle en 2, tu n'es jamais à l'abri de tomber sur la bonne réponse. A priori, c'est cela qui manque. Vérifions-le sur les 3 algorithmes.
Code 1 : Si "m" est la solution, "b" prend la valeur de "m". Et "a" va s'évertuer à se rapprocher de la solution, sans jamais l'atteindre évidemment, par définition même de la dichotomie (on coupe en deux à l'infini).
Code 2 : Si "m" est la solution, "a" prend la valeur de "m". f(a)=0. Au tour suivant, tu vas choisir un "m" entre la bonne réponse et b. f(m) et f(b) sont alors de même signe. Comme "a" prend la valeur de "m", f(a) et f(b) sont de même signe. Et c'est le drame.
Code 3: Si "m" est la solution, "b" prend la valeur de "m". Et "a" va s'évertuer à se rapprocher de "b" comme dans le premier code.
Bonjour, ce n'est pas un problème d'algorithmie, mais de langage de programmation en l'occurence python.
Les trois algorithmes sont corrects, cependant il y a un problème en langage python.
Tester le programme ci-contre, et la réponse sera incorrecte dans le cas dicho2 pour ma fonction.
Merci bien.
Je n'avais pas exécuté ton code. Je viens de le faire. Et cela me donne totalement raison.
Quand a=2, c'est la bonne réponse. Du coup, ton code déraille. Au tour suivant a=3 et b=4. Et c'est foutu. Puisque la bonne réponse est 2.
PS : Connais-tu la différence entre la division entière et la division réelle ? Un petit "a=a*1.0" et "b=1.0*b" ne seraient pas de refus.