#!/usr/bin/env python
# coding: utf-8

# # Algorithme de dichotomie

# On considère la fonction $f:x\longmapsto 2x^3+3x^2-12x+5$ définie sur l'intervalle $[-4;2]$.
# 
# On en donne le tableau de variations ci-dessous :
# ![](http://lcs.allende.lyc14.ac-caen.fr/~lecluseo/tdv.jpg)

# ## Etude sur l'intervalle [1;2]

# ***1°/*** Justifier que l'équation $f(x)=0$ possède une solution ***unique*** sur l'intervalle $[1;2]$

# ***2°/*** On appelle $\alpha$ l'unique solution del'équation $f(x)=0$ sur l'intervalle $[1;2]$. 
# $a$ et $m$ sont deux réels de l'intervalle $[1;2]$.
# 
# Justifier que 
# - **si $f(a)\times f(m)<0$, alors $\alpha\in [a;m]$**
# - **si $f(a)\times f(m)>0$, alors $\alpha\notin [a;m]$**

# ***3°/*** On cherche à trouver une valeur approchée de l'équation $f(x)=0$. Pour ce faire, on considère l'algorithme suivant :
# 
# <PRE>
# A prend la valeur 1
# B prend la valeur 2
# M prend la valeur 1,5
# P=0,1
# Tant Que B-A>P
#     Si f(M)*f(A)>0
#         A prend la valeur M
#     Sinon
#         B prend la valeur M
#     M prend la valeur (A+B)/2
# Fin TantQue
# Afficher M
# </PRE>
# Compléter le tableau ci-dessous en donnant à chaque début de passage dans la boucle les valeurs demandées
# 
# En déduire la valeur retournée par l'algorithme.

# Variables | Etape 1 | Etape 2 | Etape 3 | Etape 4 | Etape 5
# ----------|---------|---------|---------|---------|--------
#     A     |  1      |         |         |         |        
#     B     |  2      |         |         |         |        
#     M     |         |         |         |         |        
#    f(A)   |         |         |         |         |        
#    f(M)   |         |         |         |         |        
#    B-A    |         |         |         |         |        
# 
# Quelle est la valeur retournée par l'algorithme ?
# 
# On pourra s'aider de la cellule Python ci-dessous pour faire tourner le coeur de l'algorithme à la main.

# In[ ]:


def f(x):
    # On programme la fonction f en Python
    return 2*x**3+3*x**2-12*x+5

A=1
B=2
M=(A+B)/2
print("M=",M)
print("f(A)=",f(A))
print("f(M)=",f(M))
print("B-A=",B-A)


# ## Bilan de la partie d'analyse de l'algorithme

# Cet algorithme met en œuvre la méthode dite de ***dichotomie*** qui consiste à **diviser par deux** la longueur de recherche en prenant le **milieu de l'intervalle** à chaque fois.
# 
# Chacun a, peut-être sans le savoir, déjà utilisé cet algorithme dans des jeux type "trouver le nombre entre 0 et 100 auquel je pense". On essaye 50, et si la personne répond plus petit, on essaye 25 et ainsi de suite jusqu'à trouver le nombre cherché.

# ## Programmation de l'algorithme en Python

# ***5°/*** Compléter le programme suivant et vérifier qu'il retourne bien la valeur escomptée

# In[ ]:


def f(x):
    # On programme la fonction f en Python
    return 2*x**3+3*x**2-12*x+5

A=1
B=2
M=1.5
P=0.1

while ... :
    if f(M)*f(A)>0 :
        ...
    else:
        ...
    M=...

print(M)


# ***6°/*** Modifier cet algorithme pour obtenir une valeur approchée de $\alpha$ à $10^{-4}$ près

# ## Etude sur l'intervalle [-2;1]

# ***7°/*** Justifier que l'équation $f(x)=0$ possède une solution ***unique*** $\beta$ sur l'intervalle $[-2;1]$

# ***8°/*** Copier/Coller puis modifier le programme de la partie précédente afin de déterminer une valeur approchée de $\beta$ à $10^{-4}$ près.

# In[ ]:


# Copier/Coller / Modifier votre programme


# ## Adapter l'algorithme

# ***7°/*** Justifier que l'équation $f(x)=10$ possède une solution ***unique*** $\gamma$ sur l'intervalle $[-2;1]$

# ***8°/*** Copier/Coller puis modifier le programme de la partie précédente afin de déterminer une valeur approchée de $\gamma$ à $10^{-4}$ près.

# In[ ]:


# Copier/Coller / Modifier votre programme


# Vous pouvez vous entraîner à refaire ces programmes sur la calculatrice. Cet algorithme de dichotomie est au programme du bac et tombe régulièrement.

# In[ ]: