I- Présentation du problème

A) Les entrées

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

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

2.Fonction deplacement

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;
}

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

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

#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.