Algorithmique Devoirs Mathématiques 1rS

[Ertin0x]

Bonjour,

Je bloque sur l'exercice de mon DM, il porte sur l'algorithmique et l'énoncé est :
Une marche aléatoire dans une ville est un déplacement aléatoire où la direction change à chaque intersection de façon aléatoire et indépendamment des mouvements précédents.

On parle de déplacement "sans mémoire" ou même de "marche de l'ivrogne".

Considérons un marcheur aléatoire à Manhattan, à chaque croisement de rue il prends une direction aléatoire.

Au bout de combien de temps va-t-il tomber à l'eau en moyenne ?

On va simplifier le problème, on supposera que Manhattan est un carré composé 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 et ouest et il avance d'une unité. Construire un algorithme avec Algobox ou Python qui simule une marche aléatoire jusqu'à ce que le marcheur sorte du carré et qui donne le nombre d'étape avant la sortie.

Pour cette question, j'ai réussi a faire un algorithme mais j'ai l'impression qu'il n'est pas juste :

https://gyazo.com/5f62b0bfb8b3c726c94ae062c021062f

2) Faire un deuxième algorithme qui simule 5000 marches aléatoire et qui calcule le temps moyens de sortie du carré.

Pour celui si je n'es pas compris comment faire j'ai beau retourné le problème dans tout les sens je ne vois pas comment faire pour obtenir la réponse.


Je vous remercie d'avance pour vos réponses. Cordialement.

[aviateur]

Bonjour
Ton algo c'est pas étonnant que tu aies un doute:
Il ne correspond en rien du tout à l'énoncé
Si (x.y) sont les coordonnées tu dois
ajouter à chaque étape l'un des 4 vecteurs
(1,0) (-1,0) (0,1) (0,-1) pris au hasard
Pour cela tu tire un nombre au hasard
de 1 à 4 et tu associes à chacun l'un des 4 vecteurs
Tu peux commencer à corriger ton algo
en fonction de cette remarque

[Black Jack]

Salut,

En supposant que les 4 coins du carré ont pour coordonnées : (0 ; 0) , (11 ; 0) , (0 ; 11) et (11 ; 11)

Pour 1 seul test :

- on impose l'abscisse = 0
- on impose l'ordonnée = 0
- on impose compteur = 0
- on impose eau = 0

- Boucle tant que eau = 0
{
- on incrémente le compteur
- On produit un entier aléatoire n allant de 0 à 3
- Si n = 0, on fait -1 sur l'abscisse
- Si n = 1, on fait +1 sur l'abscisse
- Si n = 2, on fait -1 sur l'ordonnée
- Si n = 3, on fait +1 sur l'ordonnée
- Si (abscisse < 0 ou abscisse > 11 ou ordonnée < 0 ou abscisse > 11), on impose eau = 1
}
- affichage de compteur
*********************

Pour les 5000 essais :

On impose compteur = 0
Boucle de 5000 fois
{
- on impose l'abscisse = 0
- on impose l'ordonnée = 0
- on impose eau = 0
- Boucle tant que eau = 0
{
- on incrémente le compteur
- On produit un entier aléatoire n allant de 0 à 3
- Si n = 0, on fait -1 sur l'abscisse
- Si n = 1, on fait +1 sur l'abscisse
- Si n = 2, on fait -1 sur l'ordonnée
- Si n = 3, on fait +1 sur l'ordonnée
- Si (abscisse < 0 ou abscisse > 11 ou ordonnée < 0 ou abscisse > 11), on impose eau = 1
}
}
Affiche le calcul (compteur/5000)
*********************

[Ertin0x]

Bonjour
Ton algo c'est pas étonnant que tu aies un doute:
Il ne correspond en rien du tout à l'énoncé
Si (x.y) sont les coordonnées tu dois
ajouter à chaque étape l'un des 4 vecteurs
(1,0) (-1,0) (0,1) (0,-1) pris au hasard
Pour cela tu tire un nombre au hasard
de 1 à 4 et tu associes à chacun l'un des 4 vecteurs
Tu peux commencer à corriger ton algo
en fonction de cette remarque

Je viens de faire cela mais maintenant AlgoBox ne veut pas m'afficher les nombres négatif c'est à dire que quand il doit faire -1 il fait +1.

https://gyazo.com/b0da737de704315c2ebd9982e346b1ea

[Ertin0x]

Salut,

En supposant que les 4 coins du carré ont pour coordonnées : (0 ; 0) , (11 ; 0) , (0 ; 11) et (11 ; 11)

Pour 1 seul test :

- on impose l'abscisse = 0
- on impose l'ordonnée = 0
- on impose compteur = 0
- on impose eau = 0

- Boucle tant que eau = 0
{
- on incrémente le compteur
- On produit un entier aléatoire n allant de 0 à 3
- Si n = 0, on fait -1 sur l'abscisse
- Si n = 1, on fait +1 sur l'abscisse
- Si n = 2, on fait -1 sur l'ordonnée
- Si n = 3, on fait +1 sur l'ordonnée
- Si (abscisse < 0 ou abscisse > 11 ou ordonnée < 0 ou abscisse > 11), on impose eau = 1
}
- affichage de compteur
*********************

