Crédits

Toute la structure html/css/js et une partie du contenu ont été réalisés par Nicolas Buyle-Bodin professeur au lycée Lacassagne, avec l'aide de Jean-Manuel Mény, professeur au lycée de la plaine de l'Ain. Ils ont travaillé pendant plusieurs centaines d'heures pour créer un site de formation à destination des enseignants du secondaire de l'académie de Lyon d'une grande qualité visible sur le portail Mathématiques du site académique. Ils ont eu la gentillesse de placer leur code source sous licence Creative Commons BY-NC-SA Respect de la Paternité - Pas d'utilisation commerciale - Partage des conditions initiales à l'identique..

Nous les en remercions chaleureusement.

Approximation de $\sqrt{2}$ par balayage

On considère la fonction $f:x \mapsto x^2$ définie sur l'intervalle $[1;2]$.

Dresser le tableau de variations de la fonction $f$ sur l'intervalle $[1;2]$ en précisant son minimum et son maximum sur l'intervalle.
Ce tableau vous semble-t-il cohérent avec la proposition suivante : l'équation $f(x)=2$ possède une unique solution sur l'intervalle $[1;2]$ et on note$\sqrt{2}$ cette solution ?
La fonction Python ci-dessous, retourne un couple de valeurs qui peut être affiché avec print ou récupéré dans un couple de variables :
```
def double_et_suivant(n):
    return (2 * n, 2 * n + 1)
    
print(double_et_suivant(2))
(a, b) = double_et_suivant(502)
print(a, b)
        
```
```
(4, 5)
(1004, 1005)
```
Écrire une fonction balayage(epsilon) qui retourne un couple $(a, b)$, tel que $a$ et $b$ forment un encadrement de $\sqrt{2}$ d'amplitude epsilon : $a \leqslant \sqrt{2} \leqslant b$ et $b - a = \text{epsilon}$.
Par exemple print(balayage(0.1)) doit afficher :
```
(1.4, 1.5)
```

Solution Questions 1 et 2
Solution Question 3

$f:x \mapsto x^2$ est strictement croissante sur l'intervalle $[1;2]$, on a $f(1) < 2 < f(2)$ et $f$ est continue sur $[1;2]$, c'est-à-dire que sa courbe ne comporte pas de sauts entre deux points successifs. D'après un corollaire du théorème des valeurs intermédiaires, qui sera présenté en classe de Terminale, l'équation $f(x)=2$ possède donc une unique solution sur l'intervalle $[1;2]$. Cette solution est usuellement notée $\sqrt{2}$.


def balayage(epsilon):
    x = 1
    while x ** 2 < 2:
        x = x + epsilon
    return (x - epsilon, x)

print(balayage(0.1))

Le juste prix

Dans le jeu du Juste prix, l'animateur présente un objet et donne une fourchette de prix. Le joueur doit deviner le prix de l'objet en un nombre maximum de propositions. A chaque proposition du joueur, l'animateur précise si le prix proposé est supérieur ou inférieur au prix réel.

On veut écrire une fonction juste_prix(prixSup) qui respecte la spécification suivante :
- elle doit prendre comme paramètre un prix maximum ;
- elle doit simuler une partie de Juste prix ;
- elle ne doit pas afficher le résultat mais retourner un couple constitué du juste prix et du nombre de propositions soumises, qui peut ensuite être utilisé pour un affichage avec un print.
La machine ne fait qu'exécuter les instructions du programme donc elle peut alterner entres les positions d'animateur et de joueur ! L'animateur choisit d'abord le prix entier qu'il faut deviner entre 0 et prixSup euros, à l'aide de la fonction randint de la bibliothèque random. Dans cette question le nombre de propositions n'est pas limité.
- Compléter la fonction juste_prix(prixSup) pour qu'elle respecte la spécification ci-dessus, en choisissant une stratégie qui soumet automatiquement la proposition qui semble la meilleure pour le joueur.
- Dans cette question, on considère le cas d'une borne supérieure de prix de 100 euros. Peut-on être sûr que la fonction déterminera le juste prix en un nombre fini d'essais ? Si oui, peut-on déterminer le nombre maximum de propositions ?

from random import randint

def juste_prix(prixSup):
    prix = randint(0, prixSup)  #prix qu'il faut deviner
    prixInf = 0                 #borne inférieure de l'intervalle contenant le prix
    proposition = (prixInf + prixSup)//2             
    n = 1                       #nombre de propositions
    while proposition != prix:
        #à compléter
        n = n + 1
    return (prix, n)
                        
#Exemple d'exécution pour prixSup = 100
(prix, n) = juste_prix(100)
print("Bravo ! Vous avez deviné le juste prix", prix, " en ", n, " propositions.")

