Citation : khdra

meci

pgcd =: [: {. |/\@|.^:(*@{:)^:_

File de priorité - avec itérateurs (C++)

#ifndef _P_QUEUE_H
#define _P_QUEUE_H


#include <vector>
#include <algorithm>


template <typename T>
class p_queue : private std::vector<T>
{
public:
    typedef typename std::vector<T>::const_iterator const_iterator;

    p_queue();

    void push (const T& x)  { std::vector<T>::push_back(x); push_heap( std::vector<T>::begin(), std::vector<T>::end() ); }
    void pop ()             { pop_heap( std::vector<T>::begin(), std::vector<T>::end() ); std::vector<T>::pop_back(); }

    inline const T& top() const { return std::vector<T>::front(); }
    inline bool empty() const   { return std::vector<T>::empty(); }
    inline size_t size() const  { return std::vector<T>::size(); }

    inline const_iterator begin()     { return std::vector<T>::begin(); }
    inline const_iterator end()       { return std::vector<T>::end(); }
};


#endif

Citation : http://www.cplusplus.com/reference/stl/vector/push_back/

This effectively increases the vector size by one, which causes a reallocation of the internal allocated storage if the vector size was equal to the vector capacity before the call.

Citation : Yannshu

Par contre, ajouter des éléments dans un vector avec des push_back, c'est pas génial il me semble...

Citation : http://www.cplusplus.com/reference/stl/vector/push_back/

This effectively increases the vector size by one, which causes a reallocation of the internal allocated storage if the vector size was equal to the vector capacity before the call.

let rec  partition l p=
  match l with
    | [] -> ([],[])
    |a::q when a<p ->
      let (x,y)= partition q p in
      (a::x,y)
    |a::q -> let (x,y)= partition q p in
      (x,a::y);;

let rec quicksort l =
  if l=[] then []
  else let a =List.hd l and q = List.tl l in
       let x,y = partition q a in
       (quicksort x)@(a::(quicksort y));;

let crible n =
  let t = Array.make (n+1) true in
  for i = 2 to n/2 do (*racine de n marche mieux (en complexité) car a partir de racine de n, k est tj plus grand que n et donc la suite est inutile *)
      if t.(i) then
	( 
	let k = ref (i*i) in
	while !k <= n do
	  t.(!k)<- false;
	  k:= !k +i;
	done;
	) 
  done;                     (* la c'est fini il reste plus qu'a les afficher *)
  for i = 2 to n do 
    if t.(i) then (print_int(i);print_string" ";)
  done;;

let partition t d f =
  let i = ref d and j = ref f in 
  while !i < !j do
    if t.(!i+1) <= t.(!i) then 
      ( 
	swap t !i (!i+1);  
	incr i; 
      ) 
    else 
      (    
	swap t (!i+1) !j;
	decr j;
      )
  done;
!i;;


let quicksort t =
  let rec aux d f =
    if d < f then
    let i = partition t d f in
    aux d (i-1);
    aux (i+1) f;
  in 
  aux 0 ((Array.length t)-1);;

Pathfinder : Dijkstra

Principe

Complexité

[C++] Implémentation avec priority queue

/* Par The Doctor pour le sdz */
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int NB_MAX_NOEUDS = 1000;
const int INFINI = 1000*1000*1000;
const int INDEFINI = -INFINI;

struct arrete
{
   int idNoeudArrive;
   int poidsArrete;
   
   arrete() {}
   arrete(int idNoeudArrive, int poidsArrete) : idNoeudArrive(idNoeudArrive), poidsArrete(poidsArrete) {}
};

struct noeud
{
   int idNoeud;
   int dist;
   
   noeud() {}
   noeud(int idNoeud, int dist) : idNoeud(idNoeud), dist(dist) {}      
   
   bool operator < (const noeud &autre) const
   {
      if(dist != autre.dist)
         return dist > autre.dist;
      return idNoeud > autre.idNoeud;
   }
};


vector<arrete> voisinDuNoeud[NB_MAX_NOEUDS+2];
priority_queue<noeud> noeudsAVisiter;
int dist[NB_MAX_NOEUDS+2];
bool dejaVu[NB_MAX_NOEUDS+2];
int chemin[NB_MAX_NOEUDS+2];

int nbNoeuds, nbArretes, noeudDepart, noeudArrive;

void initDist()
{
   for(int iCase = 0 ; iCase < NB_MAX_NOEUDS+2 ; iCase++)
      dist[iCase] = INDEFINI;
}

int main()
{
   scanf("%d%d%d%d", &nbNoeuds, &nbArretes, &noeudDepart, &noeudArrive);
   initDist();
   for(int iArrete = 0 ; iArrete < nbArretes ; iArrete++)
   {
      int noeud1, noeud2, poids;
      scanf("%d%d%d", &noeud1, &noeud2, &poids);
      voisinDuNoeud[noeud1].push_back(arrete(noeud2, poids));
      voisinDuNoeud[noeud2].push_back(arrete(noeud1, poids));
   }
   
   noeudsAVisiter.push(noeud(noeudDepart, 0));
   
   while(!noeudsAVisiter.empty())
   {
      int idNoeudEnCours = noeudsAVisiter.top().idNoeud;
      int distNoeudEnCours = noeudsAVisiter.top().dist;
      
      noeudsAVisiter.pop();
      if(!dejaVu[idNoeudEnCours])
      {
         dejaVu[idNoeudEnCours] = true;
         dist[idNoeudEnCours] = distNoeudEnCours;
         for(int iVoisin = 0 ; iVoisin < (int)voisinDuNoeud[idNoeudEnCours].size() ; iVoisin++)
            noeudsAVisiter.push(noeud(voisinDuNoeud[idNoeudEnCours][iVoisin].idNoeudArrive, dist[idNoeudEnCours]+voisinDuNoeud[idNoeudEnCours][iVoisin].poidsArrete));
      }
      
   }
   printf("Distance minimale %d -> %d : %d\n", noeudDepart, noeudArrive, dist[noeudArrive]);
}

Calcul du plus petit commun multiple de deux nombres entiers positifs : PPCM

Principe

Complexité

[PHP] Implémentation

function pgcd($nb1,$nb2)
// ******************************************************************************
// *                                                                            *
// *  CALCULE LE PGCD DE DEUX ENTIERS POSITIFS    				*
// *	@$nb1 : entier positif   						*
// *	@$nb2 : entier positif   						*
// *                                                                            *
// ******************************************************************************
{

 if (($nb1 > 0) AND ($nb2 > 0) AND is_integer($nb1) AND is_integer($nb2))
   // Vérification : $nb1 et $nb2 sont des entiers positifs
   {
     while(($nb1>1) AND ($nb2 != 0)) // Tant que le reste n'est pas nul et le 
                                     // diviseur supérieur à 1
      {
        $reste = $nb1%$nb2;    // division entière
	$nb1=$nb2;
        $nb2=$reste;
    }
	}
  else $nb1 = false; // en cas d'erreur la fonction renvoie false
  return $nb1; // retourne le résultat
}
//
// ===============================================================================
//

function ppcm($nb1, $nb2)
// ******************************************************************************
// *                                                                            *
// *  CALCULE LE PPCM DE DEUX ENTIERS POSITIFS    				*
// *	@$nb1 : entier positif   						*
// *	@$nb2 : entier positif   						*
// *                                                                            *
// ******************************************************************************
{
  if (is_integer($nb1) AND is_integer($nb1)) // Vérification : entiers
    {
      if (($nb1 > 0) AND ($nb2 >0)) // Vérification : entiers positifs
	{
	  $le_pgcd = pgcd($nb1, $nb2);
	  if (is_integer($le_pgcd) AND is_integer($le_pgcd))
	    $le_ppcm = ($nb1 * $nb2) / $le_pgcd;
	  else $le_ppcm = $nb1 * $nb2;  // Sinon le ppcm est égal au produit des 2 nb
	}
    }
  else $le_ppcm = false;  // en cas de problème la fonction renvoie faux
  return $le_ppcm;
}
//
// ===============================================================================
//
function ppcm_tab($tab_nb)
// ******************************************************************************
// *                                                                            *
// *  CALCULE LE PGCD DE PLUSIEURS ENTIERS POSITIFS    				*
// *     @$tab_nb : tableau à une dimension d'entiers				*
// *                                                                            // // ******************************************************************************
{
	sort($tab_nb); //  tri du tableau pour réinitialiser les clés
	$taille = count($tab_nb);
	$retour = false;
	if (is_array($tab_nb))
	  {	//	if 1
	    switch ($taille)
	      {	// switch 1
		case 1 : 
	          if (is_integer($tab_nb[0]) AND ($tab_nb[0] != 0)) $retour = $tab_nb[0]; // s'il n'y a qu'un seul nombre, c'est lui le PPCM !
		break;
		case 2 :
		  if (is_integer($tab_nb[0]) AND is_integer($tab_nb[1]) AND ($tab_nb[0] != 0) AND ($tab_nb[1] != 0)) $retour = ppcm($tab_nb[0], $tab_nb[1]);
                    // s'il y a deux nombres, après avoir vérifié signe et type, c'est simple, on appelle la fonction PPCM
		break;			
		default :
		  if (is_integer($tab_nb[0]) AND ($tab_nb[0] != 0)) 
		    {
			$tab_reduit = array_slice($tab_nb, 1);
			$retour = ppcm($tab_nb[0],ppcm_tab($tab_reduit));
		    }
                       // s'il y a plusieurs nombres, on construit un tableau qui compte une case en moins (la première) et on appelle récursivement la fonction sur le nouveau tableau.

	       }	// switch 1
            }	// if 1
	return $retour;
}

selTri2 [] = []
selTri2 l = x:(selTri2 xs)
  where (x,xs) = remMin l
 
remMin [e] = (e, [])
remMin (x:xs) | x < y = (x,y:ys) -- L'ordre n'a pas besoin d'être conservé
              | otherwise = (y,x:ys)
  where (y,ys) = remMin xs

sans (x:xs) (y:ys) | (x < y)   = x:    xs  `sans` (y:ys)
                   | (x == y)  =       xs  `sans`    ys
                   | otherwise =    (x:xs) `sans`    ys
sans l _ = l

union (x:xs) (y:ys) | (x < y)   = x: union    xs  (y:ys)
                    | (x == y)  = x: union    xs     ys
                    | otherwise = y: union (x:xs)    ys
union xs ys = xs ++ ys

premiers    = 2:3: ([5,7..] `sans` nonPremiers)
nonPremiers = foldr f [] [ [p*p, p*(p+2) ..] | p <- tail premiers]
  where f (x:xs) ys = x: union xs ys

qSort' [] = []
qSort' (x:xs) =  (qSort inf) ++ eq ++ (qSort sup)
  where (inf,eq,sup) = partitionner x xs ([],[x],[])

partitionner _ [] classement = classement
partitionner m (x:xs) (i,e,s) = partitionner m xs nClassement
  where nClassement | x < m     = (x:i,e,s)
                    | x == m    = (i,x:e,s)
                    | otherwise = (i,e,x:s)

Citation : Idéophage

Crible d'Ératosthène en Haskell :

premiers = enleverMult [2..]
  where enleverMult (x:xs) =
          x: enleverMult (filter (\n -> (mod n x) /= 0) xs)

Chaînes de caractères : Distance de Leveinshtein − version récursive

Principe

Citation : Wikipedia

La distance de Levenshtein mesure la similarité entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu'il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre.

Complexité

[C] Implémentation

#include <string.h>


unsigned min(unsigned a, unsigned b) {
    return (a < b) ? a : b;
}


unsigned distance(const char* s, const char* t) {
    /* Aller jusqu’à la première différence. */
    for(;  *s == *t;  s++, t++) {
        if(!*s)    // Si les chaînes sont égales, leur distance est 0.
            return 0;
    }
	
    if(!*s)    return strlen(t);
    if(!*t)    return strlen(s);
    
    /* Calcule la distance minimale entre les chaînes restantes selon les
       trois cas de modification possibles : */
    unsigned d = distance(s+1, t  );      /* suppression d’un caractère, */
     d = min( d, distance(s,   t+1) );    /* insertion d’un caractère, */
     d = min( d, distance(s+1, t+1) );    /* remplacement d’un caractère. */
    
    /* la distance est 1 (la différence trouvée) plus la distance minimale
       entre les fins de chaînes. */
    return 1 + d;
}

/* Retourne vrai si la distance entre les deux chaînes est inférieure
   ou égale à d, faux sinon. */
bool compareDistance(const char* s, const char* t, unsigned d) {
    for(;  *s == *t;  s++, t++) {
        if(!*s)    // Les chaînes sont égales.
            return true;
    }
    if(!d)    // Il y a une différence alors qu’on n’en accepte pas.
        return false;
    
    /* s et t pointent maintenant sur le caractère différent, S et T sur le
       suivant (si la fin de la chaîne n’est pas déjà atteinte − sans cette
       sécurité, on pourrait lire après la fin) */
    const char *S = s,  *T = t;
    if(*s)    S++;
    if(*t)    T++;
    
    /* Compare la suite selon les trois cas de modification possibles : */
    return compareDistance(S, t, d-1)     /* suppression d’un caractère, */
        || compareDistance(s, T, d-1)     /* insertion d’un caractère, */
        || compareDistance(S, T, d-1);    /* remplacement d’un caractère. */
}

Citation : Cygal

Malheureusement, ce n'est pas un crible d'Ératosthène : l'idée du crible est d'enlever une fois pour toutes les multiples des nombres premiers déjà vus, ce qui n'est pas fait ici, et ce qui donne un programme très lent (cf. [1] et [2]).

Citation : Cygal

Une list comprehension aurait été peut-être plus élégante ici : [x | x <- xs, n `mod` x /= 0].

Citation : hedi07

Il me semble que si tu arrête ta boucle lorsque p > racine, ca t'évite de la recalculer a chaque fois.

Citation : hedi07

Il y a aussi une astuce pour remplacer p%2 : si je me souviens bien c'est !(p & 1). Le modulo étant coûteux, ca peut aider.

Calculs divers : Exponentiation rapide

Principe

n = 0b1101
b = 3

acc = 1

Le premier chiffre de n en binaire est 1.
    acc =  acc × b    // acc vaut maintenant 3
b =  b × b            // b vaut maintenant 3²

Le chiffre suivant est 0.
b =  b × b            // b vaut maintenant 3⁴

Le chiffre suivant est 1.
    acc =  acc × b    // acc vaut maintenant 3×3⁴ = 3⁵
b =  b × b            // b vaut maintenant 3⁸

Le chiffre suivant est 1.
    acc =  acc × b    // acc vaut maintenant 3⁵×3⁸ = 3¹³
b =  b × b            // b vaut maintenant 3¹⁶ (mais aucune importance)

Complexité

[C] Implémentation

/* Version itérative (préférable en C) */
int power(int x, unsigned n) {
    int acc;
    
    for(acc = 1;  n;  n /= 2) {
        if(n % 2)
            acc *= x;
        x *= x;
    }
    
    return acc;
}

/* Version récursive (le « Diviser pour régner ») */
int power(int x, unsigned n) {
    if(n) {
        int acc = (n%2) ? x : 1;
        return acc * power(x*x, n/2);
    }
    else
        return 1;
}

[OCaml] Implémentation

let pow =
    let rec pow_rec acc b = function
        | 0  -> acc
        | n  ->
            let acc = if (n mod 2 = 1) then acc*b else acc  in
            pow_rec acc (b*b) (n/2)
    in
    pow_rec 1
;;

pow 3 5;;
(*  - : int = 243  *)

let rec gpow ( * ) acc b = function
    | 0  -> acc
    | n  ->
        let acc = if (n mod 2 = 1) then acc*b else acc  in
        gpow ( * ) acc (b*b) (n/2)
;;

(* Calcule la puissance d’un flottant. *)
let pow = gpow ( *. ) 1.;;

(* Multiplie deux entiers. *)
let mul = gpow (+) 0;;

(* Génère une liste de n éléments identiques. *)
let generate_list e = gpow (@) [] [e];;

(* Concatène une chaîne n fois.  *)
let repeat_string = gpow (^) "";;

pow 2.718 5;;
(*  - : float = 148.336238491865572  *)
mul 7 6;;
(*  - : int = 42  *)
generate_list 'z' 7;;
(*  - : char list = ['z'; 'z'; 'z'; 'z'; 'z'; 'z'; 'z']  *)
repeat_string "hi-"  5;;
(*  - : string = "hi-hi-hi-hi-hi-"  *)

Fonctions mathématiques : calcul de l'exponentielle

Principe

[C] Implémentation

double exp(double x)
{
    double res = 1 + x;
    double puis = x, fact = 1;
    const int pres = 25;
    int i;

/* Comme res vaut déjà 1 + x, il faut commencer à x^2, soit i = 2 */
    for(i = 2; i < pres; i++)
    {
        puis *= x;
        fact *= i;
        res += puis / fact;
    }
    return res;
}

Citation : informaticienzero

La méthode utilise le développement limité : <math>\(e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots + \frac{x^n}{n!} + o(x\n)\)</math> ce qui donne en abrégé <math>\(e^x = \sum_{n = 0}^\infty \frac{x^n}{n!}}\)</math>

>>> import math
>>> exp = math.exp
>>> exp(300)
1.9424263952412558e+130
>>> def fact(n): return 1 if n == 0 else f*fact(n-1)
>>> sum(300**n/fact(n) for n in range(25))
4.946304776354304e+35