Partage
  • Partager sur Facebook
  • Partager sur Twitter

Algorithmes divers multi-langage

tris, pathfinder, calcul, matrice, etc.

    21 mai 2009 à 2:44:18

    Voici une implémentation en C que je propose :

    void my_tri_insertion(int *tab, size_t len)
    {
            size_t j;
            int i, key;
    
            for(j = 1; j < len; j++)
            {
                    for(key = tab[j], i = j; i > 0 && tab[i - 1] > key; i--)
                            tab[i] = tab[i - 1];
                    tab[i] = key;
            }
    }
    


    Et un code pour tester :

    #include <stdio.h>
    
    void my_tri_insertion(int *tab, size_t len);
    void print_t(int *t, size_t len);
    
    int main(void)
    {
            int t[] = {5, 2, 9, 7, 6, 3, 0, 8, 1, 4};
    
            print_t(t, 10);
            my_tri_insertion(t, 10);
            print_t(t, 10);
    
            return 0;
    }
    
    
    void my_tri_insertion(int *tab, size_t len)
    {
            size_t j;
            int i, key;
    
            for(j = 1; j < len; j++)
            {
                    for(key = tab[j], i = j; i > 0 && tab[i - 1] > key; i--)
                            tab[i] = tab[i - 1];
                    tab[i] = key;
            }
    }
    
    void print_t(int *t, size_t len)
    {
            size_t i;
    
            for(i = 0; i < len; i++)
                    printf("%d ", t[i]);
    
            putchar('\n');
    }
    
    • Partager sur Facebook
    • Partager sur Twitter
      21 mai 2009 à 20:58:09

      Algorithmes de tri : Tri par tas (heapsort)


      Principe


      On peut observer ce tri comme l'enchaînement de deux algorithmes assez remarquables : la construction d'un tas (un arbre dont chaque élément est inférieur à son parent) puis le vidage progressif du tas. Pour la construction du tas, chaque élément de la séquence à trier est inséré dans l'arbre de manière à garder une structure de tas. Le vidage consiste à retirer le plus grand élément du tas (racine de l'arbre), à restructurer le tas, puis à réitérer ces opérations tant que le tas n'est pas vide. On peut donc récupérer ainsi à chaque tour les maxima et les placer à la chaîne pour obtenir la séquence initiale triée. Plus.

      Complexité


      L'opération de construction du tas est en O(n log n), le vidage progressif également (récupération du maximum en O(1) et restructuration du tas en O(log n)), on obtient donc un tout, le tri par tas, également en O(n log n). C'est optimal. Ce tri a outre cela une qualité majeure : sur les tableaux, il est possible de l'implémenter en place, donc avec une complexité mémoire en O(1).

      Image utilisateur
      Performances


      [C++] Implémentation


      Plus bas, une implémentation assez simple et sémantiquement parlante en C++. La fonction du tri est heap_sort et elle prend en paramètre le std::vector à trier. On appelle ensuite dans l'ordre build_heap (construction du tas) puis delete_heap (vidage du tas). La fonction down_heap insère un élément (indice passé en paramètre) dans le tas (l'implémentation est en place, donc le tas est modélisé dans le std::vector-même). Les fonctions sont ici polymorphes : vous pouvez envoyer un std::vector de n'importe quel type.

      template <typename T>
      void down_heap(std::vector<T>& v, int i, size_t n)
      {
          unsigned int j=2*i+1;
          while (j < n)
          {
              if(j+1 < n) if(v[j+1] > v[j]) j++;
              if(v[i] >= v[j]) return;
              std::swap(v[i], v[j]);
              i = j; j = 2*i+1;
          }
      }
      
      template <typename T>
      void build_heap(std::vector<T>& v)
      {
          for(int i = v.size()/2-1; i >= 0; --i)
              down_heap(v, i, v.size());
      }
      
      template <typename T>
      void delete_heap(std::vector<T>& v)
      {
          unsigned int n = v.size();
          while (n > 1)
          {
              std::swap(v[0], v[--n]);
              down_heap(v, 0, n);
          }
      
      }
      
      template <typename T>
      void heap_sort(std::vector<T>& v)
      {
          build_heap(v);
          delete_heap(v);
      }
      
      • Partager sur Facebook
      • Partager sur Twitter
        28 juin 2009 à 16:37:06

        Salut à tous et toutes :D,

        j'ai une question pour ne pas encombrer inutilement cette page.
        j'ai toujours eu besoin (et je sais que je suis loin d'etre le seul) d'une petite mèthode qui permet de faire un arrondi sur une précision près.

        Je me suis amusé à faire cette petite méthode dans divers langages (ocaml, java, scheme, c et python). Je voulais savoir si vous trouveriez interessant que je les mette ?

        Une autre méthode intéressante est de trouver deux nombre identiques sur un epsilon près, si celle-ci vous interesse je peux la coder dans les memes langages que précités.

        Dites moi quoi :)
        • Partager sur Facebook
        • Partager sur Twitter
          28 juin 2009 à 16:53:36

          Bah oui, jaguar001, ça peut nous intéresser. Poste. :)
          • Partager sur Facebook
          • Partager sur Twitter
            28 juin 2009 à 19:20:50

            Methode d'arrondi sur une precision près
            Je pense que beaucoup de monde la demande cette petite méthode bien pratique, et même si elle n'est pas bien difficile l'avoir sous la main est bien plus agréable.

            Principe
            Cette méthode quelque soit le langage est implémentée et utilisable de la même façon.
            Elle permet de garder autant de chiffres que l'on souhaite derrière la virgule.
            Il y a deux paramètres :
            - nber : le nombre à arrondir
            - precision : précision (10eme, 100eme, 1000eme...)

            Exemple si besoin est :
            Si on a 100.22234444 et que l'on souhaite une precision au centieme près
            alors la valeur des paramètres est : nber = 100.22234444 et precision = 100
            On aura comme réponse 100.22 comme souhaité

            Les différents langages
            public static double arrondir(double nber, int precision)
                         {
            	             double result = (int)(nber*precision);
            	             return result/precision;
                         }
            


            double arrondir(double nber, int precision)
            {
            	int result = (int)(nber*precision);
            	return result/precision;
            }
            


            let arrondir (nber:float) (precision:int) = 
            	let prec = float_of_int(precision) in
            		let result = int_of_float(nber*.prec)  in 
            			float_of_int(result)/.prec;;
            


            (define (arrondir nber precision)
            	(let* ((result ( * nber precision)))
                      
                      (/ (round result) precision)))
            


            def arrondir(nber, precision) :
            	result = int(nber*precision)
            	return result/(1.0*precision)
            


            Conclusion
            Voilà je pense que c'est pas mal, je n'ai pas dit que c'était parfait et qu'il n'y a pas moyen de faire plus condenser mais j'ai voulu faire clair et visuel dans les codes.
            J'espère que vous apprécierez.
            • Partager sur Facebook
            • Partager sur Twitter
              28 juin 2009 à 19:27:02

              Hum, pourquoi pas. Mais présente ça comme tout le monde.
              • Partager sur Facebook
              • Partager sur Twitter
                28 juin 2009 à 22:15:36

                voila je l'ai édité je pense que la c'est bon ;)
                • Partager sur Facebook
                • Partager sur Twitter
                  29 juin 2009 à 13:32:02

                  Algorithmes divers sur séquence : Inverser une liste chaînée


                  Principe


                  L'algorithme prend en entrée une liste et renvoie une liste avec les mêmes éléments mais dans le sens inverse. Pour inverser une liste chaînée de manière efficace, nous allons utiliser l'astuce de l'accumulateur. L'idée est la suivante : on parcourt la liste à inverser et à chaque tour, on place l'élément de tête au sommet de l'accumulateur ; à la fin du parcours, l'accumulateur (qui ne sera autre qu'une liste) est la liste de départ inversée.

                  Complexité


                  En utilisant l'accumulateur, en complexité linéaire, c'est à dire en O(n). Attention à ne pas utiliser la méthode naïve qui est quadratique (inverse du reste concaténé à l'élément de tête, nécessite pour chaque concaténation un parcours de la liste).

                  [OCaml] Implémentation


                  Nous allons en réalité construire deux fonctions, l'une dans l'autre, la principale ne nous servant qu'à pouvoir appeler reverse sans le paramètre acc qui est un détail interne qui n'intéresse pas forcément le codeur. Pour le reste, je crois que le code est assez clair, il reflète de manière très transparente les précédentes explications. La fonction reverse est tail-rec.

                  let reverse l =
                    let rec reverse acc = function
                    | [] -> acc
                    | t::q -> reverse (t::acc) q
                    in reverse [] l
                  


                  jaguar001 : Regarde un peu la manière dont les autres algorithmes sont présentés et édite ton post.
                  • Partager sur Facebook
                  • Partager sur Twitter
                    29 juin 2009 à 16:14:38

                    Une autre implémentation, en C :

                    List* reverse(List* l)
                    {
                        List *t = NULL, *acc = NULL;
                        while(l)
                        {
                            t = l;
                            l = t->next;
                            t->next = acc;
                            acc = t;
                        }
                        return acc;
                    }
                    


                    La définition de la structure List que j'utilise (que l'on rencontre souvent) est la suivante :
                    typedef struct list
                    {
                        int data;
                        struct list* next;
                    } List;
                    

                    Pour tester rapidement :
                    #include <stdio.h>
                    #include <stdlib.h>
                    
                    typedef struct list
                    {
                        int data;
                        struct list* next;
                    } List;
                    
                    List* create(int data, List* next)
                    {
                        List* l = malloc(sizeof *l);
                        l->data = data;
                        l->next = next;
                        return l;
                    }
                    
                    void erase(List* l)
                    {
                        if(!l) return;
                        erase(l->next);
                        free(l);
                    }
                    
                    void print(List* l)
                    {
                        if(!l) return;
                        printf("%d ", l->data);
                        print(l->next);
                    }
                    
                    List* reverse(List* l)
                    {
                        List *t = NULL, *acc = NULL;
                        while(l)
                        {
                            t = l;
                            l = t->next;
                            t->next = acc;
                            acc = t;
                        }
                        return acc;
                    }
                    
                    int main()
                    {
                        List* l = create(1, create(2, create(3, create(4, NULL))));
                        print(l);
                        l = reverse(l);
                        putchar('\n');
                        print(l);
                        erase(l);
                        return 0;
                    }
                    
                    • Partager sur Facebook
                    • Partager sur Twitter
                      29 juin 2009 à 16:32:47

                      Voici une version de l'algo de ShareMan qui change directement la liste :

                      void reverse(List** l)
                      {
                          List *t = NULL, *acc = NULL;
                          while(*l)
                          {
                              t = *l;
                              *l = t->next;
                              t->next = acc;
                              acc = t;
                          }
                          *l = t; /*t est sur la dernière cellule... enfin, la première*/
                      }
                      
                      • Partager sur Facebook
                      • Partager sur Twitter
                        1 juillet 2009 à 10:44:27

                        Une autre implémentation du tri rapide, en Haskell (assez proche de l'implémentation OCaml) :

                        qsort [] = []
                        qsort (t:q) = qsort a ++ t : qsort b
                          where a = [y | y <- q, y < t]
                                b = [y | y <- q, y >= t]
                        
                        • Partager sur Facebook
                        • Partager sur Twitter
                          1 juillet 2009 à 13:13:45

                          Une implémentation Haskell du tri fusion :

                          split [] = ([], [])
                          split [e] = ([e], [])
                          split (t:n:q) = (t:q1, n:q2)
                            where (q1, q2) = split q
                          
                          merge l [] = l
                          merge [] l = l
                          merge (t1:q1) (t2:q2) =
                            if t1 < t2 then t1: merge q1 (t2:q2)
                            else t2: merge (t1:q1) q2
                          
                          msort [] = []
                          msort [e] = [e]
                          msort l = merge (msort l1) (msort l2)
                            where (l1, l2) = split l
                          
                          • Partager sur Facebook
                          • Partager sur Twitter
                            1 juillet 2009 à 14:32:44

                            Un simple tri par insertion en Haskell :

                            insert e [] = e:[]
                            insert e (t:q) = case e < t
                              of True  -> e:t:q
                                 False -> t: insert e q
                            	  
                            isort [] = []
                            isort (t:q) = insert t l
                              where l = isort q
                            
                            • Partager sur Facebook
                            • Partager sur Twitter
                              1 juillet 2009 à 14:44:28

                              Une implémentation assez concise de l'algorithme d'inversion de liste, en Haskell :

                              reverse_list l = rev l []
                                where rev [] acc = acc
                                      rev (t:q) acc = rev q (t:acc)
                              
                              • Partager sur Facebook
                              • Partager sur Twitter
                                1 juillet 2009 à 15:05:23

                                Une implémentation Haskell de l'algorithme "calcul d'une racine carrée" d'après l'implémentation OCaml de robocop :

                                racine_carre n = rc n 2 5
                                  where rc x un 0 = un
                                        rc x un n = rc x ((1 / (2 * un)) * (x - un ** 2) + un) (n-1)
                                
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  1 juillet 2009 à 15:39:23

                                  Algorithmes sur ABR : Construire un ABR à partir d'une liste


                                  Principe


                                  On itère sur la liste d'entrée en insérant chaque élément un par un dans l'ABR qui se construit donc progressivement. Au final, on obtient un ABR à partir de notre liste.

                                  Complexité


                                  Pour n éléments à insérer, l'opération est en O(n*log n), chaque insertion se faisant en O(log n).

                                  [OCaml] Implémentation


                                  Nous allons construire deux fonctions, l'une permettant d'insérer un élément dans un ABR passé en paramètre et renvoyant l'ABR résultant de cette insertion et l'autre, la principale, itérant sur la liste d'entrée et insérant chaque élément dans l'ABR résultant de la précédente insertion (on part d'un ABR vide). Le code est générique : on se sert d'un prédicat pour choisir la "direction" (droite ou gauche) lors de l'insertion.

                                  type 'a abr =
                                  | Vd
                                  | Nd of 'a abr * 'a * 'a abr
                                  
                                  let rec inserer pred v = function
                                  | Vd -> Nd (Vd, v, Vd)
                                  | Nd (fg, r, fd) ->
                                    if pred v r then Nd (inserer pred v fg, r, fd)
                                    else Nd (fg, r, inserer pred v fd)
                                  
                                  let rec construire_arbre pred = function
                                  | [] -> Vd
                                  | t::q -> inserer pred t (construire_arbre pred q)
                                  


                                  Un petit essai très simple :
                                  # construire_arbre ( < ) (1::7::3::6::2::[]);;
                                  - : int abr = Nd (Nd (Vd, 1, Vd), 2, Nd (Nd (Vd, 3, Vd), 6, Nd (Vd, 7, Vd)))
                                  # construire_arbre ( > ) (1::7::3::6::2::[]);;
                                  - : int abr = Nd (Nd (Nd (Vd, 7, Vd), 6, Nd (Vd, 3, Vd)), 2, Nd (Vd, 1, Vd))
                                  
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    3 juillet 2009 à 11:37:29

                                    Ne faudrait il pas dans l'algorithme du PGCD vérifier si on a bien a > b et inverser les 2 valeurs sinon? :euh:
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      3 juillet 2009 à 12:13:48

                                      Cela ne change absolument rien. Supposons que l'on travaille avec la fonction récursive suivante :

                                      let rec pgcd a b = match b with
                                      | 0 -> a
                                      | _ -> pgcd b (a mod b)
                                      


                                      Si a > b, alors c'est déjà bon. Si a < b, alors a % b = a. Finalement, la fonction pgcd va être rappelée avec b et a mod b, donc b puis a. Le "bon" ordre se met en place tout seul.
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        3 juillet 2009 à 12:29:01

                                        Algorithme d'Euclide en Haskell :

                                        pgcd a 0 = a
                                        pgcd a b = pgcd b ((mod) a b)
                                        
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          3 juillet 2009 à 12:55:33

                                          D'acord merci, je suis pas encore à l'aise avec les fonction recursives :)
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            3 juillet 2009 à 12:59:18

                                            Non mais ça n'a rien à voir avec la récursivité, c'est l'algorithme d'Euclide en lui-même qui permet cela.
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              3 juillet 2009 à 14:12:24

                                              L'algorithme d'Euclide utilise la division euclidienne (a/b). Si b>a, alors a = 0*b + a. Comme le reste est non nul, b = a et a = reste d'où a = a et la division euclidienne de a par a donne pour reste 0. On pourrait en conclure que a est PGCD et pourtant ce n'est pas le cas.
                                              En revanche, dans ta fonction, tu appelles la fonction avec comme argument (b, a%b). on a a%b = a donc l'argument est (b, a) et comme tu dis on est dans le bon ordre.
                                              Il y a donc une différence entre l'algorithme d'Euclide lui même et celui implémenté non?
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                3 juillet 2009 à 14:15:30

                                                Ci-dessous, une implémentation OCaml d'un algorithme permettant de calculer un PPCM à l'aide du PGCD. On supposera qu'OCaml connait la fonction pgcd de type int -> int -> int :

                                                let ppcm a b =
                                                  (a * b) / pgcd a b
                                                
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  6 juillet 2009 à 10:54:42

                                                  Une implémentation en C pour "Fonction mathématique : calcul d'une racine carrée". La fonction renvoie -1 en cas d'erreur:

                                                  double my_sqrt(double a)
                                                  {
                                                    double un;
                                                    int i;
                                                  
                                                    un = 2.0;
                                                    i = 0;
                                                  
                                                    if (a < 0)
                                                      {
                                                        un = -1;
                                                      }
                                                  
                                                    else
                                                      {
                                                        while (i <= 5)
                                                          {
                                                            un = ((a - un * un) / (2 * un)) + un;
                                                            i++;
                                                          }
                                                      }
                                                  
                                                    return (un);
                                                  }
                                                  


                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    9 juillet 2009 à 11:04:51

                                                    Pathfinding : BFS (Breadth First Search) algorithme


                                                    Principe


                                                    Le but du pathfinding est de trouver le plus court chemin entre deux point dans une map, un graph. L'algorithme BFS propose un parcourt en largeur de la map en associant un coefficient pour chaque point de la map/du graph. Le plus court chemin est donc le chemin qui possède les plus petits coefficients.

                                                    Complexité


                                                    edit : un BFS s'effectue en O(nbNoeuds + nbArcs), enfin avec la notation O je devrais dire O(nbArcs). (merci Artiks)

                                                    [C] Implémentation


                                                    On dispose d'une map qui possède un départ et une arrivée. Le but est de trouver le plus court chemin depuis le départ jusqu'à l'arrivée.
                                                    Pour ce, on va parcourir notre map en largeur depuis le départ. On va associer a chaque case une sorte de coefficient de distance. Plus la case sera loin du départ, plus le coefficient sera grand. Des qu'un coefficient est place sur une case entourant l'arrivée, on stop l'attribution de coefficient.
                                                    Ensuite, on part de l'arrivée et on se dirige toujours vers la case nous entourant possédant le plus petit coefficient.

                                                    J'ai choisis ici d'utiliser des tableaux a deux dimensions comme support plutôt que des graphs en liste chainee, car c'est plus simple a comprendre.



                                                    Attention, c'est un peu long : )
                                                    /*
                                                    **
                                                    ** BFS algorithm made by VladIsYourGod
                                                    **
                                                    */
                                                    
                                                    #include <unistd.h>
                                                    #include <stdlib.h>
                                                    #include <string.h>
                                                    
                                                    # define MAP_HEIGHT	15
                                                    # define MAX		0xffffff
                                                    
                                                    
                                                    /*
                                                    ** Faites un loader de map si vous vous ennuyez 
                                                    ** o symbolise le depart
                                                    ** x symbolise l'arrivee
                                                    ** # represente un obstacle
                                                    ** ' ' un chemin libre
                                                    ** Il faut trouver le plus cours chemin entre o et x
                                                    **
                                                    ** Cette implementation ne prend pas en compte les diagonales
                                                    */
                                                    
                                                    /*
                                                    ** Initialisation de la map.
                                                    ** Cette map doit toujours etre rectangulaire et posseder des murs sur les cotes
                                                    */
                                                    static char	**init_map(void)
                                                    {
                                                      char		**map;
                                                    
                                                      map = malloc(sizeof(*map) * (MAP_HEIGHT + 1));
                                                      map[0] = strdup("###############");
                                                      map[1] = strdup("#            x#");
                                                      map[2] = strdup("#  #### ##### #");
                                                      map[3] = strdup("#  ###        #");
                                                      map[4] = strdup("# ###  ########");
                                                      map[5] = strdup("# ####        #");
                                                      map[6] = strdup("#    ######## #");
                                                      map[7] = strdup("## ###        #");
                                                      map[8] = strdup("#   #         #");
                                                      map[9] = strdup("#             #");
                                                      map[10] = strdup("# ## ###      #");
                                                      map[11] = strdup("#             #");
                                                      map[12] = strdup("# ###      ####");
                                                      map[13] = strdup("#  o          #");
                                                      map[14] = strdup("###############");
                                                      map[15] = 0;
                                                      return (map);
                                                    }
                                                    
                                                    /*
                                                    ** On code proprement, donc on free chaque malloc : )
                                                    */
                                                    static void	free_map(void **map)
                                                    {
                                                      int		c;
                                                    
                                                      c = 0;
                                                      while (map[c])
                                                        {
                                                          free(map[c]);
                                                          c++;
                                                        }
                                                      free(map);
                                                    }
                                                    
                                                    /*
                                                    ** Fonction pour l'affichage de la map
                                                    */
                                                    static void	aff_map(char **map)
                                                    {
                                                      int		c;
                                                    
                                                      c = 0;
                                                      while (map[c])
                                                        {
                                                          write(1, map[c], strlen(map[c]));
                                                          write(1, "\n", 1);
                                                          c++;
                                                        }
                                                    }
                                                    
                                                    /*
                                                    ** Fonction qui regarde si une case est libre autout de la case courante
                                                    */
                                                    static char	free_place(int **h_map, int c, int c2)
                                                    {
                                                      if (h_map[c][c2 - 1] == -2)
                                                        return (1);
                                                      else if (h_map[c][c2 + 1] == -2)
                                                        return (1);
                                                      else if (h_map[c + 1][c2] == -2)
                                                        return (1);
                                                      else if (h_map[c - 1][c2] == -2)
                                                        return (1);
                                                      return (0);
                                                    }
                                                    
                                                    
                                                    /*
                                                    ** On copie la map dans un int ** et on associe des coefiscients pour chaque type de case
                                                    */
                                                    static int	**cpy_map(char **map, int w, int h)
                                                    {
                                                      int		c;
                                                      int		c2;
                                                      int		**h_map;
                                                    
                                                      h_map = malloc(sizeof(*h_map) * (h + 1));
                                                      for (c = 0 ; c < h ; c++)
                                                        {
                                                          h_map[c] = malloc(sizeof(**h_map) * (w + 1));
                                                          for (c2 = 0 ; c2 < w ; c2++)
                                                    	{
                                                    	  if (map[c][c2] == '#')
                                                    	    h_map[c][c2] = -3;
                                                    	  else if (map[c][c2] == ' ')
                                                    	    h_map[c][c2] = -2;
                                                    	  else if (map[c][c2] == 'x')
                                                    	    h_map[c][c2] = -1;
                                                    	  else if (map[c][c2] == 'o')
                                                    	    h_map[c][c2] = 0;
                                                    	}
                                                        }
                                                      h_map[c] = 0;
                                                      return (h_map);
                                                    }
                                                    
                                                    
                                                    /*
                                                    ** On associe un coefiscient de proximite a chaque point
                                                    */
                                                    static int	associate_coef(int **h_map, int c, int c2)
                                                    {
                                                      if (h_map[c][c2 - 1] == -2)
                                                        h_map[c][c2 - 1] = h_map[c][c2] + 1;
                                                      if (h_map[c][c2 + 1] == -2)
                                                        h_map[c][c2 + 1] = h_map[c][c2] + 1;
                                                      if (h_map[c - 1][c2] == -2)
                                                        h_map[c - 1][c2] = h_map[c][c2] + 1;
                                                      if (h_map[c + 1][c2] == -2)
                                                        h_map[c + 1][c2] = h_map[c][c2] + 1;
                                                      return (1);
                                                    }
                                                    
                                                    /*
                                                    ** Fonction qui recherche le plus petit coefiscient sur les cases entourant une case
                                                    */
                                                    static void	get_smaler(int  **map_h, int *c, int *c2)
                                                    {
                                                      int		min;
                                                      int		dir_c;
                                                      int		dir_c2;
                                                    
                                                      min = MAX;
                                                      if (map_h[*c][*c2 - 1] >= 0 && map_h[*c][*c2 - 1] < min)
                                                        {
                                                          min = map_h[*c][*c2 - 1];
                                                          dir_c = *c;
                                                          dir_c2 = *c2 - 1;
                                                        }
                                                      if (map_h[*c][*c2 + 1] >= 0 &&  map_h[*c][*c2 + 1] < min)
                                                        {
                                                          min = map_h[*c][*c2 + 1];
                                                          dir_c = *c;
                                                          dir_c2 = *c2 + 1;
                                                        }
                                                      if (map_h[*c - 1][*c2] >= 0 && map_h[*c - 1][*c2] < min)
                                                        {
                                                          min = map_h[*c - 1][*c2];
                                                          dir_c = *c - 1;
                                                          dir_c2 = *c2;
                                                        }
                                                      if (map_h[*c + 1][*c2] >= 0 && map_h[*c + 1][*c2] < min)
                                                        {
                                                          min = map_h[*c + 1][*c2];
                                                          dir_c = *c + 1;
                                                          dir_c2 = *c2;
                                                        }
                                                      *c = dir_c;
                                                      *c2 = dir_c2;
                                                    }
                                                    
                                                    /*
                                                    ** On recherche le chemin ayant les plus petits coefiscient
                                                    */
                                                    static void	put_shorter(int **map_h, char **map, int w, int h)
                                                    {
                                                      int		c = 0;
                                                      int		c2 = 0;
                                                    
                                                      while (c < w && map_h[c][c2] != -1)
                                                        {
                                                          c2 = 0;
                                                          while (c2 < h && map_h[c][c2] != -1)
                                                    	c2++;
                                                          if (map_h[c][c2] != -1)
                                                    	c++;
                                                        }
                                                      while (map_h[c][c2] != 0)
                                                        {
                                                          get_smaler(map_h, &c, &c2);
                                                          map[c][c2] = 'o';
                                                        }
                                                    }
                                                    
                                                    /*
                                                    ** Fonction qui test on a pas associe de coefiscient a une case joignant l'arrive
                                                    */
                                                    
                                                    static int	is_end(int **h_map, int c, int c2)
                                                    {
                                                      if (h_map[c][c2] == -1 &&
                                                          ((h_map[c][c2 - 1] != -3 && h_map[c][c2 - 1] != -2) ||
                                                           (h_map[c][c2 + 1] != -3 && h_map[c][c2 + 1] != -2) ||
                                                           (h_map[c - 1][c2] != -3 && h_map[c - 1][c2] != -2) ||
                                                           (h_map[c + 1][c2] != -3 && h_map[c + 1][c2] != -2)))
                                                        return (1);
                                                      return (0);
                                                    }
                                                    
                                                    /*
                                                    ** On parcourt la map en largeur
                                                    */
                                                    static void	bfs(char **map, int w, int h)
                                                    {
                                                      int		**h_map;
                                                      int		c;
                                                      int		c2;
                                                      char		end = 1;
                                                    
                                                      h_map = cpy_map(map, w, h);
                                                      while (end)
                                                        {
                                                          for (c = 0 ; c < h && end ; c++)
                                                    	{
                                                    	  for (c2 = 0 ; c2 < w && end ; c2++)
                                                    	    {
                                                    	      if (is_end(h_map, c, c2)) /* On associe un coefiscient pour chaque point different d'un obstacle et de l'arrive */
                                                    		end = 0;
                                                    	      if (end && h_map[c][c2] != -3 && h_map[c][c2] != -2 && h_map[c][c2] != -1 && free_place(h_map, c, c2))
                                                    		end = associate_coef(h_map, c, c2);
                                                    	    }
                                                    	}
                                                        }
                                                      put_shorter(h_map, map, w, h);
                                                      free_map((void **)h_map);
                                                    }
                                                    
                                                    /*
                                                    ** Un main, what else ? 
                                                    */
                                                    int	main(void)
                                                    {
                                                      char	**map;
                                                    
                                                      map = init_map();
                                                      aff_map(map);
                                                      bfs(map, strlen(map[0]), MAP_HEIGHT);
                                                      aff_map(map);
                                                      free_map((void **)map);
                                                      return (0);
                                                    }
                                                    

                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                    Découvrez un petit jeu Android bien sympa : http://www.siteduzero.com/forum/sujet/appli-jeu-android-cube-racer
                                                      9 juillet 2009 à 11:15:57

                                                      Salut, tu n'as pas du bien comprendre ce que complexité voulait dire.

                                                      un BFS s'effectue en O(nbNoeuds + nbArcs), enfin avec la notation O je devrais dire O(nbArcs).

                                                      De plus, mets juste le code du BFS, parce que là on a pas besoin du code de construction du graphe, et tout ce qui va avec.

                                                      Aussi, je comprends pas bien ce que tu cherches à faire avec tes coefficients, pourquoi t'utilises pas tout simple une file avec une Struct pour stocker les coordonnées du noeud courant et sa distance au début (édit : à la fin, j'ai relu ton post, tu pars de la fin :)) ?

                                                      édit 2 : ce n'est pas Best First Search mais Breadth First Search : Parcours en largeur d'abord :)
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        9 juillet 2009 à 11:25:19

                                                        Ce n'est pas vraiment un bfs, mais c'est l'algo qui ressemble le mieux a ce que j'ai fait : )

                                                        Si je te mets juste l'algo, sans rien autour, il est possible que beaucoup de gens ne comprennent pas.

                                                        Pourquoi utilise une liste chainée alors qu'un tableau suffit ?

                                                        Je pars du début pour associer mes coefficients, et ensuite, je pars de la fin pour me diriger vers le départ en prenant le chemin compose par les plus petit coefficient.
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                        Découvrez un petit jeu Android bien sympa : http://www.siteduzero.com/forum/sujet/appli-jeu-android-cube-racer
                                                          9 juillet 2009 à 11:38:48

                                                          Je te parle pas de ta manière de représenter ton graphe, elle est correcte :)

                                                          Non moi je te parle de la manière de procéder dans le BFS, pour pas s'embêter avec un tas de choses...

                                                          Tu peux faire pareil (associer une distance à la sortie puis partir du début en remontant jusqu'à la sortie) plus simplement (enfin je trouve), en procédant avec une file qui stocke une structure, contenant les cases dans l'ordre où elles doivent être traitées, et la distance à la sortie.

                                                          En re re lisant ton code, je comprends mieux avec tes explications ce que tu fais, fin je crois, mai je trouve ça plus propre avec une file :p
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            9 juillet 2009 à 11:46:29

                                                            Oui, les files sont une autres solution, c'est sur. J'y avais pense, mais je me suis finalement dit que peu de gens les maitrisaient par rapport a la population globale de se site.

                                                            Ce code est loin d'etre parfait, on peut tout optimiser pour gagner en performance et en vitesse, mais le but est qu'il soit compris par un maximum de gens.
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                            Découvrez un petit jeu Android bien sympa : http://www.siteduzero.com/forum/sujet/appli-jeu-android-cube-racer
                                                              9 juillet 2009 à 15:06:26

                                                              Bon je suis d'accord avec artiks il y a pas mal de chose qui ne vont pas
                                                              Tout d'abord la représentation du graphe, c'est un bonne représentation visuelle d'une map mais pas d'un graphe quelconque, pour représenter un graphe on utilise soit une liste d'adjacence soit une matrice
                                                              Après le bfs ou parcours en largeur c'est pas un algorithme en lui même, c'est juste un ordre de parcours des noeuds
                                                              Par exemple tu peux très bien faire un bfs sans pour autant faire un plus court chemin ou un pathfinding
                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              Algorithmes divers multi-langage

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                                              • Editeur
                                                              • Markdown