Modifier la fonction précédente en juste_prix2(prixSup, nmax), qui prend comme deuxième paramètre un nombre maximum de propositions nmax. On adaptera les valeurs que la fonction doit retourner pour que l'affichage du résultat du jeu puisse être effectué avec un print en dehors de la fonction comme ci-dessous.
```
Bravo ! Vous avez deviné le juste prix 18  en  4  propositions.
```
ou
```
Vous avez atteint le nombre maximum  4  de propositions sans deviner le juste prix  99 .
```
Écrire une fonction seuil_nbpropositions(prixSup) qui retourne le nombre maximum de propositions nécessaires pour déterminer un juste prix dans l'intervalle $[0;\text{prixSup}]$ avec l'algorithme des fonctions juste_prix et juste_prix2.

Solution Question 1
Solution Question 2
Solution Question 3


from random import randint

def juste_prix(prixSup):
    prix = randint(0, prixSup)  #prix qu'il faut deviner
    prixInf = 0                 #borne inférieure de l'intervalle contenant le prix
    proposition = (prixInf + prixSup)//2             
    n = 1                        #nombre de propositions
    while proposition != prix:
        if proposition < prix:
            prixInf = proposition + 1  #risque de boucle infini si prixInf = proposition , voyez-vous pourquoi ?
        else:
            prixSup = proposition - 1  #risque de boucle infini si prixSup = proposition , voyez-vous pourquoi ?
        proposition = (prixInf + prixSup)//2
        n = n + 1
    return (prix, n)

#Exemple d'exécution pour prixSup = 100
(prix, n) = juste_prix(100)
print("Bravo ! Vous avez deviné le juste prix", prix, " en ", n, " propositions.")

Prenons l'exemple d'une borne supérieure de prix de 100 euros. Le prix qu'il faut deviner appartient donc à l'intervalle $[0;100]$. A chaque tour de boucle, l'amplitude de l'intervalle de prix, prixSup - prixInf est divisée par 2.
- A l'entrée du tour de boucle numéro 1, l'amplitude est de $100 - 0=\frac{100}{2^{0}}$. A la fin du du tour de boucle numéro 1, l'amplitude est de $100 - 0=\frac{100}{2^{1}}$.
- A l'entrée du tour de boucle numéro 2, l'amplitude est de $\frac{100}{2^{1}}$. A la fin du du tour de boucle numéro 2, l'amplitude est de $100 - 0=\frac{100}{2^{2}}$.
- A l'entrée du tour de boucle numéro n, l'amplitude est de $\frac{100}{2^{n-1}}$. A la fin du du tour de boucle numéro 2, l'amplitude est de $100 - 0=\frac{100}{2^{n}}$.
Il existe nécessairement un numéro $n$ de tour de boucle tel que l'amplitude de l'intervalle de prix $\frac{100}{2^{n}}$ en sortie de boucle soit inférieure à $1$.
A la fin de ce tour de boucle, on a prixInf == proposition == prixSup. Comme on a toujours, prixInf <= prix <= prixSup, on a alors proposition == prix et la boucle se termine.

On a $2^{6}=64$ et $2^{7}=128$ donc la boucle s'exécutera au plus $7$ fois.

La fonction juste_prix2(prixSup, nmax) retourne un triplet constitué d'un booléen indiquant si le juste prix a été deviné, du juste prix et du nombre de propositions


from random import randint

def juste_prix2(prixSup, nmax):
    prix = randint(0, prixSup)  #prix qu'il faut deviner
    prixInf = 0                 #borne inférieure de l'intervalle contenant le prix
    proposition = (prixInf + prixSup)//2             
    n = 1                        #nombre de propositions
    while n < nmax and proposition != prix:
        if proposition < prix:
            prixInf = proposition + 1  #risque de boucle infini si prixInf = proposition , voyez-vous pourquoi ?
        else:
            prixSup = proposition - 1  #risque de boucle infini si prixSup = proposition , voyez-vous pourquoi ?
        proposition = (prixInf + prixSup)//2
        n = n + 1
    return (proposition == prix, prix, n)
    
        
#Exemple d'exécution pour prixSup = 100 et nmax = 8 qui est supérieur au nombre maximum de propositions nécessaires dans ce cas

(resultat, prix, n) = juste_prix2(100, 8)
if resultat:
    print("Bravo ! Vous avez deviné le juste prix", prix, " en ", n, " propositions.")
else:
    print("Vous avez atteint le nombre maximum ", n, " de propositions sans deviner le juste prix ", prix, ".")

On peut généraliser l'étude menée en question 1 sur l'exemple de prixSup égal à 100 où l'intervalle de recherche initial est $[0;100]$. Le nombre maximal de propositions est le plus petit entier $n$ tel que $\frac{\text{prixSup}}{2^{n}}<1 \Leftrightarrow \text{prixSup} < 2^{n}$.
On utilise un algorithme de seuil avec une boucle while. La condition d'entrée de boucle est la négation de la condition de sortie de boucle souhaitée qui est $\text{prixSup} < 2^{n}$. La condition d'entré de boucle est donc $\text{prixSup} ≥ 2^{n}$.
```
def seuil_nbpropositions(prixSup):
    n = 0
    puissance2 = 1
    while prixsup >= puissance2:
        n = n + 1
        puissance2 = 2 * puissance2
    return n
    
```

Approximation de $\sqrt{2}$ par dichotomie

