Inscris-toi au e-camp "Héberge ton jeu Facebook sur Azure" de Microsoft vendredi 25 mai à 13h30 !

> Le Site du Zéro - Informatique

> Les forums

> Programmation

> Autres langages, outils et approches

> Multiplication inexplicable

> Lecture du sujet

Multiplication inexplicable

[Algorithmique]

Pour accéder à cette section
Connectez-vous !

Résolu Le problème de ce sujet a été résolu

Page 1

Auteur

Message

1 visiteur sur ce sujet (1 Anonyme)

Page 1

bouboudu21

# Posté le 03/08/2011 à 12:49:11

Le bonheur même !
Avatar

Ville : Fontaine-lès-dijon
Pays : France métropolitaine

Bonjour,

Je suis en train de lire le tutoriel « Algorithmique pour l'apprenti programmeur » et j'en suis au chapitre « Une classe d'algorithmes non naïfs : diviser pour mieux régner ». J'en suis au calcul approximatif de la racine de 2, dont un exemple est donné en php. Je l'ai codé en c++ et il fonctionne ; mais je ne comprends pas entièrement son fonctionnement : pour y a-t-il besoin de multiplier fonction(valeur_moyenne) par fonction(début) ?
Code : PHP

1	if (f($a) * f($m) < 0)

Pourquoi ne suffit-il pas de calculer fonction(valeur_moyenne) ?
Bien sûr, cette méthode ne fonctionne pas. Mais pourquoi ? Pourriez-vous m'expliquer l'utilité de cette multiplication ?

Merci d'avance,
bouboudu21

Édité le 03/08/2011 à 13:35:23 par bouboudu21

=======> L'invective ne déshonore que son auteur.

Si vous ne comprenez pas, cherchez dans le dico... :lol:

# Posté le 03/08/2011 à 12:49:11

bluestorm

# Posté le 03/08/2011 à 13:18:54

dont ask to ask
Avatar

Groupe : Anciens

Blog
Twitter

L'algorithme repose sur l'hypothèse que les deux bornes de l'intervalle de recherche donnent un résultat de signe opposé : par exemple f($a) est négatif, et f($b) positif, ou l'inverse. On se sert de ça pour savoir dans quelle moitié chercher ensuite (celle qui préserve cette différence de signes). Tester (f($a) * f($b) < 0) est une façon astucieuse de vérifier que les deux valeurs sont de signes opposés.

big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog

cbasile06

# Posté le 03/08/2011 à 13:20:11

Je pompe, donc je suis

Études : ENS Paris

Le test f($a) * f($m) < 0 sert en fait à regarder si f($a) et f($m) sont de même signe ou non.
C'est cela qui permet de déterminer l'intervalle où appliquer la prochaine itération de l'algorithme : en effet, il faut que l'évaluation de la fonction en chacune des deux bornes donne des résultats de signes différents pour être « sûr » qu'il y a un zéro de la fonction entre les deux (avec le théorème des valeurs intermédiaires, puisque notre fonction est continue).

Je reconnais que le tutoriel n'explique pas très clairement ce point.
Dans cette partie :
Citation : Tutoriel

On constate que f(0) est négatif et que f(2) est positif. Comme notre fonction est continue, l'équation f(x) = 0 possède nécessairement une solution entre 0 et 2. En utilisant la dichotomie, on peut réduire l'intervalle et donc améliorer la qualité de l'approximation.

Comme pour la recherche d'un mot dans le dictionnaire, on sélectionne une nouvelle valeur m positionnée au milieu de l'intervalle [a;b]. Si f(m) est positif, on peut en déduire que la solution est comprise dans l'intervalle [a;m]; sinon, elle se trouve dans l'intervalle [m; b].

Il faut bien se rendre compte que l'on choisit les intervalles de façon à ce que, dans un cas $f(a) < 0$ et $f(m) > 0$ , ou alors $f(m) < 0$ et $f(b) > 0$ : dans tous les cas, les valeurs prises par $f$ aux deux bornes de l'intervalle sont de signes opposés !
Cela aurait peut-être été plus clair en précisant « Si f(m) est positif, c'est-à-dire du signe de f(b), ... »

Tutoriels intéressants/utiles :
Des formules mathématiques sur le SdZ! - La programmation fonctionnelle avec Haskell
Algorithmique pour l'apprenti programmeur - Le typage - Compilez sous GNU/Linux !
Image utilisateur

bouboudu21

# Posté le 03/08/2011 à 13:35:04

Le bonheur même !
Avatar

Ville : Fontaine-lès-dijon
Pays : France métropolitaine

Bonjour,

Merci tout d'abord pour vos réponses, j'ai compris à quoi servait cette opération. Mais le code du tutoriel pourrait être un petit peu simplifié : pourquoi ne pas tester directement si fonction(valeur_moyenne) est supérieur ou inférieur à 0 ? Cela nous donne directement la « direction » à prendre (entre début et valeur_moyenne, ou entre valeur_moyenne et fin) :

Code : C++

if(fonction(valeurMoyenneActuelle) > 0)
{
      return trouverZero(debut, valeurMoyenneActuelle, precision);
}
else
{
      return trouverZero(valeurMoyenneActuelle, fin, precision);
}

Dans mon précédent mail, je dis que cette méthode ne fonctionne pas. Mais c'est parce que je ne m'étais pas rendu compte qu'il faut inverser « < » et « > ». Maintenant, cela fonctionne.

Merci encore pour vos réponses.
bouboudu21

Édité le 03/08/2011 à 13:36:01 par bouboudu21

=======> L'invective ne déshonore que son auteur.

Si vous ne comprenez pas, cherchez dans le dico... :lol: