Markov Ants

1. Présentation du problème
- 1.1. Input
  - 1.1.1. Exemple de fourmillière
- 1.2. Output
2. Code
3. Conclusion

1. Présentation du problème

Une fourmie cherche à sortir de sa fourmilière pour chercher de la nourriture. La fourmie se déplace aléatoire à droite, à gauche, en bas ou en haut à chaque tour. En partant d’un point donné de la fourmilière, le but est de savoir en moyenne, combien de temps la fourmie va mettre à rejoindre la dortie de celle-ci.

1.1. Input

step
W H
anthill

Il nous est donné en entrer du programme :

step Le nous de case parcouru par la fourmi à chaque tour.
W La longueur de la fourmilière
H La largeur de la fourmilière.
anthill Le schéma de la fourmilière avec A pour la position initiale de la fourmi.

1.1.1. Exemple de fourmillière

+---+
|...|
|.A.|
|...|
+---+

1.2. Output

Le temps moyen mis la fourmis pour sortir de la fourmillière.

2. Code

2.1. Programme principal

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

int search_food(int start[2], char anthill[100][100], int width, int height, int speed){
    int random_dir = rand() % 4;
    int new_y = start[0] + ((random_dir-2)%2) * speed;
    int new_x = start[1] + ((random_dir-1)%2) * speed;
    if (new_x <= 0 || new_x >= width - 1 || new_y <= 0 || new_y >= height - 1){
        return 1;
    } else{
        return 1 + search_food((int[2]) {new_y, new_x}, anthill, width, height, speed);
    }
}

int main()
{
    srand(time(NULL));

    int step;
    scanf("%d", &step);
    int w;
    int h;
    int average = 0;
    int nb_test = 100000;
    scanf("%d%d", &w, &h); fgetc(stdin);
    char anthill[h][w];
    int start[2];
    for (int i = 0; i < h; i++) {
        scanf("%[^\n]", anthill[i]); fgetc(stdin);
        for (int j = 0; j < w; ++j){
            if (anthill[i][j] == 'A'){
                start[0] = i;
                start[1] = j;
            }
        }
    }
    for (int i=0; i<nb_test; ++i) {
        average += search_food(start, anthill, w, h, step);
    }
    printf("%.1f\n", average / (double) nb_test);

    return 0;
}

2.2. Explications

2.2.1. Main

On commence par récupérer les inputs et on choisi un nombre de tests que l’on va exécuter afin d’obtenir une moyenne significative. Ici j’ai choisi de faire 10000 tests. Ensuite on appelle 10000 fois la fonction search_food en partant de la position initiale de la fourmi et on fait la moyenne.

2.2.2. Search_food

On simule ici les déplacements aléatoire de la fourmi dans la fourmillière et l’on compte son nombre de déplacements. Cette fonction est une fonction récursive. Son cas de base est le suivant: La fourmi est en dehors de la fourmillière. Dans ce cas-là, on renvoie 1.

Sinon, on renvoie 1 plus le résultat de search_food en ayant déplacé la fourmi d’une case aléatoirement.

2.3. Tests

Procédont maintenant à quelques tests.

2.3.1. Test d’exemple

— INPUT —

1
5 5
+---+
|...|
|.A.|
|...|
+---+

— OUTPUT —

4.5

2.3.2. Test plus long