On considère de nouveau la fonction $f:x \mapsto x^2$ définie sur l'intervalle $[1;2]$.
Nous allons adapter l'algorithme de recherche mis en place dans le jeu du Juste prix à la recherche d'un encadrement de l'unique solution $\sqrt{2}$ de l'équation $f(x)=2$.
Par souci de généralisation, on considère plutôt la fonction $g:x \mapsto f(x) - 2$ et on va rechercher l'unique solution dans l'intervalle $[1;2]$ de l'équation $g(x)=0$ qui est équivalente à $f(x)=2$.
La fonction $g$, les bornes $\text{a} = 1$ et $\text{b}=1$ de l'intervalle $[1;2]$ et une amplitude $\text{epsilon}$ ($0,01$ par exemple) peuvent alors être passés comme paramètre à la fonction ci-dessous, écrite en pseudo-code. Elle va retourner un couple de valeurs représentant la borne inférieure $\text{a}$ et la borne supérieure $\text{b}$ d'un encadrement de $\sqrt{2}$ qui est l'unique solution dans l'intervalle $[1;2]$ de l'équation $g(x)=0$. L'amplitude $\text{b}-\text{a}$ de l'encadrement retourné sera inférieure ou égale à $\text{epsilon}$.

L'algorithme est une recherche par dichotomie comme pour la recherche du juste prix dans l'exercice 2.

Recopier et compléter le tableau ci-dessous d'évolution des variables lors de l'exécution de l'appel de fonction $\text{dichotomie(g, 1, 2, 0.1)}$ .
$g$ est la fonction $g:x \mapsto x^2-2$. Les valeurs des variables seront prises juste avant l'entrée dans la boucle, puis à la fin de chaque tour de boucle.

Étape	$m$	Signe de $g(a) \times g(m)$	$a$	$b$	$b - a$
Initialisation	Rien	Rien	$1$	$2$	$1$
Premier tour de boucle	$1,5$	négatif	$1$	$1,5$	$0,5$
Second tour de boucle	.....	.....	.....	.....	.....

- Écrire en Python une fonction g(x) qui implémente la fonction mathématique $g:x \mapsto x^2-2$.
- Écrire en Python une fonction dichotomie(g, a, b, epsilon) qui implémente la fonction dont le pseudo-code est donné ci-dessus.
- Retrouver avec cette fonction l'encadrement de $\sqrt{2}$ d'amplitude inférieure ou égale à $0,1$ qui a été obtenu à la main en question 1.
- Comment peut-on utiliser les fonctions précédentes pour déterminer un encadrement de $\sqrt{2}$ d'amplitude inférieure ou égale à $0,01$ ? Combien de tours de boucles sont-ils alors effectués ?

Solution Question 1
Solution Question 2

Étape	$m$	Signe de $g(a) \times g(m)$	$a$	$b$	$b - a$
Initialisation	Rien	Rien	$1$	$2$	$1$
Premier tour de boucle	$1,5$	négatif	$1$	$1,5$	$0,5$
Second tour de boucle	$1,25$	positif	$1,25$	$1,5$	$0,25$
Troisième tour de boucle	$1,375$	positif	$1,375$	$1,5$	$0,125$
Quatrième tour de boucle	$1,4375$	négatif	$1,375$	$1,4375$	$0,03125$

Implémentation en Python de la fonction mathématique $g:x \mapsto x^{2}$ :
```
def g(x):
    return x ** 2 - 2
```

Implémentation en Python de la fonction $\text{dichotomie(g, a, b, epsilon)}$ :


def dichotomie(g, a, b, epsilon):    
    while b - a > epsilon:        
        m = (a + b)/2
        if g(a) * g(m) < 0:
            b = m
        else:
            a = m       
    return (a, b)

Pour obtenir un encadrement de $\sqrt{2}$ d'amplitude $0,1$, on peut saisir l'instruction :
```
print(dichotomie(g, 1, 2, 0.1))
```
L'encadrement affiché est bien :
```
(1.375, 1.4375)
```
Pour obtenir un encadrement de $\sqrt{2}$ d'amplitude $0,01$, on peut saisir l'instruction :
```
print(dichotomie(g, 1, 2, 0.01))
```
A chaque tour de boucle l'amplitude $b -a$ de l'intervalle $[a;b]$ contenant $\sqrt{2}$, est divisée par $2$.
- après $1$ tour de boucle, cette amplitude est de $\frac{1}{2^{1}}$ ;
- après $2$ tours de boucle, cette amplitude est de $\frac{1}{2^{2}}$ ;
- après $n$ tours de boucle, cette amplitude est de $\frac{1}{2^{n}}$ ;
La boucle s'arrête lorsque cette amplitude devient inférieure ou égale à epsilon. Par exemple, pour epsilon égal à $0,01$, il suffit de déterminer le plus entier $n$ tel que $\frac{1}{2^{n}} \leqslant 0,01 \Leftrightarrow 100 \leqslant 2^{n}$ et on trouve $n=7$ car $2^6=64$ et $2^7=128$.