J'aimerais savoir si quelqu'un pourrait m'aider pour un problème d'algorithme. Je dois réaliser un algorithme dans un DM et je bloque complètement!
Voici le sujet:
Une marche aléatoire dans une ville est un déplacement où la direction change à chaque intersection de façon aléatoire et indépendamment des mouvements précédents.
Considérons un marcheur aléatoire à Manhattan, à chaque croisement de rue il prend une direction aléatoire.
Au bout de combien de temps va-t-il tomber à l'eau en moyenne?
On supposera que Manhattan et un carré de 11 rues est-ouest et 11 rues nord-sud
1) Le marcheur démarre du point O de coordonnées (0 ; 0).
A chaque étape il prend une direction aléatoire entre nord, sud, est ou ouest et il avance d'une unité. Construire un algorithme avec Algobox qui simule une marche alétoire jusqu'à ce que le marcheur sorte du carré et qui donne le nombre d'étape avant la sortie.
Merci pour toutes éventuelles réponses
***Forum modifié en fonction du profil***
Bonjour, lance toi et propose quelque chose. ça n'est pas très compliqué.
le principe c'est :
Tant qu'il n'est pas tombé dans l'eau (c.a.d que les coordonnées sont entre -6 et 6)
je choisis au hasard s'il avance Nord Sud ou Est Ouest
je tire au hasard 1 ou -1 et j'incrémente les coordonnées dans cette direction,
j'incrémente le nombre d'étapes faites de 1
fin du tant_que
affichage du nombre d'étapes
Bonjour,
et pour que ce soit "en moyenne" il faudra répéter toute cette expérience un nombre suffisamment grand de fois ...
mais en faire déja une .
bein déja X et Y, la position du marcheur (coordonnées) à tout instant
et N le nombre de pas effectués à tout instant
les autres variables seront des variables pour le calcul (par exemple pour contenir des valeurs aléatoires etc) créées au besoin au fur et à mesure de l'avancement de l'écriture.
si ça se trouve même il n'y aura besoin d'en créer aucune autre, selon la façon dont on écrit tout ça.
pour répéter tout l'ensemble il faudra créer une grande boucle et un calcul de moyenne etc, donc d'autres variables
mais comme je le disais :
mais en faire déja une (seule marche aléatoire qui se termine par un "plouf" = ce qu'a dit Glapion)
Est-ce ce que l'on pourrait m'apporter une réponse concrète car après plusieurs essais je n'y arrive décidément pas!
Merci pour toute réponse
Essaye de te lancer et de proposer quelque chose, on corrigera. On t'a donné l'idée générale, tu n'as plus qu'à te battre avec la syntaxe.
Voici ce que j'ai déjà écrit sur Python:
from random import randint
P=(0,0)
i=randint(-1,1)
j=randint(-1,1)
P=(i,j)
k=1
while not P==(i,5) or P==(5,j) or P==(-5,j) or P==(i,-5):
i=i+randint(-1,1)
j=j+randint(-1,1)
P=(i,j)
k=k+1
print(P,k)
c'est un bon début ... mais ça ne va pas.
deux sortes d'erreurs :
erreurs de principe
erreurs de traduction et maladresses
analysons tout ça
au départ on part de (0,0) point barre
il n'y a rien du tout à tirer au sort :
P=(0,0)
i=randint(-1,1)
j=randint(-1,1)
P=(i,j)
k= 0
ensuite le "tant que"
ce n'est pas ça du tout
il ne s'agit pas de faire une égalité mais une inégalité
tant que le point est dans le carré
c'est à dire tant que son abscisse est entre -6 et +6 (bornes exclues)
ET son ordonnée est entre -6 et +6
on peut traduire ça en termes de coordonnées x et y
et cela va induire que l'idée d'utiliser un tuple P pour représenter la position est mauvaise (maladroite)
en effet on devra séparer les deux composantes pour faire ce test
autant utiliser directement deux variables simples x et y !! (ou i et j si tu veux les appeler comme ça)
et si jamais on a besoin par moment de faire une opération conjointe sur les deux, rien n'empêche d'écrire
(x, y) = (0, 0)
sans définir explicitement une variable tuple P.
et du coup les deux composantes resteront toujours accessibles en tant que x et y vu que ce tuple n'a pas d'existence réelle.
la condition du tant que s'écrira alors
tant que -6 < x < 6 ET -6 < y < 6
que l'on peut traduire par
tant que |x|<6 ET |y| < 6
i=i+randint(-1,1)
j=j+randint(-1,1)
randint(-1,1) va donner trois valeurs : -1 ou 0 ou +1
tu est donc amené en calculant comme ça à tirer au sort parmi 3*3 = 9 déplacements
et pas 4
tu inclus des déplacement illégaux dans le tas :
0 et 0 je reste sur place, interdit
1 et 1 je me déplace à la fois en x et en y c'est à dire en diagonale, interdit
etc
pourquoi ne pas traduire mot à mot ce que proposait Glapion ?
tirer à pile ou face (2 valeurs par randint(0,1) si on se déplace en x ou bien en y
ce "si" se traduira par un "si" (if ... else ... ) effectif dans le code
puis pour chaque cas tirer à pile ou face (deux valeurs seulement, un autre randint(0, 1), si on se déplace en + ou en -
pour éviter d'imbriquer des "si" dans les "si" on peut faire ce déplacement de façon calculatoire par une transformation affine simple qui au tirage 0 va faire correspondre -1 et au tirage 1 faire correspondre +1
P=(i,j) inutile vu que P n'a pas d'utilité réelle
vas y corrige...
un peu plus de réactivité permettrait d'avancer dans cet exercice
parce que une fois fait ça , ce n'est pas encore fini du tout ...
énoncé parti aux oubliettes, le demandeur semble se désintéresser de la question ...
histoire de ne pas faire totalement l'exo je l'ai fait en Algobox au lieu de Python, avec une méthode de calcul "originale" (sans "si")
la facilité de tracer sur l'écran graphique de Algobox me permettant de tracer (non demandé) un histogramme des longueurs avant la chute :
VARIABLES
DX EST_DU_TYPE LISTE
DY EST_DU_TYPE LISTE
X EST_DU_TYPE NOMBRE
Y EST_DU_TYPE NOMBRE
N EST_DU_TYPE NOMBRE
D EST_DU_TYPE NOMBRE
msg EST_DU_TYPE CHAINE
i EST_DU_TYPE NOMBRE
T EST_DU_TYPE LISTE
S EST_DU_TYPE NOMBRE
max EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
// initialisation des constantes de la table des déplacements
DX[0] PREND_LA_VALEUR -1:1:0:0
DY[0] PREND_LA_VALEUR 0:0:-1:1
// histogramme des longueurs, on se limite à une longueur max de 200
POUR i ALLANT_DE 0 A 200
DEBUT_POUR
T[i] PREND_LA_VALEUR 0
FIN_POUR
// cumul des longueurs (pour la moyenne)
S PREND_LA_VALEUR 0
// trajet maxi
max PREND_LA_VALEUR 0
// effectuer 1000 expériences
POUR i ALLANT_DE 1 A 1000
DEBUT_POUR
// un trajet
// point de départ
X PREND_LA_VALEUR 0
Y PREND_LA_VALEUR 0
N PREND_LA_VALEUR 0
TANT_QUE (abs(X)<6 ET abs(Y)<6) FAIRE
DEBUT_TANT_QUE
D PREND_LA_VALEUR ALGOBOX_ALEA_ENT(0,3)
// TRACER_SEGMENT_Rouge (X,Y)->(X+DX[D],Y+DY[D])
X PREND_LA_VALEUR X+DX[D]
Y PREND_LA_VALEUR Y+DY[D]
N PREND_LA_VALEUR N+1
// msg PREND_LA_VALEUR N+" : X="+X+", Y="+Y
// AFFICHER* msg
FIN_TANT_QUE
// fin du trajet
// cumul pour la moyenne
S PREND_LA_VALEUR S+N
// trajet maxi
SI (N>max) ALORS
DEBUT_SI
max PREND_LA_VALEUR N
FIN_SI
SI (N<=200) ALORS
DEBUT_SI
// cumul dans l'histogramme
// la longueur maxi est de 200
T[N] PREND_LA_VALEUR T[N]+1
FIN_SI
// recommencer nouveau trajet
FIN_POUR
// fin de l'expérience calcul de la moyenne
S PREND_LA_VALEUR S/1000
msg PREND_LA_VALEUR "moyenne = "+S+", longueur maxi = "+max
AFFICHER msg
POUR i ALLANT_DE 0 A 200
DEBUT_POUR
TRACER_SEGMENT_Rouge (i,0)->(i,T[i])
FIN_POUR
FIN_ALGORITHME
les instructions en commentaires (donc non exécutées) sont des reliquats de la mise au point de la boucle de base.
ce qui donne par exemple (les valeurs changent à chaque exécution bien entendu, vu que c'est aléatoire ...)
***Algorithme lancé***
moyenne = 42.603, longueur maxi = 217
***Algorithme terminé***
il semble que certaines longueurs de trajets ne soient jamais obtenues (les "trous" réguliers dans l'histogramme
phénomène à expliquer ...
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :