Exercice corrigéOn a programmé une fonction nommée hasard(), censée retourner le nombre 0 dans 50% des cas et le nombre 1 dans les autres cas.
Pour tester cette fonction, on utilise un programme basé sur l'algorithme suivant :
variable
...somme: nombre
début algorithme
...// initialisation
...somme ← 0
...// traitement
...pour i variant de 1 à 10 000
......somme ← somme + hasard()
...fin pour
...// sortie
...écrire "Le nombre 1 a été généré " somme " fois"
fin algorithme
- Expliquer le fonctionnement de l'algorithme ci-dessus.
- L'exécution de l'algorithme retourne le message "Le nombre 1 a été généré 4947 fois". Peut-on en déduire une anomalie pour la fonction hasard()?
Corrigé
-
- somme ← 0 ... : initialise la variable somme à 0.
- pour i variant de 1 à 10 000 ...: on effectue une boucle 10 000 fois.
- somme ← somme + hasard() ... : on ajoute le résultat de la fonction hasard() à la variable somme.
La variable somme ne sera pas modifiée si hasard() renvoie zéro. Elle sera incrémentée de 1 lorsque hasard() retourne 1.
La variable somme va donc compter le nombre de fois où la fonction hasard() retourne "1". - écrire "Le nombre 1 a été généré" somme "fois" : ... On affiche le résultat stocké dans la variable somme.
Si la fonction hasard() fonctionne correctement, le nombre affiché devrait avoisiner
10 000\times \frac{50}{100}=5 000 - On souhaite que la proportion de chiffres "1" retournés avoisine les 50% (soit une proportion de 0,5).
L'algorithme effectue 10 000 tests de la fonction hasard().
On a bien : 0,2 \leqslant 0,5 \leqslant 0,8 et 10 000\geqslant 25
L'intervalle de fluctuation au seuil de 0,95 est donc :
I=\left[0,5-\frac{1}{\sqrt{10000}} ; 0,5+\frac{1}{\sqrt{10000}}\right]=\left[0,49 ; 0,51\right]
Le message retourné par l'algorithme indique une proportion de résultats "1" égale à
\frac{4947}{10000}=0,4947.
Ce nombre appartient bien à l'intervalle I.
Aucune anomalie n'a donc été détectée par l'algorithme.