Inscription / Connexion Nouveau Sujet
Niveau première
Partager :

DM-algorithme

Posté par
Rem25
16-02-19 à 11:45

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***

DM-algorithme

Posté par
Glapion Moderateur
re : DM-algorithme 16-02-19 à 11:54

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

Posté par
mathafou Moderateur
re : DM-algorithme 16-02-19 à 12:06

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 .

Posté par
Rem25
re : DM-algorithme 16-02-19 à 15:44

Mais je ne vois pas quelles variables je dois introduire

Posté par
mathafou Moderateur
re : DM-algorithme 16-02-19 à 15:54

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)

Posté par
Rem25
re : DM-algorithme 27-02-19 à 12:16

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

Posté par
Glapion Moderateur
re : DM-algorithme 27-02-19 à 12:21

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.

Posté par
Rem25
re : DM-algorithme 27-02-19 à 16:19

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)

Posté par
mathafou Moderateur
re : DM-algorithme 28-02-19 à 12:03

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...

Posté par
mathafou Moderateur
re : DM-algorithme 01-03-19 à 11:31

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 ...

Posté par
mathafou Moderateur
re : DM-algorithme 02-03-19 à 18:47

é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 ...)

DM-algorithme

***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 ...

Posté par
Glapion Moderateur
re : DM-algorithme 03-03-19 à 11:32

superbe



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !