Marche aléatoire d'une tortue : article mathématice


Voici un nouvel article pour la revue MATHÉMATICE concernant l'exercice 4 du
sujet du Bac S Antilles de septembre 2013.

Une nouvelle fois, un sujet de Bac reproduit les calculs d'un tableur et on ne peut que le regretter...

N'utilisez jamais excel pour faire des calculs !!

Regardez le massacre:

IMAGE(http://download.tuxfamily.org/tehessinmath/les_images/excel.png)

Un traitement introduisant des coordonnées cartésiennes est proposé alors qu'on peut l'éviter : quand on marche sur un pont, on ne pense pas forcément à ses coordonnées GPS...

Il suffit de compter ses pas en distingant ceux faits vers la gauche, la droite ou tout droit.

Trajet de la tortue avec xcas

On peut commencer par faire traverser le pont à une tortue.
Elle connaît les instructions avance(distance), tourne_droite(angle) et tourne_gauche(angle) dont les appellations parlent d'elles-mêmes.

On va également faire dessiner et colorier le pont par la tortue, la moitié gauche étant jaune et la droite verte.

On utilise une boucle « pour » plutôt que « tant que » : cela évite les risques de boucle infinie quand le test est une égalité même si le risque est nul ici car on ne travaille que sur des entiers de 1 à 10... On reste aussi efficace car retourne "Plouf !" nous fait sortir du programme.

Giac-XCAS
robot():={
  local Pas,ecart,u,h;
  Pas  := 0  ;
  ecart:= 0  ;
  u    := 30 ; // l'unité de longueur
  // le dessin du pont 
  crayon jaune; rectangle_plein(10*u,u),jaune;
  pas_de_cote(-u);
  crayon vert; rectangle_plein(10*u,u),jaune; crayon bleu;
  pas_de_cote(u);
  
  pour Pas de 1 jusque 10 faire
    h := -1 + hasard(3); // un entier entre -1 et 1
    ecart := h + ecart; // on s'écarte de h sur le côté
    si abs(ecart) > 1 alors 
      retourne "Plouf !" 
    sinon
      avance((1 - abs(h)) * u); // on s'écarte seulement si h est non nul 
      tourne_droite(45 * h);
      avance(abs(h) * u * sqrt(2)); // on avance d'une diagonale
      tourne_gauche(45 * h); // on remet la tortue dans l'axe
    fsi;
  fpour;
  retourne("Gagné !")
}:;

Voici un trajet de tortue réussi:

IMAGE(http://download.tuxfamily.org/tehessinmath/les_images/tortue_gagne.png)

et un plongeon:

IMAGE(http://download.tuxfamily.org/tehessinmath/les_images/tortue_perd.png)

On peut simuler un grand nombre de trajets pour calculer la fréquence de succès:

Giac-XCAS
parcours(Ecart,Pas):={
  si abs(Ecart) > 1 alors retourne(0.0);
  sinon si Pas == 10 alors retourne(1.0);
        sinon parcours((Ecart + (-1 + hasard(3))), Pas + 1)
        fsi;
  fsi      
}:;

On trouve alors une fréquence d'environ 13,7%

Giac-XCAS
moyenne([seq(parcours(0,0) , k = 1..2^(18))]) 

On peut modifier légèrement le script précédent pour avoir le nombre moyen de pas (environ 5,3):

Giac-XCAS
parcours(Ecart,Pas):={
  si abs(Ecart) > 1 alors retourne(evalf(Pas));
  sinon si Pas == 10 alors retourne(10.0);
        sinon parcours((Ecart -1 + hasard(3)), Pas + 1)
        fsi;
  fsi      
}:;

Avec Python

Même principe:

Python
def parcours(ecart,pas):
    if abs(ecart) > 1:
        return 0
    elif pas == 10:
        return 1
    else:
        return parcours(ecart + randint(-1,2), pas + 1)

On vérifie en calculant les probabilités:

Python
def p(n):
    if n == 0:
        return [0,1,0]
    else:
        [a,b,c] = p(n - 1)
        return [(a + b) / 3, (a + b + c) / 3, (b + c) / 3]

Ce qui donne:

Python
In [65]: p(10)
Out[65]: [0.04027163880844722, 0.056952700299751045, 0.04027163880844722]
 
In [66]: sum(p(10))
Out[66]: 0.13749597791664547

Avec c

C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
// on utilise rand pour obtenir un entier dans [a,b[ avec une loi -presque- uniforme 
int hasard(int a, int b){ 
    return rand()%(b-a) + a; 
}
 
// la fonction de parcours habituelle : on tombe ou on arrête ou on continue en incrémentant nos compteurs de mouvement 
double parcours(int ecart, int pas){
  if(abs(ecart) > 1)
    {return 0.0;} // le robot est tombé : le parcours vaut 0
  else
    {if (pas == 10)
       {return 1.0;} // on a traversé : le parcours vaut 1
     else
       {return parcours(ecart + hasard(-1,2), pas + 1);}
    }
}
 
// la procédure principale qui compte les parcours réussis 
double main(void){
  int i;
  int s = 0.0; 
  srand(time(NULL)); // la graine aléatoire est le temps machine
  for(i = 0; i < 10000000; i++){
    s = s + parcours(0,0); // on incrémente s par les parcours réussis
  }
  printf("Fréquence de réussite  : %f\n ",s / 100000.0);
  return 0;
}

Ce qui donne instantanément pour dix millions de trajets:

Bash
$ gcc -o robot robot.c
$ ./robot 
Fréquence de réussite  : 13.748420