% Markov ants
% Eliott ESBELIN
% 15.03.25

-----

<div class="content">

# I- Présentation du problème

## A) Les entrées
<div class="liste">
On nous fourni:

* Un entier `step`;
* Deux entiers `w` et `h`;
* Une grille de taille `w*h` représentant la fourmilière;
</div>

## B) Le but du jeu

Une fourmi est placé dans la grille et doit arriver au bord ou en dehors de cette fourmilière. Dans cette représentation ASCII de la fourmilière, la fourmi est représentée par la lettre A et les frontières par les caractères suivants: |, -, +. Chaque élément de la fourmilière est distant de 1cm.

La fourmi quitte sa fourmilière pour chercher de la nourriture, mais elle ne sait pas où aller, donc à chaque seconde elle se déplace de manière aléatoire (d'une distance de `step` cm) directement au nord, au sud, à l'est ou à l'ouest avec une probabilité égale.

Le but est de déterminé le temps moyen en seconde que met une fourmi pour arriver à atteindre la nourriture qui se trouve aux limites de la fourmilière.

## C) La sortie

Un flottant arrondi à une décimale.

# II- Ma méthode de résolution

## A) Approche synoptique

J'ai pensé à faire un calcul de moyenne lambda basé sur une multitude de résultat. Je vais faire en sorte d'effectuer un grand nombre de fois la simulation d'une fourmi qui désire sortir de la fourmilière pour avoir une base sur laquelle effectuer mon calcul de moyenne.

## B) Approche algorithmique et explication de mon programme

### 1.Inclusion des bibliothèques

```c

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

```

### 2.Fonction deplacement

```c

int deplacement(posX,posY,pas,largeur,hauteur){
    int sommeDeplacement=0;
    while(posX>0 && posX<largeur-1 && posY>0 && posY<hauteur-1){
        int aleatoire=rand()%4;
        switch(aleatoire){
            case 0:
                posY+=pas;
                break;
            case 1:
                posY-=pas;
                break;
            case 2:
                posX+=pas;
                break;
            case 3:
                posX-=pas;
                break;
        }
        sommeDeplacement++;
    }
    return sommeDeplacement;
}

```

<div class="liste">
Cette fonction prend en entrée 5 arguments qui sont:

* posX -> colonne sur laquelle se trouve la fourmi;
* posY -> ligne sur laquelle se trouve la fourmi;
* pas  -> distance parcouru en une seconde par la fourmi;
* largeur -> largeur de la grille;
* hauteur -> hauteur de la grille;
</div>

Elle permet de déterminer le temps que met une fourmi à sortir ou atteindre les bords de la fourmilière. Elle incrémente de pas ou décrémente de pas `posY` ou `posX` suivant le déplacement que la fourmi a choisi d'effectuer. Ce choix est réaliser aléatoirement et retourne un chiffre entre 0 et 4 à chaque passsage dans la boucle `while`. Chaque passage dans cette boucle correspond à un déplacement, ce qui est compté dans la variable `sommeDeplacement`. 

Ensuite, on sort de la boucle while lorsque que `posX` ou `posY` a atteint ou dépassé les bords de la grille rreprésenté par les valeurs `0` et `largeur-1` pour `posX` et par les valeurs `0` et `hauteur-1` pour `posY`.

Enfin, la fonction retourne la valeur de la variable `sommeDeplacement`.

### 3.Le main

```c

int main(){
    srand(time(NULL));
    int step;
    scanf("%d", &step);
    int w,h;
    scanf("%d%d", &w, &h); fgetc(stdin);
    char map[16][16];
    int i,j,l;
    int x,y;
    int sommeTotalTemps=0;
    float nbTour=300000.0;
    for(i=0; i<h; i++){
        char row[32];
        scanf("%[^\n]", row); fgetc(stdin);
        for(j=0;j<w;j++){
            if(row[j]=='A'){
                x=j;
                y=i;
                row[j]='.';
            }
        }
        strcat(map[i],row);
    }
    for(l=0;l<nbTour;l++){
        sommeTotalTemps+=deplacement(x,y,step,w,h);
    }
    printf("%.1f",roundf((sommeTotalTemps/nbTour)*10)/10);
    return 0;
}

```

Le main permet d'abord de récupérer toutes les différentes entrées. On initialise la variable pour les nombres aléatoires, une variable `sommeTotalTemps` qui représente la somme des temps qu'on mit les différentes fourmis pour sortie de la fourmilière ainsi qu'une variable `nbTour` à 300 000 qui corespond aux nombres de fourmis que l'on veut pour notre moyenne.

Une boucle for permet ensuite de déterminé la position initial de la fourmi (la lettre `A`), et garde sa position dans les varibales `x` et `y`. 

Ensuite on effectue `nbTour` appel à la fonction `deplacement` avec les arguments suivants: `deplacement(x,y,step,w,h)` et on additione à chaque passage le temps mis par une fourmi pour réussir sa mission.

Enfin, on affiche la moyenne arrondi à une décimale du temps mis par une fourmi pour aller chercher sa nourriture.

# III- Un autre programme

```c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define N 1000000

struct Coords {
    int x, y;
};
int main()
{
    struct Coords A;
    int step;
    scanf("%d", &step);
    int w;
    int h;
    scanf("%d%d", &w, &h); fgetc(stdin);
    for (int i = 0; i < h; i++) {
        char row[32];
        scanf("%[^\n]", row); fgetc(stdin);
        for(int j = 0; row[j] != '\0' && row[j-1] != 'A' && A.x == 0; j++) {
            A.x = row[j] == 'A'?j:0;
            A.y = row[j] == 'A'?i:0;
        }
    }
    int results[N] = {0};
    float sum = 0;
    for(int i = 0; i < N; i++, sum += results[i-1]) {
        struct Coords Test = A;
        for (int j = 0, random = 0;Test.y > 0 && Test.y < h-1 && Test.x > 0 && Test.x < w-1; j++, results[i]++) {
            int random = (rand()%4);
            if(random == 0) Test.x += step;
            if(random == 1) Test.x -= step;
            if(random == 2) Test.y += step;
            if(random == 3) Test.y -= step;
        }
    }
    printf("%.1f\n", sum/N);
    return 0;
}

```

Ce programme réalise déjà toutes les opérations dans son `main`. Il utilise un `define` pour son nombre total de test. Il utilise finalement la même méthode que moi pour calculer sa moyenne mais il l'implémente différemment. En effet il cherche la position initiale de la fourmi dès le début lorsqu'il récupére les différentes lignes de sa grille, en utilisant un opérateur ternaire dont la syntaxe est `condition ? si : sinon`. 

Ensuite il initialise un tableau pour stocker toutes les temps mis par les fourmis pour sortir de la fourmilière, puis il rentre dans sa boucle `N` fois, choisi un nombre aléatoire mais sans utiliser de `srand` au début de son main. Lui ne fait pas un `switch` pour connaitre la direction dans laquelle va la fourmi, il utilise 4 `if` ce qui revient sensiblement au même. 

Enfin, il effectue sa division pour afficher la moyenne avec une décimale de précision.

</div>
<div class="zone-telechargement">
<p>Vous trouverez <a href="../telechargement.html">ici</a> la page de téléchargement du rapport en markdown.</p>
</div>
<div class="footer">
<p>&copy; 2025 ESBELIN Eliott Prep'ISIMA</p>
<div class="footer-images">
```{=html}
    <a href="https://www.uca.fr/"><img src="../Image/UCA.png" alt="Logo UCA"></a>
    <a href="https://www.isima.fr/"><img src="../Image/ISIMA.png" alt="Logo INP/ISIMA"></a>
```
</div>
</div>