Inscription / Connexion Nouveau Sujet
algorithme- balayage successifs- fonctions
On souhaite créer un algorithme qui permet de déterminer les décimales successives des solutions de f(x)=0
1) Quelle condition doivent vérifier deux images successives tableau de valeur pour que leurs antécédents encadrent la solution de f(x)=0?
2) Ecrire un algorithme qui permet de trouver l'arrondi par défaut à 10^-8 près de la solution.
3) Le faire fonctionner et donner votre proposition (penser à vérifier). Vous pouvez l'écrire en français ou avec le vocabulaire de votre calculatrice ou encore avec algobox.
Mes réponses:
1- Il faudrait que le fonction change de signe donc que les deux images successives du tableau soient de signe opposés. ALORS f(a)<0 <f(b) OU f(b)<0<f(a).
2-
Variables : a , p nombres
Entrée: saisir a
saisir p
Traitement:
Tant que 0 <f(a) X f(a+p)
a prend la valeur a+p
Si 0<f(a) X f(b)
Fin tant que
Sortie: Afficher a
Afficher a+p
Avec p le pas. Ici, p= 0.000 000 01
Voilà pouvez-vous me corriger svp?
p n'est pas un pas, mais un encadrement.
La recherche se fait par dichotomie.
Un truc du genre :
saisir a, saisir b
p prend la valeur 10-8
Tant que abs(a - b) > p
c prend la valeur (a + b)/2
si f(c)*f(b) > 0 alors b prend la valeur c
sinon a prend la valeur c
Fin tant que
afficher (a+b)/2
REM :
comme on veut l'arrondi par défaut à 10^-8 près de la solution
ce n'est pas (a + b)/2 qu'il faudra afficher...
Bonjour,
la façon dont est écrit l'énoncé suggère bien des balayages successifs et pas du tout une méthode par dichotomie.
le but est bien d'obtenir les chiffres successifs, un par un.
un exemple de ce que doit faire l'algorithme avec une fonction f(x) = x^3 - 2x² - 5
cherchons les racines entre 0 et 9
x = 0 f(x) = -5
x = 1 f(x) = -6
x = 2 f(x) = -5
x = 3 f(x) = 4 terminé, changement de signe
on va donc chercher entre 2 et 3 pour obtenir le chiffre suivant, donc par pas de 0.1 :
x = 2.0 f(x) = -5
x = 2.1 f(x) = -4.559
x = 2.2 f(x) = -4.032
x = 2.3 f(x) = -3.413
x = 2.4 f(x) = -2.696
x = 2.5 f(x) = -1.875
x = 2.6 f(x) = -0.944
x = 2.7 f(x) = 0.1030 terminé, changement de signe
on va donc chercher entre 2.6 et 2.7, donc par pas de 0.01
x = 2.60 f(x) = -0.944
x = 2.61 f(x) = -0.844619
x = 2.62 f(x) = -0.744072
x = 2.63 f(x) = -0.642353
x = 2.64 f(x) = -0.539456
x = 2.65 f(x) = -0.435375
x = 2.66 f(x) = -0.330104
x = 2.67 f(x) = -0.223637
x = 2.68 f(x) = -0.115968
x = 2.69 f(x) = -0.007091
x = 2.70 f(x) = 0.1030 terminé, changement de signe
on va donc chercher entre 2.69 et 2.70 par pas de 0.001
etc
d'où son nom de balayages (on balaye les valeurs par pas fixé) successifs (et on recommence avec un pas plus fin)
on va donc avoir pour cet algorithme :
une boucle qui essaye les valeurs par pas de p
contenue dans une boucle qui divise p par 10
cette dernière boucle, la plus externe, sur p, s'arrêtant à la précision demandée
les valeurs initiales (de x) et le pas initial (ici c'était 1, mais ça peut être 10 ou 0.1) dépendant de la fonction et d'une étude préalable qui en a été faite (variations)
le but n'est pas de trouver la solution par la méthode la plus efficace (qui serait bien par dichotomie, c'est à dire "balayages successifs en base 2 !), mais de faire ce qui est demandé dans l'énoncé : trouver les chiffres successifs.
Du coup cet algorithme non plus ne répond pas à la consigne?
VARIABLES
precision EST_DU_TYPE NOMBRE
a EST_DU_TYPE NOMBRE
b EST_DU_TYPE NOMBRE
m EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
precision PREND_LA_VALEUR 0.00000001
LIRE a
LIRE b
TANT_QUE (b-a>precision) FAIRE
DEBUT_TANT_QUE
m PREND_LA_VALEUR (a+b)/2
SI (F1(m)*F1(b)>0) ALORS
DEBUT_SI
b PREND_LA_VALEUR m
FIN_SI
SINON
DEBUT_SINON
a PREND_LA_VALEUR m
FIN_SINON
FIN_TANT_QUE
AFFICHER a
AFFICHER " < solution < "
AFFICHER b
FIN_ALGORITHME
avec F1 définie par f1(x)= -3*x-5+(2*x+8)/(x*x+1)
à mon avis non, puisqu il n'obtient pas les décimales successivement mais des valeurs de plus en plus précises par dichotomie. (c'est la méthode proposée par pgeod)
il trouve bien la solution, mais pas par la méthode suggérée par l'énoncé
le but de cette suggestion étant de savoir imbriquer une boucle à l'intérieur d'une autre, et pas tellement de trouver la solution de l'équation, qui n'est qu'un prétexte.
Je m'essaie au balayage, cet algorithme permet-il de déterminer les décimales successives des solution f(x)=0?
VARIABLES
a EST_DU_TYPE NOMBRE
precision EST_DU_TYPE NOMBRE
x EST_DU_TYPE NOMBRE
inf EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE a
LIRE precision
x PREND_LA_VALEUR a
TANT_QUE(F1(a)*F1(x)>0) FAIRE
DEBUT_TANT_QUE
x PREND_LA_VALEUR x+precision
FIN_TANT_QUE
inf PREND_LA_VALEUR x-precision
AFFICHER inf
AFFICHER " < solution <= "
AFFICHER x
FIN_ALGORITHME
avec F1 définie par f1(x)= -3*x-5+(2*x+8)/(x*x+1)
ceci est un balayage simple pas une succession de balayages chiffre par chiffre
regarde mon exemple (c'est UN exemple, pas des exemples)
tu avais une première boucle par pas de 1 qui "essaye" un par un les chiffres des unités
puis une deuxième boucle par pas de 0.1 qui "essaye" les chiffres des dixièmes
puis une 3ème boucle par pas de 0.01 qui "essaye" les chiffres des centièmes
etc
évidemment toutes ces boucles là on ne les fait pas comme ça à la queue leu leu "séparément" dans des exécutions séparées du programme !
on fait une boucle qui contient ces boucles
c'est justement le but de cet exercice : les boucles imbriquées
une boucle sur la valeur du pas de plus en plus petite
qui contient une boucle sur les valeurs de x
toi tu as fait juste la boucle interne : la boucle sur les valeurs de x
avec un pas fixe que tu as appelé précision
tu vois bien que si tu saisis précision = 0.00000001 ton algorithme risque fort d'exécuter ta boucle unique des milliards de fois avant de s'arrêter
ce n'est justement pas du tout ce qu'on veut, mais effectuer un balayage de plus en plus fin, chiffre par chiffres
si je veux 8 chiffres il y aura au plus 10 (de 0 à 9) fois 8 = 80 boucles en tout.
et "en moyenne" on pourrait estimer que ce serait plutôt environ la moitié (si on considère qu'il y a autant de chance d'avoir un certain chiffre < 5 que > 5)
a EST_DU_TYPE NOMBRE
precision EST_DU_TYPE NOMBRE
x EST_DU_TYPE NOMBRE
inf EST_DU_TYPE NOMBRE
h EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE a
LIRE precision
x PREND_LA_VALEUR a
TANT_QUE (F1(a)*F1(x)>0) FAIRE
DEBUT_TANT_QUE
x PREND_LA_VALEUR x+precision
FIN_TANT_QUE
inf PREND_LA_VALEUR x-precision
AFFICHER inf
AFFICHER " < solution <= "
AFFICHER x
POUR h ALLANT_DE 1 A 8
DEBUT_POUR
precision PREND_LA_VALEUR precision/10
x PREND_LA_VALEUR a
TANT_QUE (F1(a)*F1(x)>0) FAIRE
DEBUT_TANT_QUE
x PREND_LA_VALEUR x+precision
FIN_TANT_QUE
inf PREND_LA_VALEUR x-precision
AFFICHER inf
AFFICHER " < solution <= "
AFFICHER x
FIN_POUR
FIN_ALGORITHME
a EST_DU_TYPE NOMBRE
precision EST_DU_TYPE NOMBRE
x EST_DU_TYPE NOMBRE
inf EST_DU_TYPE NOMBRE
h EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE a
LIRE precision tout dépend de ce que veut dire ce "precision" ...
x PREND_LA_VALEUR a
TANT_QUE (F1(a)*F1(x)>0) FAIRE |
DEBUT_TANT_QUE |
x PREND_LA_VALEUR x+precision |
FIN_TANT_QUE |
inf PREND_LA_VALEUR x-precision | partie inutile et ruinant tout le principe de ce qu'on veut faire
AFFICHER inf |
AFFICHER " < solution <= " |
AFFICHER x |
POUR h ALLANT_DE 1 A 8 donc toujours 8 chiffres
DEBUT_POUR
precision PREND_LA_VALEUR precision/10 faux. ne pas confondre le pas courant et la précision finale
x PREND_LA_VALEUR a faux. repartir à chaque fois de a est aberrant il faut poursuivre à partir du dernier encadrement trouvé
TANT_QUE (F1(a)*F1(x)>0) FAIRE voire note infra
DEBUT_TANT_QUE
x PREND_LA_VALEUR x+precision faux même raison (pas et précision)
FIN_TANT_QUE
inf PREND_LA_VALEUR x-precision | mal placé selon ce qu'on veut faire
AFFICHER inf |
AFFICHER " < solution <= " |
AFFICHER x |
FIN_POUR
FIN_ALGORITHME
tel que tu l'as écrit ça ne marche que si on a entré précision = 1 et rien d'autre
et donc le LIRE précision est totalement faux
et de plus donne une liste d'encadrements successifs
sinon il faut déplacer les "afficher" à la fin de tout (après le fin pour)
plus quelques petits détails de principe "aux limites" (les boucles à un près, ce qui t'a forcé à calculer un "inf" inutile)
qui t'empêcheraient d'enchainer les boucles sur x "sainement" :
on a imaginé la méthode avec
deux valeurs successives du tableau de valeurs sont de signe différent
toi avec ton tant que F1(a)*F1(x) >0 tu considère le premier terme du tableau par rapport au terme courant
le plus logique serait de considérer F1(x)*F1(x+p) comme condition du tant que ... (deux valeurs successives)
on a alors sans besoin de "revenir en arrière" la solution entre x et x + p au sortir du tant que
VARIABLES
a EST_DU_TYPE NOMBRE
p EST_DU_TYPE NOMBRE
x EST_DU_TYPE NOMBRE
n EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE a
LIRE p
x PREND_LA_VALEUR a
POUR n ALLANT_DE pow(1, 0) A pow(1, -8)
DEBUT_POUR
TANT_QUE (F1(x)*F1(x+p)>0) FAIRE
DEBUT_TANT_QUE
x PREND_LA_VALEUR x+p
FIN_TANT_QUE
AFFICHER x
AFFICHER " < solution <="
AFFICHER x+p
FIN_POUR
FIN_ALGORITHME
Et celui-ci? 
POUR est une boucle sur des nombres entiers et rien d'autre, qui à chaque boucle est augmenté toujours de 1 et rien d'autre
pour gérer autre chose que des nombres entiers il faut le faire avec une boucle tant que
que veut dire "POUR n ALLANT_DE 1 A 0.00000001" ???
(vu que les pow() de valeurs constantes on peut les écrire exactement comme ça, ça ne change rien)
en fait une telle boucle ne sera jamais exécutée car la valeur initiale 1 est déja supérieure à la valeur finale (0.00000001) !
avec une boucle pour ce serait par exemple
Lire n (nombre de chiffres à trouver)
pour k de 0 à n (vu que on doit faire la boucle pour un pas de 100=1 à 10-n
k n'est pas le pas, c'est un compteur)
etc
d'autre part la gestion du pas est toujours défectueuse :
le pas est ici constant et toujours égal à la valeur entrée p
alors que à chaque exécution de la boucle la plus externe (pour), le pas p devrait être divisé par 10
c'est le principe de base de cette méthode par balayages successifs.
et de toute façon le pas initial (la valeur entrée) devrait être disons 1 (la plus grosse valeur de départ du pas de la table)
AFFICHER x+p est sans doute un AFFICHERCALCUL n'est-ce pas ?
courage, c'est "presque bon"
il ne reste que quelques petits détails :
- la boucle pour (sur un nombre entier) ou la remplacer par un tant que
- cette gestion du pas qui doit prendre successivement les valeurs 1, 1/10, 1/100, ... jusqu'à 1/10n
la modification n'est pas compliquée : chaque nouvelle valeur de ce pas est la valeur précédente divisée par 10 !
(et c'est pas l'utilisateur qui fait cette division, c'est le programme)
VARIABLES
a EST_DU_TYPE NOMBRE
p EST_DU_TYPE NOMBRE
x EST_DU_TYPE NOMBRE
n EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE a
LIRE p
LIRE n
POUR n ALLANT_DE 0 A 8
DEBUT_POUR
p PREND_LA_VALEUR p/pow(10,n)
x PREND_LA_VALEUR a
TANT_QUE (F1(x)*F1(x+p)>0) FAIRE
DEBUT_TANT_QUE
x PREND_LA_VALEUR x+p
FIN_TANT_QUE
AFFICHER x
AFFICHER " < solution <="
AFFICHERCALCUL x+p
a PREND_LA_VALEUR x
n PREND_LA_VALEUR 0
FIN_POUR
FIN_ALGORITHME
A la fin n reprend la valeur zero afin d'obenir la décimales suivante car après 0, il faut que n reste à 1
???
il fallait juste modifier quelques "virgules", pas tout casser et remplacer ce qui marchait par quelque chose qui ne marche plus !
LIRE n
suivi de POUR n
est absurde : la valeur lue est immédiatement détruite par l'instruction pour et remplacée par 0
modifier dans une boucle pour la variable de la boucle pour est simplement courir à sa perte !!!
ton programme ne se termine jamais. vu que n restera bloqué éternellement à la valeur 1 (ta réinitialisation fautive de n à 0 à la fin suivie de l'incrémentation de 1 par l'instruction pour)
ta gestion de p est toujours mauvaise : tu fais trop compliqué
d'une boucle pour à l'autre on fait juste une simple division de p par 10 et c'est tout
tes échanges de a et de x sont tout bonnement inutiles
LIRE x
et plus aucune initialisation de a et de x autre que cette valeur là
ensuite x progresse par l'algorithme sans aucune bidouille.
un exemple qui marche :
VARIABLES
x EST_DU_TYPE NOMBRE
p EST_DU_TYPE NOMBRE
n EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
AFFICHER "valeur initiale de x "
LIRE x
// le pas initial est généralement de 1, mais pourrait être plus grand
AFFICHER "pas initial "
LIRE p
AFFICHER "nombre de chiffres après la virgule"
LIRE n
TANT_QUE (p >= pow(10,-n)) FAIRE
DEBUT_TANT_QUE
TANT_QUE (F1(x)*F1(x+p)>0) FAIRE
DEBUT_TANT_QUE
x PREND_LA_VALEUR x+p
FIN_TANT_QUE
// ici la solution est entre x et x+p
AFFICHER x
AFFICHER " < x <= "
AFFICHERCALCUL* x+p
// précision 10 fois plus petite et on continue à partir de là, de cette valeur de x là
p PREND_LA_VALEUR p/10
FIN_TANT_QUE
// le dernier encadrement affiché est à la précision demandée
FIN_ALGORITHME
tu vois que tu n'en étais pas loin du tout
juste que tu t'égares avec ta gestion du pas et de x à faire des trucs bien trop compliqués !!
(et l'incompréhensuion du mécanisme des boucles POUR)
Nota :
on peut faire aussi avec une boucle pour, mais ce sera un "pour k de 0 à n"
et cela impose un p initial toujours de 1 pour avoir le nombre de boucles qui correspond au nombre de chiffres après la virgule.
Nota : Algobox effectue des arrondis intempestifs sur ses calculs de sorte que la précision de 8 chiffres après la virgule est inaccessible, on ne pourra en pratique pas dépasser 6 chiffres.
pour avoir les 8 (voire 12 chiffres) il faut faire ça avec autre chose que Algobox. (en JavaScript ou autres par exemple)
et gérer soi-même les arrondis parce que en interne 1/10 n'est pas une valeur qui tombe juste en binaire
il risque donc d'afficher 0.5 comme en fait 0.499999999999998 par exemple
ou faire des bidouilles immondes en Algobox pour inhiber ces histoires d'arrondis
VARIABLES
p EST_DU_TYPE NOMBRE
x EST_DU_TYPE NOMBRE
n EST_DU_TYPE NOMBRE
k EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE x
LIRE p
LIRE n
POUR k ALLANT_DE 0 A n
DEBUT_POUR
TANT_QUE (F1(x)*F1(x+p)>0) FAIRE
DEBUT_TANT_QUE
x PREND_LA_VALEUR x+p
FIN_TANT_QUE
AFFICHER x
AFFICHER " < solution <="
AFFICHERCALCUL* x+p
p PREND_LA_VALEUR p/10
FIN_POUR
FIN_ALGORITHME
C'était donc ça?
oui. ou presque.
ça ne marche que si on entre p = 1 (déja signalé)
corriger ça avec une boucle pour est inutilement compliqué par rapport à la boucle "tant que" que je proposais
avec la boucle pour, demander la valeur initiale du pas est donc inutile
une simple affectation
p PREND_LA_VALEUR 1
suffit à la place
nota : Algobox effectue des arrondis intempestifs qui rendent illusoire une demande de 8 chiffres après la virgule, il faut se contenter de moins selon les valeurs de la solution.
exemple :
avec ma fonction x3 - 2x2 - 5 au lieu de la tienne on obtient :
2 < x <= 3
2.6 < x <= 2.7
2.69 < x <= 2.7
2.69 < x <= 2.691
2.6906 < x <= 2.6907
2.69064 < x <= 2.69065
2.690647 < x <= 2.690648
2.6906474 < x <= 2.6906475
2.6906474 < x <= 2.6906475 arrondi intempestif du 8ème chiffre, donc faux
alors qu'on devrait (voudrait) obtenir, avec un autre langage que Algobox :
2 < x <= 3
2.6 < x <= 2.7
2.69 < x <= 2.70
2.690 < x <= 2.691
2.6906 < x <= 2.6907
2.69064 < x <= 2.69065
2.690647 < x <= 2.690648
2.6906474 < x <= 2.6906475
2.69064744 < x <= 2.69064745 8ème chiffre correct (pas arrondi)
D'accord.
Mais puisqu'on demande de trouver l'arrondi par défaut à 10^-8 près de la solution
j'ai pensé à cet algorithme:
VARIABLES
a EST_DU_TYPE NOMBRE
m EST_DU_TYPE NOMBRE
p EST_DU_TYPE NOMBRE
n EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE a
LIRE m
p PREND_LA_VALEUR 1
n PREND_LA_VALEUR 0
TANT_QUE (n<m) FAIRE
DEBUT_TANT_QUE
TANT_QUE (F1(a)* F1(a+p)>0) FAIRE
DEBUT_TANT_QUE
a PREND_LA_VALEUR a+p
FIN_TANT_QUE
p PREND_LA_VALEUR p/10
n PREND_LA_VALEUR n+1
AFFICHER a
FIN_TANT_QUE
FIN_ALGORITHME
tu as refabriqué une boucle "pour" avec une boucle "tant que"
ce qui est inutilement compliqué.
et en plus tu l'as mal traduite
il n'y a pas qu'une seule façon d'écrire cet algorithme
mais mélanger plusieurs "façons" sème la pagaille et donne des trucs faux.
avec ta boucle "pour fabriquée à la main"
il fallait écrire
n PREND_LA_VALEUR 0
TANT_QUE (n<=m) FAIRE 
, m compris, et pas <
DEBUT_TANT_QUE
[...autre boucle etc]
n PREND_LA_VALEUR n+1
FIN_TANT_QUE
ceci étant alors totalement équivalent à (plus simple à écrire)
POUR n ALLANT_DE 0 A m (une boucle "pour" est bornes incluses)
DEBUT_POUR
[...autre boucle etc]
FIN_POUR
que tu avais écrit à 12:47
il faut bien exécuter m+1 boucles (de 0 à m inclus) puisque on va faire les calculs de p = 1 (100) à 10-m inclus
il suffisait donc exclusivement sans rien toucher du tout au reste de remplacer la seule ligne
LIRE p
par :
p PREND_LA_VALEUR 1
exactement au même endroit
pour obtenir un algorithme impeccable, suite à ma remarque sur la valeur initial de de p, tout le reste étant bon par ailleurs.
plutôt que de revenir sur une autre méthode (avec un tant que) et ajouter une erreur qu'il n'y avait pas avant...
le remplacement de la boucle pour par un tant_que que j'évoquais concerne une autre méthode :
un tant_que sur la valeur de p, pas sur un compteur ...
en fait ton dernier algorithme est la traduction de celui de zygomatique sur l'autre forum (et il est faux, mais il n'arrête pas de modifier son message, alors va savoir ce qu'il en est maintenant)
tu sembles d'ailleurs bien t'amuser à recopier des messages d'un forum vers l'autre....
Annuler
connectez vous