Pour les 5000 essais :

On impose compteur = 0
Boucle de 5000 fois
{
- on impose l'abscisse = 0
- on impose l'ordonnée = 0
- on impose eau = 0
- Boucle tant que eau = 0
{
- on incrémente le compteur
- On produit un entier aléatoire n allant de 0 à 3
- Si n = 0, on fait -1 sur l'abscisse
- Si n = 1, on fait +1 sur l'abscisse
- Si n = 2, on fait -1 sur l'ordonnée
- Si n = 3, on fait +1 sur l'ordonnée
- Si (abscisse < 0 ou abscisse > 11 ou ordonnée < 0 ou abscisse > 11), on impose eau = 1
}
}
Affiche le calcul (compteur/5000)
*********************

Après avoir fait ce que vous avez fait, rien ne change l'algorithme ne m'affiche rien. https://gyazo.com/2a203fd4aae098a9ebbcfec3dda821fc

[Black Jack]

Code: Tout sélectionner

VARIABLES
  abscisse EST_DU_TYPE NOMBRE
  ordonnee EST_DU_TYPE NOMBRE
  compteur EST_DU_TYPE NOMBRE
  eau EST_DU_TYPE NOMBRE
  hasard EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  compteur PREND_LA_VALEUR 0
  abscisse PREND_LA_VALEUR 0
  ordonnee PREND_LA_VALEUR 0
  eau PREND_LA_VALEUR 0
    TANT_QUE (eau==0) FAIRE
      DEBUT_TANT_QUE
      compteur PREND_LA_VALEUR compteur + 1
      hasard PREND_LA_VALEUR ALGOBOX_ALEA_ENT(0,3)
      SI (hasard==0) ALORS
        DEBUT_SI
        abscisse PREND_LA_VALEUR abscisse - 1
        FIN_SI
      SI (hasard==1) ALORS
        DEBUT_SI
        abscisse PREND_LA_VALEUR abscisse + 1
        FIN_SI
      SI (hasard==2) ALORS
        DEBUT_SI
        ordonnee PREND_LA_VALEUR ordonnee - 1
        FIN_SI
      SI (hasard==3) ALORS
        DEBUT_SI
        ordonnee PREND_LA_VALEUR ordonnee + 1
        FIN_SI
      SI (abscisse < 0 OU abscisse > 11 ou ordonnee < 0 ou ordonnee > 11) ALORS
        DEBUT_SI
        eau PREND_LA_VALEUR 1
        FIN_SI
      FIN_TANT_QUE
  AFFICHER compteur
FIN_ALGORITHME

*****************
Essaie de comprendre et enjoliver si besoin est.

Remarque, lorsqu'on écrit un Si ..., on ne peut pas utiliser le signe =, il faut écrire ==

Ex :
SI (hasard==2) ALORS ...

Et pas
SI (hasard=2) ALORS ...

[Ertin0x]

Code: Tout sélectionner

VARIABLES
  abscisse EST_DU_TYPE NOMBRE
  ordonnee EST_DU_TYPE NOMBRE
  compteur EST_DU_TYPE NOMBRE
  eau EST_DU_TYPE NOMBRE
  hasard EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  compteur PREND_LA_VALEUR 0
  abscisse PREND_LA_VALEUR 0
  ordonnee PREND_LA_VALEUR 0
  eau PREND_LA_VALEUR 0
    TANT_QUE (eau==0) FAIRE
      DEBUT_TANT_QUE
      compteur PREND_LA_VALEUR compteur + 1
      hasard PREND_LA_VALEUR ALGOBOX_ALEA_ENT(0,3)
      SI (hasard==0) ALORS
        DEBUT_SI
        abscisse PREND_LA_VALEUR abscisse - 1
        FIN_SI
      SI (hasard==1) ALORS
        DEBUT_SI
        abscisse PREND_LA_VALEUR abscisse + 1
        FIN_SI
      SI (hasard==2) ALORS
        DEBUT_SI
        ordonnee PREND_LA_VALEUR ordonnee - 1
        FIN_SI
      SI (hasard==3) ALORS
        DEBUT_SI
        ordonnee PREND_LA_VALEUR ordonnee + 1
        FIN_SI
      SI (abscisse < 0 OU abscisse > 11 ou ordonnee < 0 ou ordonnee > 11) ALORS
        DEBUT_SI
        eau PREND_LA_VALEUR 1
        FIN_SI
      FIN_TANT_QUE
  AFFICHER compteur
FIN_ALGORITHME

*****************
Essaie de comprendre et enjoliver si besoin est.

Remarque, lorsqu'on écrit un Si ..., on ne peut pas utiliser le signe =, il faut écrire ==

Ex :
SI (hasard==2) ALORS ...

Et pas
SI (hasard=2) ALORS ...

Je vous remercie j'ai pu comprendre d'où venait l'erreur et la corriger et j'ai pu faire le deuxième algorithme sans problème un grand merci à vous !