slr56 Tout problème a sa solution. | Bonjour,
je suis en train de faire un algorithme dont le sujet est le suivant :
Une blatte ivre est placée sur un carré au milieu d'un sol carrelé dans une pièce rectangulaire de taille n*m carreaux. L'insecte erre (à la recherche d'un aspirine) aléatoirement de carreau en carreau dans la pièce. En supposant qu'il puisse aller du carreau courant sur chacun des huit carreaux environnants (à moins qu'il ne soit devant un mur) avec une probabilité équivalente, combien de temps lui faudra-t-il pour toucher chaque carreau sur le sol au moins une fois.
Ce problème est difficile à résoudre en utilisant les techniques de probabilité pure mais est beaucoup plus simple à résoudre avec un ordinateur. La technique employée est appelée simulation. Cette technique est largement utilisée dans l'industrie pour prévoir les flux de trafic, contrôle d'inventaire, etc. Le problème peut être simulé en utilisant la méthode suivante:
Un tableau count de n*m est utilisé pour représenter le nombre de fois que notre blatte atteint chaque carreau sur le sol. Toutes les cellules de ce tableau sont initialisée à zéro. La position de l'insecte sur le sol est représentée par les coordonnées (ibug, jbug). Les huit déplacements possibles de l'insecte sont représentés par les carreaux localisés dans:
(ibug + imove[k], jbug + jmove[k]) où 0=< k =< 7 et
imove[0] = -1 jmove[0] = 1
imove[1] = 0 jmove[1] = 1
imove[2] = 1 jmove[2] = 1
imove[3] = 1 jmove[3] = 0
imove[4] = 1 jmove[4] = -1
imove[5] = 0 jmove[5] = -1
imove[6] = -1 jmove[6] = -1
imove[7] = -1 jmove[7] = 0
Un déplacement aléatoire sur chacun des huit carreaux voisins est simulé en générant une valeur aléatoire pour k entre 0 et 7. Bien sûr, l'insecte ne peut pas aller en dehors de la pièce, donc les coordonnées traversant un mur doivent être ignorées, et une nouvelle valeur doit être générée. Chaque fois qu'un carreau est rencontré, le compte de ce carreau est incrémenté de sorte qu'une entrée non nulle montre le nombre de fois que l'insecte atterri sur le carreau. Quand chaque carreau a été traversé au moins une fois, l'expérience est terminée.
A/ Traiter toutes les valeurs de n et m, 2=< n =<40 et 2=< m =<20
Je décompose le programme en procédure.
Code :
- Debut
- procedure choix_taille
- procedure initialiser_tableau
- procedure incrementer_cases //procedure qui fait déplacer la blatte de manière aléatoire
- Fin
|
Code :
- procedure choix_taille
- entier : n, m
-
- Tant que m<2 ou m>20 faire
- afficher "saisissez la taille m du tableau:"
- entrer m
- Refaire
- Tant que n<2 ou >40 faire
- afficher "saisissez la taille n du tableau:"
- entrer n
- Refaire
- finproc
|
Code :
- procedure initialiser_tableau (dr Tab : tableau[2..n][2..m] d'entier)
- entier : i,n,j,m
- Pour i depuis 2 jusqu' à n faire
- Pour j depuis 2 jusqu'à m faire
- Tab[i,j]=0
- Finpour
- Finpour
- finproc
|
Code :
- procedure incrementer_cases
- entier : ibug, imove, jbug, jmove
- Comment récupérer la taille du tableau choisis par l'utilisateur dans la première procédure?
- Comment faire pour ne pas sortir du tableau?
- Comment faire déplacer la blatte de manière aléatoire tout en respectant les contraintes (les murs et la blatte se déplace sur 1 des 8 carreaux qui entoure sa position)?
- Comment parcourir le tableau jusqu'à ce que toutes les cellules aient une valeur supérieure à 0?
- Finproc
|
Merci à ceux qui m'aideront.
Cordialement.
Message édité par slr56 le 11-11-2008 à 17:24:50
|
