Inscription / Connexion Nouveau Sujet
DM Algorithme de dichotomie
Bonjour à tout le monde 
Le problème ici est que mon prof de mathématique nous as donné un Dm sur ça ( alors qu'il me semble ne l'avoir pas vu hormis un exercice sur un algortyhme en début d'année)que je ne comprends strictement pas. Je suis complètement perdu.... Même si le début parle de fonction ça me bloque. Quelqu'un pourrait-il m'aider ?
Amicalement
B - Recherche d'un algorithme de dichotomie permettant la résolution d'une équation
de type f(x)=0
1 - Assurons-nous que l'équation admette bien une solution sur l'intervalle [a ; b] :
On choisira une fonction f dont la courbe représentative Cf peut
être tracée sur l'intervalle [a ; b] sans lever le crayon.
Ainsi, pour que l'équation f(x)= 0 admette une solution sur [a ; b],
il suffit que (entourer la bonne réponse)
f(a) et f(b) soient de même signe
f(a) et f(b) soient de signes contraires
f(a) et f(b) soient nuls
2 - Dans l'intervalle où se situe la solution, f(x) change donc de signe (et « passe » donc par f(x)=0). Or,
après avoir « coupé » l'intervalle en deux, on a besoin d'un test pour savoir dans lequel des deux
intervalles est la solution (pour l'algorithme du jeu le test était « est-ce que la solution est supérieure
à… ?).
Quel test proposez-vous pour ce nouvel algorithme ?
(entourer la bonne réponse)
si f(a) x f(b) ≤ 0 alors une solution est dans l'intervalle [a ; b]
si f(a) x f(b) = 0 alors une solution est dans l'intervalle [a ; b]
si f(a) + f(b) = 0 alors une solution est dans l'intervalle [a ; b]
si f(a) x f(b) ≥ 0 alors une solution est dans l'intervalle [a ; b]
3 - Si une des bornes de l'intervalle prend la valeur recherchée, il serait intéressant d'arrêter la recherche
et d'afficher la solution exacte.
Compléter l'algorithme de résolution proposé ci-dessous :
(compléter …1 avec « > » ou « < » ; …2 avec « ou » ou « et » ; …3 avec « = » ou « ≠ »)
| Algorithme |
Variables : a, b : nombres réels n : nombre réel f : fonction p : nombre réel Initialisations, entrées : Saisir f, a, b et p Traitement : tant que (b-a) …1 p …2 f(n) …3 0 n prend la valeur ………… si f(a) x f(n) … 0 alors b prend la valeur n sinon … prend la valeur n fin du si fin du tant que Sorties : si f(n) … 0 alors afficher « valeur exacte », n sinon afficher ……………………….. (ou « solution comprise entre » a « et » b) |
| Commentaires | Bornes de l'intervalle [a ;b]
Nouvelle borne Fonction étudiée à définir Précision souhaitée du résultat Pour obtenir la précision souhaitée (ou afficher la solution exacte si on l'obtient) On se place au milieu de l'intervalle Test (voir q.2) |
4 - Implémenter cet algorithme sur Algobox en vous aidant de celui donné pour le jeu.
Résoudre par le calcul l'équation (x - 1)² - 3 = 0. Quelle est l'unique solution sur l'intervalle [0 ;3] ?
Tester ensuite votre programme pour Y1(x)= (x - 1)² - 3 avec pour intervalle de recherche [0 ;3].
6 - Pour aller plus loin…
Sachant que 2 est l'unique solution positive de l'équation x² - 2 = 0. Proposer un algorithme (en
langage naturel) permettant d'obtenir la racine carré d'un nombre x ∈ IR+ .
La seule entrée donnée par l'utilisateur sera la valeur de x (l'intervalle de recherche sera donc déterminé
par le programme).
Bonjour à toi
Je vais essayer de te donner quelques pistes pour démarrer.
1) le mieux serait de faire un dessin. En gros si un dessine comme ça une courbe, quand sommes nous sûrs que cette courbe "passe" par 0, c'est à dire traverse l'axe des abscisses ? Représente les 3 possibilités qui te sont proposées, et regarde dans quelle cas il est certain que la courbe traverse.
2) Regarde un peu avec des exemples chacune des propositions.
Le mieux serait de faire un tableau de signe (donc la réponse, à priori, serait un produit , du style f(a)*f(b) ...)
3) il s'agit d'un algorithme un peu compliqué, et il faudra voir au fur et à mesure de tes idées et bien comprendre qu'elle étape fait chaque ligne (d'ailleurs je pense qu'il manque dans l'initialisation la valeur initiale de n, qui devrait être initialisée à n = b je pense)
Voilà j'espère que ça te dégrossi un peu le travail
Merci beaucoup je vais utiliser se que vous avez dit pour voir. Je tiendrais au courant si c'est bon ou pas
Même si j'aurais préféré que mon prof nous fasse plus travailler les algorithmes
Je suis a faire l'algorihtme et je n'y arrive vraiment pas. Ca me marque erreur de synthaxe je suis bloque depuis 2 jours :/
Voici le début de la synthaxe
http://www.hostingpics.net/viewer.php?id=689132fzqd.png
Je suis perdu 
Alors beaucoup de choses ne vont pas.
Je pense que tu t'es trompé sur les questions 1 et 2, je joints plusieurs dessins pour m'expliquer
Dans la question 1) grâce à mon dessin on voit directement la bonne réponse :
si f(a) et f(b) sont de mêmes signes, alors il n'y a pas nécessairement de solution de f(x) = 0
si f(a) et f(b) sont de signes opposés (ici f(a) >0 et f(b) < 0), il y a nécessairement une solution
si f(a) et f(b) sont nuls, alors il y a certes au moins 2 solutions (a et b) mais ce n'est pas très intéressant (et est d'ailleurs englobé dans le cas f(a) et f(b) de signes opposés au sens large)
donc la bonne réponse est la 2
Pour la question 2) , il fait trouver un test qui permette de dire si f(a) et f(b) sont tous deux de signes opposés. Pour cela, il faut forcément avoir recourt à un produit.
Contrexemples pour la somme :
f(a) = 1 et f(b) = 1 : la somme est positive, mais si f est la fonction constante égale à 1, il n'y a pas de racines
si f(a) + f(b) = 0 alors f(a) = - f(b) , ce qui ne se produit pas nécessairement :
f : x -> x² -1 sur l'intervalle [0;2] : on n'aura jamais f(a) + f(b) = 0, pourtant il y a bel et bien une racine en x = 1
Donc il faut regarder les produits en n'oubliant pas la question précédente qui dit qu'il faut f(a) et f(b) de signes opposés
si f(a)f(b) >= 0 alors f(a) et f(b) sont de même signe
si f(a)f(b) <= 0 alors f(a) et f(b) sont de signes opposés
si f(a) f(b) = 0 alors f(a) = 0 ou f(b) = 0 (produit nul)
Les deux premières conclusion découlent d'un petit tableau de signe facile à vérifier
donc le test principale est SI f(a) * f(b) <= 0 ...
Ensuite revenons au programme lui-même.
Ta déclaration de variable m'a l'air bonne (si le type chaîne correspond bien à une fonction, là tu en sais plus que moi je ne code pas sous Algobox)
les valeurs de a et de b doivent être saisies par l'utilisateur donc tu peux les rentrer par défaut si tu veux.
Ensuite il manque une valeur par défaut de n. Le mieux serait de l'initialiser à n = b
Je pense ensuite que tu n'as pas vraiment compris le but de cet algorithme : on recherche de manière approchée le point d'intersection de la courbe avec l'axe des abscisses, on on procède un peu à tâton.
On prend notre intervalle [a;b] , on le coupe en deux, ce qui revient à regarder les intervalles [a; (a+b)/2] [(a+b)/2 ; b] ensuite on effectue le test f(a)*f(n) <= 0
avec n = (a+b)/2
Si c'est effectivement négatif, alors ça veut dire que notre racine se trouve dans le premier intervalle , donc notre intervalle [a;b] devient [a;(a+b)/2]
Sinon, c'est que la racine est dans l'autre, donc [a;b] devient [(a+b)/2;b]
Donc dans chacun des cas, il faut remplacer soit la valeur de a, soit la valeur de b par (a+b)/2
Enfin dernière chose, p correspond à la précision voulue, c'est à dire l'écart maximal entre b et a attendu.
donc p DOIT être strictement positif.
Par exemple, une approximation de PI à 0.01 près reviendra à rentrer p = 0.01
Merci beaucoup je comprend mieux mon algorthime est presque terminer juste la fin qui bug sinon sa va et la question 6 commençait aussi même si je n'ai pas touujours trouver de truc.
Si d'autre avis n'hésitez pas :p
Pour trouver une valeur approchée d'une racine d'un réel m > 0, il suffit d'utiliser une dichotomie pour résoudre
x² - m = 0
En effet, cette équation a 2 solutions : et
En effectuant une dichotomie sur [0;m], on est sûr d'approcher la racine de m aussi près qu'on veut (il faut pour cela fixer la valeur de p)
Annuler
connectez vous