Markov ants

1. Introduction Markov ants
2. Solution expliquée
3. Tests et exécutions
4. solutions de la communauté

1. Introduction Markov ants

Une fourmi quitte sa fourmilière pour chercher de la nourriture, mais elle ne sait pas où aller, donc chaque seconde, elle se déplace aléatoirement de quelques centimètres directement vers le nord, le sud, l’est ou l’ouest avec une probabilité égale.

2. Solution expliquée

Pour cette exercice il nous suffit de générer des movement aléatoires sur la grille donné pui faire une moyenne du nombre de déplacement qu’a mis chacune des fourmies.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#define M 100

int main()
{
  //initialiser le random
    srand( time( NULL ) );

    int step;
    float generation=0;

    scanf("%d", &step);

    //hauteur et largeur
    int w;
    int h;
    // initialisation position de départ x,y et position actuelle
    int startpos_x=0,startpos_y=0;
    int pos_x=0,pos_y=0;
    char tab[M][M];

    scanf("%d%d", &w, &h); fgetc(stdin);

    //on range dans un tableau le paterne de la fourmilière et on initialise le point de départ
    for (int i = 0; i < h; i++) {
        char row[32];
        scanf("%[^\n]", row); fgetc(stdin);
        for(int x=0;x<w;x++)
        {
            tab[i][x]=row[x];
            if(row[x]=='A')
            {
                startpos_x=x;
                startpos_y=i;
            }
        }
    }

    // on fait la simulation 100000 afin d'avoir toujours la même moyenne et on additionne le nombre de déplacements de chaques fourmi
    float timeToLeave = 0.0;
    for(int u=0;u<100000;u++)
    {
        pos_y=startpos_y;
        pos_x=startpos_x;
        timeToLeave=0;
      while(pos_y<h && pos_x < w && pos_x>0 && pos_y>0 && tab[pos_y][pos_x]!='|' && tab[pos_y][pos_x]!='+' && tab[pos_y][pos_x]!='-')
      {
        switch(rand() % 4)
        {
        case 0:
            pos_y+=step*1;
            break;
        case 1:
            pos_y-=step*1;
            break;
        case 2:
            pos_x+=step*1;
            break;
        case 3:
            pos_x-=step*1;
            break;
        }
      timeToLeave++;

     }
        generation+=timeToLeave;
    }
    // faire le calcul de la moyenne
    printf("%.1f\n",generation/100000);

    return 0;
}

3. Tests et exécutions

Les test se font avec plusieurs longueurs de pas, et des fourmilièrers plus ou moins grandes.

Test avec comme entrées

gcc -Wextra -Wall -Werror MarkovAnt.c
./a.out
3
7 7
+-----+
|.....|
|.....|
|..A..|
|.....|
|.....|
+-----+

Résultat:

1.0

4. solutions de la communauté

Dans la solution de Orselix,il utilise une fonction pour les déplacement des fourmies qui est récursif et qui renvoie le nombre de déplacement d’une fourmie, puis il fait une moyenne sur 100000 itérations

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>


int deplacement(int h,int w, int pos[],int step) {
    if(pos[0]<=0 || pos[0]>=h-1 || pos[1]<=0 || pos[1]>=w-1) return 0;
    int liste_direction[4] = {-1, 0, 1, 0};
    int choix = rand()%4;
    pos[0] += liste_direction[choix]*step;
    pos[1] += liste_direction[(choix+1)%4]*step;
    return (1 + deplacement(h,w,pos,step));
}

int main()
{
    srand(4);
    int step;
    scanf("%d", &step);
    int w;
    int h;
    int base[2] = {-1,-1};
    scanf("%d%d", &w, &h); fgetc(stdin);
    for (int i = 0; i < h && base[0]==-1; i++) {
        char row[32];
        scanf("%[^\n]", row); fgetc(stdin);
        for(int j=0;j<w;++j) {
            if(row[j]=='A') {
                base[0] = i;
                base[1] = j;
            }
        }
    }
    int somme = 0;
    for (int i=0;i<100000;++i) {
        int pos[2] = {base[0],base[1]};
        somme += deplacement(h,w,pos,step);
    }
    printf("%.1f",somme/100000.0);
    return 0;
}

Code de Orselix

retour au Hub

Markov ants

Table of Contents

1. Introduction Markov ants

2. Solution expliquée

3. Tests et exécutions

4. solutions de la communauté