Un marcheur un peu égaré part de l'origine O et peut se déplacer soit vers la gauche, soit vers la droite, avec une même probabilité à chaque instant t . Il s'agit d'une marche aléatoire.
Quel algorithme permet à l'utilisateur de saisir un entier t et d'indiquer où se trouve le marcheur à l'instant t ?
On importe le module \verb/random/ pour utiliser la fonction \verb# randint #. Elle prend deux arguments entiers a et b et renvoie un entier entre ces deux nombres.
Si l'on tire un 0 , alors on se déplace vers la gauche en retirant une unité à la variable x , sinon on ajoute une unité.
On doit ensuite faire attention au symbole « : » à la fin d'une instruction, et l'entier ne peut être obtenu avec l'instruction \verb # t = int(compute("Que vaut t :")) # .
Ainsi, l'algorithme peut s'écrire :
from random import *
x = 0
t = int(input("Que vaut t :"))
i = 0
while i < t :
k = randint(0 , 1)
if k = = 0 :
x -= 1
else :
x += 1
i += 1
print("x = " , x)
Peut-on revenir à l'origine si t est impair ?
Si le marcheur revient au point de départ, alors le nombre d'étapes nécessaires est divisible par 2.
On ne peut donc pas revenir à l'origine si t est impair.
Quel algorithme permet de générer une marche aléatoire et d'indiquer le premier instant t pour lequel le marcheur revient à l'origine ?
Pour générer une marche aléatoire, on incrémente à chaque étape d'une boucle infinie la valeur de la variable x de 1 si on se déplace vers la droite, de -1 sinon.
Dès que x vaut 0 , on sort de la boucle infinie avec le mot-clé \verb/break/.
L'algorithme qui convient est donc :
from random import *
x = 0
t = 0
while True:
k = randint(0 , 1)
if k = = 0 :
x -= 1
else :
x += 1
if x = = 0 :
break
t += 1
print("t = " , t)