Partage
  • Partager sur Facebook
  • Partager sur Twitter

Algorithmes divers multi-langage

tris, pathfinder, calcul, matrice, etc.

    16 mai 2009 à 20:26:17

    Je ne crois pas que le fait de passer la fonction "f" en paramètre aie beaucoup d'intérêt. Ça n'augmente pas la généricité puisqu'on ne sait rien de ce dont la fonction peut avoir besoin, donc on ne traite que des cas particuliers : la preuve, entre ton ancienne version et la nouvelle tu as changé l'interface de f, tu prenais la taille du tableau (drôle d'idée btw) et maintenant tu prends i+1, pourquoi +1 ?
    Si tu voulais un truc vraiment générique, tu lui donnerais le tableau et l'indice en cours, mais franchement je ne vois pas l'intérêt. Tant qu'on n'a pas besoin de l'abstraction, ce n'est pas la peine d'abstraire.
    • Partager sur Facebook
    • Partager sur Twitter
      17 mai 2009 à 13:17:06

      Combinatoire : calcul de la i-ème permutation d'une liste a n éléments



      Principe


      Le principe de cet algoritme est la notation factorielle :
      http://en.wikipedia.org/wiki/Factoradic

      Pour expliquer plus simplement :
      1) Il y a n! permutations de n éléments
      2) Donc (n-1)! permutations de n-1 éléments,
      3) Ainsi le premier chiffre de la ième permutation serra le i/(n-1)! chiffre de la liste
      4) On retire le chiffre de la liste, puis on réitère ce raisonnement, avec la i%(n-1)! permutation d'un ensemble a n-1 éléments

      Complexité


      La complexité de cet algoritme est en O(n) (n étant le nombre d'éléments, et non le numéro de la permutation).
      Si on calcule la complexité par rapport au numéro de la permutation, la complexité est en
      Il permet de calculer très rapidement la milliardième permutation d'un tableau a 13 éléments par exemple.

      [C] Implémentation


      L'implémentation est basique et peut tout a fait être améliorée (précalcul des factorielles, utilisation de listes)

      #include <stdlib.h>
      #include <string.h>
      #include <stdio.h>
      
      
      int * permutation( int * elem, int size, int num )
      {
          int i,j,k;
          int fact;
          int * temp = malloc( sizeof(int) * size);
          int * perm = malloc( sizeof(int) * size);
      
          memcpy( temp, elem, sizeof(int) * size);
      
          for ( i=0; i<size-1; i++)
          {
              for ( j=size-i-1, fact=1; j>0; fact *= j--);
      
              k = num/fact;
              num %= fact;
      
              perm[i] = temp[k];
              for ( ; k+1<size; k++)
              {
                  temp[k] = temp[k+1];
              }
          }
          perm[size-1] = temp[0];
          free(temp);
          return perm;
      }
      
      int main(void)
      {
          int tab[4] = {1,2,3,4};
          int i;
      
          int * perm;
          for(i=0; i<24; i++)
          {
              perm = permutation(tab, 4, i );
              printf("{%d,%d,%d,%d)\n", perm[0], perm[1], perm[2], perm[3]);
              free(perm);
          }
      
          return 0;
      }
      
      • Partager sur Facebook
      • Partager sur Twitter
        17 mai 2009 à 15:06:47

        Merci pour ta participation. ;)

        Citation : Floooder

        Si on calcule la complexité par rapport au numéro de la permutation, la complexité est en


        Phrase incomplète. :)
        • Partager sur Facebook
        • Partager sur Twitter
          17 mai 2009 à 15:51:28

          Algorithmes divers sur séquence : Recherche dichotomique


          Principe


          Une recherche naïve parcourt toute la séquence concernée (en O(n) donc). Avec la recherche dichotomique, on profite du fait qu'une séquence soit triée. Le principe, récursif, est le suivant : on compare l'élément recherché à la médiane de la séquence. Trois cas sont possibles : soit il y a équivalence, on retourne l'indice de la médiane ; soit l'élément recherché est supérieur, on fait donc une recherche dichotomique sur la seconde partie de la séquence, soit l'élément recherché est inférieur, auquel cas on fait une recherche dichotomique sur la première partie de la séquence. Plus ici.

          Complexité


          En O(log n) sur un tableau et à première vue en O(n log n) sur une liste chaînée (à confirmer). De toute manière, on n'utilisera jamais de recherche dichotomique sur une liste chaînée, la mieux que l'on puisse y faire est une recherche séquentielle, en O(n).

          [Javascript] Implémentation


          Dans cette implémentation récursive en Javascript, la fonction dichotomie (qui effectue la recherche dichotomique) prend en paramètre le tableau où la recherche est effectuée, la valeur recherchée et deux indices deb et fin permettant de "circonscrire" la partition en cours de tab. Si deb est supérieur à fin, la valeur n'a pas été trouvé, on renvoie alors -1. Sinon on récupère la valeur médiane et on effectue les différents tests (voir "principe").

          function dichotomie(tab, valeur, deb, fin)
          {
          	if(deb <= fin){
          		var milieu = parseInt((deb+fin)/2);
          		if(tab[milieu] == valeur) return milieu;
          		else if(tab[milieu] < valeur) return dichotomie(tab, valeur, milieu+1, fin);
          		else if(tab[milieu] > valeur) return dichotomie(tab, valeur, deb, milieu-1);}
          	else return -1;
          };
          
          • Partager sur Facebook
          • Partager sur Twitter
            17 mai 2009 à 16:00:35

            Algorithmes divers sur séquence : construction d'un ABR à partir d'un tableau trié


            Principe



            On va utiliser le principe du « diviser pour régner » pour construire un arbre binaire de recherche (ABR) à partir d'un tableau trié en prenant la valeur du milieu de ce tableau et en créant un noeud avec cette valeur pour étiquette et comme fils gauche l'application récursive de notre algorithme sur la partie gauche du tableau (idem pour le fils droit). En effet, tout élément à gauche d'un autre élément dans un tableau trié est plus petit, on a donc la même relation d'ordre globale que sur les ABR.

            Complexité



            En <math>\(O(n)\)</math>.

            [OCaml] implémentation



            type 'a abr =
            |   Vide
            |   Noeud of ('a abr * 'a * 'a abr)
            
            let abr_of_array arr =
                let rec abr_of_array g d =
                    if g > d then
                        Vide
                    else
                        let m = (g + d) / 2 in
                        Noeud (abr_of_array g (m - 1), arr.(m), abr_of_array (m + 1) d)
                in
                abr_of_array 0 (Array.length arr - 1)
            


            [Python] Implémentation


            Je vais pour simplifier les choses représenter les arbres par des couples soit vides (« () ») soit constitués de 3 éléments (« (fg, elem, fd) »).

            def abr_of_list(li):
                if li == []:
                    return ()
                else:
                    m = len(li) / 2
                    return (abr_of_list(li[:m]), li[m], abr_of_list(li[m+1:]))
            


            [C] Implémentation



            struct abr
            {
                void* elem;
                struct abr* fg;
                struct abr* fd;
            };
            
            struct abr* _abr_of_arr(void* arr[], size_t g, size_t d)
            {
                size_t m = (g + d) / 2;
                struct abr* new;
            
                if (g > d)
                    return NULL;
            
                new = malloc(sizeof (struct abr));
                new->elem = arr[m];
                new->fg = _abr_of_arr(g, m - 1);
                new->fd = _abr_of_arr(m + 1, d);
                return new;
            }
            
            struct abr* abr_of_arr(void* arr[], size_t size)
            {
                return _abr_of_arr(arr, 0, size - 1);
            }
            
            • Partager sur Facebook
            • Partager sur Twitter
              17 mai 2009 à 16:12:02

              Citation : Ppjet6

              En <math>\(O(log_2(n))\)</math> si je ne me trompe pas.



              Hum, plutôt en O(n), non ?
              • Partager sur Facebook
              • Partager sur Twitter
                17 mai 2009 à 16:13:32

                Oui, en fait je suis con. On a en moyenne log2(n) appels récursifs imbriqués mais il y en a deux à chaque fois, ce qui fait donc bien du O(n).
                • Partager sur Facebook
                • Partager sur Twitter
                  17 mai 2009 à 16:47:15

                  Une autre implémentation de l'algorithme d'Euclide, toute simple, en C (valide en C++) :
                  int pgcd(int a, int b)
                  {
                      if(!b) return a;
                      return pgcd(b, a%b);
                  }
                  
                  • Partager sur Facebook
                  • Partager sur Twitter
                    17 mai 2009 à 16:48:46

                    Algorithme sur ABR : l'arbre est-il un ABR ?


                    Principe


                    Les arbres binaires de recherche sont caractérisés par une relation d'ordre globale : tout élément dans le fils gauche d'un noeud est inférieur à l'étiquette du noeud, et tout élément dans le fils droit y est supérieur. L'algorithme naïf pour vérifier si un arbre binaire est un ABR consiste donc à, pour chaque noeud, regarder si tous les éléments à gauche sont plus petits et tous les éléments à droite plus grands. Cependant, cet algorithme est très lent et oblige à parcourir de nombreuses fois l'arbre. L'algorithme que je propose ici a l'avantage de ne parcourir qu'une seule fois l'arbre. À chaque itération, on va encadrer le sous-arbre gauche et le sous-arbre droit entre une valeur minimale que ses éléments peuvent prendre et une valeur maximale. Si un des éléments sort de cet intervalle, l'arbre n'est pas un ABR.

                    Complexité



                    <math>\(O(n)\)</math> avec n la taille de l'arbre (nombre de noeuds).

                    [OCaml] Implémentation



                    type 'a abr =
                    |   Vide
                    |   Noeud of ('a abr * 'a * 'a abr)
                    
                    let is_abr tree =
                        let rec is_abr min max tree = match (min, tree, max) with
                        |   (_, Vide, _) -> true
                        |   (Some min, Noeud (_, e, _), _) when min > e -> false
                        |   (_, Noeud (_, e, _), Some max) when max < e -> false
                        |   (_, Noeud (fg, e, fd), _) ->
                                (is_abr min (Some e) fg) && (is_abr (Some e) max fd)
                        in
                        is_abr None None tree
                    


                    [Python] Implémentation



                    Je vais pour simplifier les choses représenter les arbres par des couples soit vides (« () ») soit constitués de 3 éléments (« (fg, elem, fd) »).

                    def is_abr(tree, min=None, max=None):
                        if tree == ():
                            return True
                        elif (min is not None) and (tree[1] < min):
                            return False
                        elif (max is not None) and (tree[1] > max):
                            return False
                        else:
                            return is_abr(tree[0], min, tree[1]) and is_abr(tree[2], tree[1], max)
                    
                    • Partager sur Facebook
                    • Partager sur Twitter
                      17 mai 2009 à 17:05:36

                      Très intéressant, merci. :)
                      • Partager sur Facebook
                      • Partager sur Twitter
                        17 mai 2009 à 17:06:24

                        Euclide en Python :

                        def pgcd(a, b):
                            return b if a % b == 0 else pgcd(b, a % b)
                        
                        • Partager sur Facebook
                        • Partager sur Twitter
                          17 mai 2009 à 17:17:28

                          C'est un concours ? Le voilà en Forth :

                          : PGCD  ?DUP IF TUCK MOD RECURSE THEN  ;
                          • Partager sur Facebook
                          • Partager sur Twitter
                            17 mai 2009 à 17:21:06

                            Citation : Pingouin chauffé

                            C'est un concours ?


                            Euh, non.
                            • Partager sur Facebook
                            • Partager sur Twitter
                              17 mai 2009 à 18:44:59

                              Calculs divers : Calcul du PPCM


                              Principe


                              Le <acronym title="Plus petit commun multiple">PPCM</acronym> (LCM en anglais) de deux entiers a et b est le plus petit entier positif multiple à la fois de a et de b ; on s'en servira en arithmétique pour manipuler des fractions (addition et soustraction, notamment). L'article de wikipédia vous en dira plus à son sujet.

                              [Forth] Implémentation


                              Cette définition se sert de la relation : Image utilisateur

                              : PGCD  TUCK MOD ?DUP IF RECURSE THEN  ;
                              : PPCM  2DUP ABS -ROT PGCD / SWAP ABS *  ;

                              On peut aussi écrire, d'une manière plus concise mais parfois moins efficace: PPCM  2DUP * ABS -ROT PGCD /  ;
                              Notez que la relation utilisée ne permet pas de calculer le PPCM pour a ou b nul(s) — qui est zéro, par définition.
                              • Partager sur Facebook
                              • Partager sur Twitter
                                17 mai 2009 à 19:51:11

                                Ppjet6 : erreur bête dans ton code, tu as appelé "fd" le fils gauche et inversement, ce qui rend le code faux.

                                Une autre version du code, plus légère, en utilisant des fonctions prédicats :
                                let is_abr' tree=
                                  let (&&&) p q x = p x && q x in
                                  let rec is_abr p = function
                                  | Vide -> true
                                  | Noeud (g, e, d) ->
                                      p e && is_abr ((>) e &&& p) g && is_abr ((<) e &&& p) d in
                                  is_abr (fun _ -> true) tree
                                


                                Edit : un inconvénient de cette solution est que la complexité passe en O(n log n) (pourquoi ?). On peut faire un hybride avec la première solution pour retrouver le O(n) :
                                let is_abr' tree=
                                  let check e (mini, maxi) =
                                    let check comp = function None -> true | Some e' -> comp e e' in
                                    check (>) mini && check (<) maxi in
                                  let rec is_abr p = function
                                  | Vide -> true
                                  | Noeud (g, e, d) ->
                                      check e p && is_abr (fst p, Some e) g && is_abr (Some e, snd p) d in
                                  is_abr (None, None) tree
                                

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  17 mai 2009 à 20:08:03

                                  Hm, mea culpa, l'erreur est corrigée, merci. J'avais testé sur un mauvais exemple en fait.

                                  Et j'ai beau tourner ça dans tous les sens, j'ai du mal à voir en quoi ton code est mieux que le code simple que j'ai présenté. À vrai dire je le trouve plus compliqué, moins lisible et en plus il est plus long. Niveau vitesse je pense que je suis également plus rapide (moins d'appels, etc.). Tu peux m'éclaircir sur ce point ?
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    18 mai 2009 à 19:27:23

                                    Calculs divers : Conversion base 10 vers base n


                                    Principe


                                    Le but est ici d'avoir un algorithme qui convertit un nombre en base 10 vers une base quelconque. Il existe plusieurs algorithmes aboutissant au même résultat. Celui présenté ici me plait particulièrement car il est très compact. Son principe est le suivant : soit v le nombre à convertir en base b, on renvoie le retour du même algorithme sur v/b suivi de v%b. On définie une condition d'arrêt, quand v vaut zéro.

                                    Complexité


                                    Exactement en logb(n) pour b étant la base de destination et n le nombre à convertir. Avec Landau, O(log n).

                                    [OCaml] Implémentation


                                    OCaml met une structure de données très intéressante à disposition : les listes. Dans l'implémentation de cet algorithme, nous allons justement utiliser les listes et se servir d'un accumulateur, ce qui permet de construire le résultat sous forme d'une liste d'unités sans utiliser l'opérateur @. Une implémentation basique que l'on ferait en premier lieu ne gère pas le cas 0, c'est pourquoi nous allons créer deux fonctions (l'une dans l'autre), le cœur de l'algorithme sera dans la fonction inline et la fonction englobant le tout se chargera de traiter le cas 0. Très simplement :

                                    let rec of_dec b v =
                                      let rec of_dec acc = function
                                      | 0 -> acc
                                      | v -> of_dec (v mod b::acc) (v / b)
                                      in if v = 0 then [0]
                                      else of_dec [] v
                                    


                                    Merci à coucou747 pour la refonte du code OCaml (notamment l'astuce de l'accumulateur).
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      18 mai 2009 à 20:57:28

                                      Calcul de factorielle par continuations


                                      Principe

                                      Le principe des continuations est très simple : au lieu de renvoyer tout bêtement le résultat qu'elle calcule, la fonction appelle dessus une fonction k appelée kontinuation, donnée en argument. Nous allons illustrer ce principe sur une factorielle : l'algorithme utilisé est une bête récursivité. Si n vaut 0, on appelle donc k sur 0!, c'est à dire 1. Si n est supérieur à 0, on calcule (n - 1)!, on le multiplie par n, et on lui applique k. Cela revient donc à appliquer à (n - 1)! une fonction qui multiplie par n puis applique k.

                                      Une fois la fonction déclarée, on peut donc très simplement récupérer le résultat de f(n!) en écrivant fac f n . Pour récupérer simplement n!, on écrira fac (fun x -> x) n .

                                      Complexité

                                      O(n), mais l'algorithme ici n'est pas intéressant pour le calcul de la factorielle à cause des stockages de fonctions de plus en plus complexes. Lui préférer une récursivité terminale avec accumulateur, voire même une simple récursivité si on ne manipule pas de trop grands nombres (qui de toute façon feront dépasser la capacité des int de Ocaml)

                                      ...


                                      Implémentation en Ocaml

                                      let rec fac k = function
                                          |0 -> k 1
                                          |n -> fac (fun x -> k (n * x)) (n - 1)
                                      ;;
                                      



                                      flashagogo delenda est.
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        18 mai 2009 à 23:33:00

                                        Edit : En attendant de trouver plus adapté, je mets ça dans "Calculs divers". Encore merci. ;)
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          18 mai 2009 à 23:54:44

                                          Factorielle par continuations : le retour


                                          Implémentation en Python [2.x]

                                          Cette implémentation en style impératif n'a aucun intérêt, si ce n'est d'aider à la compréhension du principe des continuations. Pour cette raison, le code est moche : il utilise le minimum de caractéristiques propres à Python pour se concentrer sur l'aspect compréhension du principe. Il est donc recommandé de lire celle là si vous avez du mal avec celle en Ocaml, mais laissez la tomber si vous avez compris l'autre. Autrement dit, si vous lisez ça, vous n'avez rien compris à mon message précédent. Vu ?
                                          def fac(k, n):
                                              resultat = 1
                                              indice = 1
                                              while indice <= n:
                                                  resultat = resultat * indice
                                                  indice = indice + 1
                                              return k(resultat)
                                          



                                          flashagogo delenda est.
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            19 mai 2009 à 1:07:17

                                            Calculs divers : Suite de Fibonacci par exponentiation de matrice


                                            Principe



                                            Tout le monde (ou presque) connait la suite de Fibonacci sous sa forme suivante :

                                            <math>\(\begin{cases}F_0 &=& 0 \\F_1 &=& 1 \\F_n &=& F_{n-1} + F_{n-2}\end{cases}\)</math>


                                            Cependant, on peut montrer mathématiquement l'égalité suivante, qui a un grand intérêt comme je le montrerai dans la partie complexité de ce message :

                                            <math>\(\forall n \in \mathbb{N}^{*},\ \begin{pmatrix}F_{n + 1} & F_n \\F_n & F_{n - 1}\end{pmatrix}=\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}^n\)</math>


                                            Avec <math>\(F_n\)</math> représentant le n-ième terme de la suite de Fibonacci (<math>\(F_0 = 0,\ F_1 = 1\, F_2 = 1,\ F_3 = 2,\ \ldots\)</math>).

                                            Démonstration : soit <math>\(\forall n \in \mathbb{N}^{*}, P_n\)</math> la proposition suivante :

                                            <math>\(\begin{pmatrix}F_{n + 1} & F_n \\F_n & F_{n - 1}\end{pmatrix}=\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}^n\)</math>


                                            On va montrer que <math>\(P_1\)</math> est vraie, puis que <math>\(\forall n \in \mathbb{N}^{*},\ P_n\ \Longrightarrow\ P_{n+1}\)</math> (démonstration par récurrence) :

                                            <math>\(\left[\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}^1=\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}=\begin{pmatrix}F_2 & F_1 \\F_1 & F_0\end{pmatrix}\right]\ \Longrightarrow\ P_1\)</math>


                                            <math>\(\begin{array}P_n & \Longrightarrow &\begin{pmatrix}F_{n + 1} & F_n \\F_n & F_{n - 1}\end{pmatrix}&=&\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}^n \\& \Longrightarrow &\begin{pmatrix}F_{n + 1} & F_n \\F_n & F_{n - 1}\end{pmatrix}\ \times\ \begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}&=&\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}^{n+1} \\& \Longrightarrow &\begin{pmatrix}F_{n+1} + F_n & F_{n+1} \\F_{n} + F_{n-1} & F_n\end{pmatrix}&=&\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}^{n+1} \\& \Longrightarrow &\begin{pmatrix}F_{n+2} & F_{n+1} \\F_{n+1} & F_n\end{pmatrix}&=&\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}^{n+1} \\& \Longrightarrow & P_{n+1}\end{array}\)</math>


                                            La proposition <math>\(P_n\)</math> est donc vraie pour tout <math>\(n\)</math> dans <math>\(\mathbb{N}^{*}\)</math>

                                            Complexité



                                            C'est là que ça devient intéressant. Avec la relation classique de récurrence de la suite de Fibonacci, on a au mieux un algorithme en <math>\(O(n)\)</math>. Là, on pourrait se dire que c'est la même chose : en effet, le calcul de <math>\(F_n\)</math> prend <math>\(n + 1\)</math> multiplication de matrices (qui sont en <math>\(O(1)\)</math>, rappelons le). Cependant, en utilisant l'algorithme d'exponentiation rapide pour multiplier notre matrice, on a <math>\(O(log_2(n))\)</math> multiplications, donnant donc un algorithme en complexité <math>\(O(log(n))\)</math>, soit beaucoup plus rapide sur de grands nombres que l'algorithme classique. En comparaison, voilà le nombre d'opérations (comparaisons, additions, multiplications, soustractions et divisions) en fonction de <math>\(n\)</math> avec les deux algorithmes (avec n allant de 0 à 200) :

                                            Image utilisateur


                                            Les résultats sont sans appels. Pour les curieux, voilà le code du benchmark :
                                            type mat2x2 = { e11 : int ; e21 : int ;
                                                            e12 : int ; e22 : int }                                                                                                                            
                                                                                                                                                                                                               
                                            let counter = ref 0                                                                                                                                                
                                                                                                                                                                                                               
                                            let count2 f = (fun a b -> incr counter; f a b)                                                                                                                    
                                                                                                                                                                                                               
                                            let ( + ) = count2 ( + )                                                                                                                                           
                                            let ( * ) = count2 ( * )                                                                                                                                           
                                            let ( / ) = count2 ( / )                                                                                                                                           
                                            let ( - ) = count2 ( - )                                                                                                                                           
                                            let ( = ) a b = count2 ( = ) a b                                                                                                                                   
                                            let ( < ) a b = count2 ( < ) a b                                                                                                                                   
                                            let ( > ) a b = count2 ( > ) a b                                                                                                                                   
                                                                                                                                                                                                               
                                            let fibo n =                                                                                                                                                       
                                              let multmat m1 m2 =                                                                                                                                              
                                                { e11=m1.e11*m2.e11 + m1.e21*m2.e12 ; e21=m1.e11*m2.e21 + m1.e21*m2.e22 ;                                                                                      
                                                  e12=m1.e12*m2.e11 + m1.e22*m2.e12 ; e22=m1.e12*m2.e21 + m1.e22*m2.e22 }                                                                                      
                                              in                                                                                                                                                               
                                              let rec expmat m n =                                                                                                                                             
                                                if n = 0 then                                                                                                                                                  
                                                  { e11 = 1 ; e21 = 0 ;                                                                                                                                        
                                                    e12 = 0 ; e22 = 1 }                                                                                                                                        
                                                else if n = 1 then                                                                                                                                             
                                                  m                                                                                                                                                            
                                                else if n mod 2 = 0 then                                                                                                                                       
                                                  expmat (multmat m m) (n / 2)                                                                                                                                 
                                                else                                                                                                                                                           
                                                  multmat (expmat (multmat m m) ((n - 1) / 2)) m                                                                                                                 
                                              in                                                                                                                                                               
                                              if (n  = 0) || (n = 1) then                                                                                                                                      
                                                n                                                                                                                                                              
                                              else
                                                let fibomat = { e11 = 1 ; e21 = 1 ;
                                                                e12 = 1 ; e22 = 0 } in
                                                (expmat fibomat (n - 1)).e11
                                            
                                            let classic_fibo n =
                                              let rec fibo a b n =
                                                if n = 0 then a
                                                else if n = 1 then b
                                                else fibo b (a + b) (n - 1)
                                              in
                                              fibo 0 1 n
                                            
                                            let count f x =
                                              counter := 0;
                                              let _ = f x in
                                              let c = !counter in
                                              counter := 0;
                                              (x, c)
                                            
                                            let rec range = function
                                            |   0 -> [0]
                                            |   n -> (range (n - 1)) @ [n]
                                            
                                            let _ =
                                              let max = 200 in
                                              let r1 = List.map (count classic_fibo) (range max) in
                                              let r2 = List.map (count fibo) (range max) in
                                              List.iter (fun (n, a) -> Printf.printf "%d %d\n" n a) r2
                                            


                                            [OCaml] Implémentation



                                            type mat2x2 = { e11 : int ; e21 : int ;
                                                            e12 : int ; e22 : int }
                                            
                                            let fibo n =
                                              let multmat m1 m2 =
                                                { e11=m1.e11*m2.e11 + m1.e21*m2.e12 ; e21=m1.e11*m2.e21 + m1.e21*m2.e22 ;
                                                  e12=m1.e12*m2.e11 + m1.e22*m2.e12 ; e22=m1.e12*m2.e21 + m1.e22*m2.e22 }
                                              in
                                              let rec expmat m n =
                                                if n = 0 then
                                                  { e11 = 1 ; e21 = 0 ;
                                                    e12 = 0 ; e22 = 1 }
                                                else if n = 1 then
                                                  m
                                                else if n mod 2 = 0 then
                                                  expmat (multmat m m) (n / 2)
                                                else
                                                  multmat (expmat (multmat m m) ((n - 1) / 2)) m
                                              in
                                              if (n  = 0) || (n = 1) then
                                                n
                                              else
                                                let fibomat = { e11 = 1 ; e21 = 1 ;
                                                                e12 = 1 ; e22 = 0 } in
                                                (expmat fibomat (n - 1)).e11
                                            


                                            [Python] Implémentation



                                            def fibo(n):
                                                if (n // 2) == 0:
                                                    return n
                                                a, b, c, d = 1, 1, 1, 0
                                                e, f, g, h = 1, 0, 0, 1
                                                n -= 1
                                                while n != 0:
                                                    if n % 2 == 1:
                                                        e, f, g, h = a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h
                                                        n -= 1
                                                    if n != 0:
                                                        a, b, c, d = a**2 + b*c, b*(a+d), c*(a+d), d**2 + b*c
                                                        n /= 2
                                                return e
                                            


                                            [Prolog] Implémentation



                                            mult_matrice([A, B, C, D], [E, F, G, H], [R, S, T, U]) :-
                                                R is (A*E + B*G), S is (A*F + B*H),
                                                T is (C*E + D*G), U is (C*F + D*H).
                                            
                                            quot_rem(A, B, Q, R) :-
                                                R is A rem B,
                                                Q is A // B.
                                            
                                            exp_matrice(_, 0, [1, 0, 0, 1]).
                                            exp_matrice(M, 1, M).
                                            exp_matrice(M1, N, M2) :-
                                                quot_rem(N, 2, N2, 0),
                                                mult_matrice(M1, M1, SQM1), exp_matrice(SQM1, N2, M2).
                                            exp_matrice(M1, N, M2) :-
                                                N2 is N - 1,
                                                exp_matrice(M1, N2, M3), mult_matrice(M1, M3, M2).
                                            
                                            hd([H|_], H).
                                            
                                            fibo(0, 0).
                                            fibo(1, 1).
                                            fibo(X, Y) :- exp_matrice([1, 1, 1, 0], X - 1, M), hd(M, Y).
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              19 mai 2009 à 5:33:20

                                              Calcul divers : Crible d'Erathostène


                                              Principe


                                              La recherche des nombres premiers est un domaine particulièrement actif dans les maths. Ici, je vous propose de voir l'une des méthodes que l'on peut employer pour déterminer les nombres premiers inférieurs à un nombre entier donné n : le crible d'Erathostène.

                                              Le principe est simple : on dispose d'un tableau contenant tous les entiers inférieurs ou égaux à n dans l'ordre croissant : {0, 1, 2, ..., n}. On part de l'entier 2 qui est le premier nombre premier rencontré lorsqu'on parcourt notre tableau (dans l'ordre croissant donc). Et, on va barrer (mettre à zéro dans le cas présent) les multiples de ce nombre en commençant par son carré et ce jusqu'à ce qu'on atteigne un multiple supérieur à n.
                                              Ensuite, on avance dans le tableau jusqu'au prochain nombre non rayé, qui est 3, et on fait de même : on commence par rayer son carré, 9, puis tous ses multiples à partir de 9.

                                              Plus généralement, pour un nombre p, on commence à p^2 jusqu'à au plus n. L'explication du carré tient au fait que tous les multiples de p inférieurs à p^2 s'écrivent k*p, avec k < p, et donc sont un multiple d'un entier premier plus petit que p et donc ont déjà été rayés.

                                              Complexité


                                              Après avoir fait pas mal de calculs (une jolie somme en fait), j'en ai déduit que cet algorithme est en <math>\(O(n \cdot \psi(\sqrt{n}))\)</math> et je vous renvoie ici pour savoir ce que c'est que <math>\(\psi\)</math>:p : http://fr.wikipedia.org/wiki/Fonction_digamma C'est assez compliqué, mais le graphe de cette fonction permet d'avoir son comportement pour les entiers positifs.

                                              Voici le graphe concernant notre algorithme :

                                              Image utilisateur
                                              Graphe de complexité en fonction de n


                                              [C] Implémentation



                                              void make_sieve(int *tab, size_t n)
                                              {
                                                      size_t i, j;
                                              
                                                      tab[1] = 0;
                                              
                                                      for(i = 2; (j = i * i) <= n; i++)
                                                              if(tab[i] != 0)
                                                                      for(; j <= n; j += i)
                                                                              tab[j] = 0;
                                              }
                                              
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                19 mai 2009 à 5:51:30

                                                Notons que cet algorithme, même s'il a une complexité temps meilleure que le test de tous les diviseurs inférieur à la racine, a une complexité mémoire bien supérieure : on passe en effet de <math>\(O(1)\)</math> à <math>\(O(n)\)</math>. Boire ou conduire, il faut choisir.
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  19 mai 2009 à 6:29:26

                                                  Tu es sur de cette complexité? Toujours pensé que l'algo était en n.ln(n) ( du au fait que la fonction de répartition des nombres premiers est équivalente a x/ln(x) )
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    19 mai 2009 à 14:07:04

                                                    Ça serait encore pire, remarque. Mais ça ne changerait pas grand chose non plus.


                                                    flashagogo delenda est
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      20 mai 2009 à 10:03:30

                                                      Maxibolt : ta version en python ne me paraît pas très intéressante puisque le calcul de la factorielle est fait de manière classique (boucle), tu as juste wouhou rajouté une continuation à la fin.

                                                      Au contraire, la version OCaml apporte quelque chose parce qu'elle est tail-récursive, et qu'on peut passer "mécaniquement" de la version naïve à ta version (tail-rec avec continuations).

                                                      Ppjet6 : ton code Python utilise des définitions inline, ce qui est assez fourbe (c'est plus court, mais la généricité se perd). On peut faire un meilleur compromis :
                                                      let rec pow mult un a = function
                                                      | 0 -> un
                                                      | n when n mod 2 = 0 -> pow mult un (mult a a) (n / 2)
                                                      | n -> mult a (pow mult un a (n - 1))
                                                      
                                                      let fibo n = if n = 0 then 0 else
                                                        let mult (a,b,c,d) (e,f,g,h) = (a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h) in
                                                        let (r, _, _, _) = pow mult (1, 0, 0, 1) (1, 1, 1, 0) (n-1) in r
                                                      
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        20 mai 2009 à 12:39:27

                                                        Bluestorm -> je sais qu'il n'a aucun intérêt, il sert uniquement à illustrer le principe des continuations. Je pense que dans ce cas, le code Python se comprend très facilement, et aide à la compréhension du code Ocaml pour ceux qui ont du mal.
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          21 mai 2009 à 2:10:15

                                                          Algorithmes de tri : Tri par insertion


                                                          Principe


                                                          C'est un tri très intuitif et c'est le plus rapide sur des séquences de petite taille. On parcourt la séquence à trier dans un certain ordre et on insère chaque élément à sa bonne place dans l'ordre opposé. On peut dire que chaque élément, l'un après l'autre, est inséré dans une séquence déjà triée résultante des précédentes insertions ; après avoir inséré le dernier élément, la séquence se retrouve triée. Plus d'infos ici.

                                                          Complexité


                                                          Sur les tableaux ou les listes chaînées, une insertion dans un ensemble trié est en O(n). On insère n élément(s). L'algorithme est donc en O(n²).

                                                          [OCaml] Implémentation


                                                          Dans cette implémentation, nous utilisons les listes. Le code est sémantiquement parlant et on comprend le principe du tri rien qu'en lisant la fonction tri_insert : si la liste à trier est vide ou est un singleton, on renvoie cette liste (elle est triée). Sinon, on a une tête suivie d'une queue auquel cas on trie la queue avec tri_insert et on y insère la tête.

                                                          let rec insert v = function
                                                          | [] -> v::[]
                                                          | t::q ->
                                                            if v < t then v::t::q
                                                            else t::insert v q
                                                            
                                                          let rec tri_insert = function
                                                          | ([] | [_]) as l -> l
                                                          | t::q -> insert t (tri_insert q)
                                                          
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            21 mai 2009 à 2:21:28

                                                            Une autre implémentation, en C++. Ici, il s'agit de trier un std::vector. On parcourt le tableau passé par référence en paramètre de gauche à droite et on insère les éléments de droite à gauche.

                                                            template <typename T>
                                                            void tri_insert(std::vector<T>& v)
                                                            {
                                                                for(unsigned int i=1; i<v.size(); ++i)
                                                                    for(unsigned int j=i; j>0; --j)
                                                                        if(v[j-1] > v[j]) std::swap(v[j-1], v[j]);
                                                            }
                                                            


                                                            Un petit code pour tester (inclure <iostream>, <vector> et <algorithm>) :
                                                            void print_int(int i)
                                                            {
                                                                std::cout << i << ' ';
                                                            }
                                                            
                                                            int main()
                                                            {
                                                                int t[] = {5, 2, 9, 7, 6, 3, 0, 8, 1, 4};
                                                                std::vector<int> v(t, t+10);
                                                            
                                                                std::for_each(v.begin(), v.end(), print_int);
                                                                std::cout << std::endl;
                                                                tri_insert(v);
                                                                std::for_each(v.begin(), v.end(), print_int);
                                                            
                                                                return EXIT_SUCCESS;
                                                            }
                                                            
                                                            • 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