Citation : bluestorm

1) Ça ne marche bien que si (n <= 10)

OK ! Je corrige :

void uintToStringInBase (unsigned n, char* str, unsigned base)
{
    if (n >= base)
        uintToStringInBase (n/base,str+1,base);
    else
        *(str+1) = 0;  /* termine la chaine */
    unsigned reste = n%base;
    *str = (reste < 10 ? '0' : 'a'-10) + reste;
}

void putUintInBase(unsigned n, unsigned base)
{
    if (n >= base)
        putUintInBase(n/base, base);
    unsigned reste = n%base;
    putchar( (reste < 10 ? '0' : 'a'-10) + reste );
}

Citation : bluestorm

2) Il faut allouer la chaîne à l'avance, alors qu'on ne connaît pas sa taille (on peut l'approximer, mais mbof)

Ben, en fait il suffit d'utiliser des chaines pouvant contenir la taille maximale possible, on n'est pas forcement a quelques octets près. (En fait, je stocke dans une chaine pour pouvoir afficher avec printf, mais on peut bien entendu imaginer stocker dans une liste.)

Si je ne me trompe pas le nombre de caractères de la chaine quand on convertit un nombre n de la base 10 à la base n est E(log n / log b) + 1

exemple 512 en base 7
log(512) / log(7) = 3,2 donc le nombre de caractères est 4
512 en base 7 donne 1 331

512 en base 26
log(512) / log(26) = 1,9 donc 2
512 = 26 X 19 + 18 512 en base 26 donne SR.

Le calcul de la factorielle avec continuation a déjà été présenté, mais voici une implémentation en Lua :

function fac(n, k)
	if n == 0 then
		return k(1)
	else
		fac(n-1, function (x) return k(n*x) end)
	end
end

Arithmétique : Décomposition d'une nombre en facteurs premiers

Principe

On sait que la décomposition en facteur premier est unique. Donc, l'idée, c'est de choisir un diviseur et son complémentaire (ex pour pour 70 : 2 et 35) et de chercher la décomposition en facteur premier de ces deux nombres.

[ocaml] Implémentation

let find_a_div n = 
  let rec aux n = function
    | 1 -> None
    | div ->
	if n mod div = 0 then Some (div, (n/div))
	else
	  aux n (div-1)
  in
    aux n (n/2)
;;
let decompose n = 
  let rec dec n = match find_a_div n with
    | None -> [n] (* si le nombre est premier, on le renvoi *)
    | Some (a,b) ->
	dec a@dec b
  in
    List.sort compare (dec n)
;;

Exemple :

decompose 196;;
- : int list = [2; 2; 7; 7]

Personnellement, je trouve que c'est mieux de ne pas trimballer n en argument de la fonction aux. Je propose aussi de prendre le premier entier inférieur ou égal à al racine carré du nombre de base comme diviseur au départ.
Je serais curieux d'entendre votre avis.

Donc voilà comment je reprendrais ton code robocop :

let find_a_div n = 
  let rec aux  = function
    | 1 -> None
    | div ->
	if n mod div = 0 then Some (div, (n/div))
	else
	  aux (div-1)
  in
    aux (int_of_float (sqrt (float_of_int n)))
;;
let decompose n = 
  let rec dec n = match find_a_div n with
    | None -> [n] (* si le nombre est premier, on le renvoi *)
    | Some (a,b) ->
	dec a@dec b
  in
    List.sort compare (dec n)
;;

Trop long et trop compliqué.

let facteurs_premiers n =
  let rec decomp d n =
    if n mod d = 0 then d :: decomp d (n / d)
    else if d * d > n then []
    else decomp (d + 1) n in
  decomp 2 n

En effet c'est plus astucieux. Merci :).

Vous m'avez donner des idées .

Arithmétique : Décomposition d'une nombre en facteurs premiers

Principe

On sait que tout facteur minimal supérieur à 1 est premier.
Tant que n est supérieur à un, on test si un nombre n est divisible par un autre nombre j. Si c'est le cas on stock j.
On divise n par j. Et ainsi de suite.
Bien sûr on démarre avec j = 2.

Exemple rapide avec n = 10, j = 2.

10 > 1
   - 10 % 2 == 0
   - on stock 2
   - on divise n par j, donc 10 / 2. n = 5

5 > 1
   - 5 % 2 != 0
   - on incrémente j, donc j = 3

5 > 1
   - 5 % 3 != 0
   - on incrémente j, donc j = 4

5 > 1
   - 5 % 4 != 0
   - on incrémente j, donc j= 5

5 > 1
   - 5 % 5 == 0
   - on stock 5
   - on divise 5 par 5, donc n = 1

1 == 1
on sort de la boucle et c'est la fin de du programme

[C] Implémentation

L'implémentation est similaire à l'explication.
Pour stocker mes facteurs, j'utilise un tableau. L'incrémentation de l'indice a lieu seulement après l'affectation.

#include <stdio.h>
#include <stdlib.h>

#define N 32

int* decompose(int n)
{
    int *t = malloc(N * sizeof *t), i = 0, j = 2;

    if (t == NULL)
        exit(EXIT_FAILURE);

        while (n > 1)
            if (n % j == 0) {
                t[i] = j;
                i++;
                n /= j;
            }
        else j++;

    return t;
}

int main(void)
{
    int *t = decompose(9438), i = 0;

    for (; i < N; ++i)
        if (t[i] != 0)
            printf("%d ",t[i]);

    free(t);
    return 0;
}

2 3 11 11 13

J'aime l'idée, 4drien l'avait posté sur le forum C.

@ bluestorm, ton code doit comporté un ptit bug car il ne sort pas la même chose que le mien et celui de robocop avec pour entrée n = 9438.

# let facteurs_premiers n =
  let rec decomp d n =
    if n mod d = 0 then d :: decomp d (n / d)
    else if d * d > n then []
    else decomp (d + 1) n in
  decomp 2 n
            ;;
val facteurs_premiers : int -> int list = <fun>
# facteurs_premiers 9438;;
- : int list = [2; 3; 11; 11]

Il faut remplacer "d * d" par "d" je pense.

On peut effectivement remplacer "d * d" par d. L'intérêt de "d * d" est de faire seulement une recherche sqrt(n) plutôt que linéaire quand le nombre est premier.

On peut donc corriger comme cela :

let facteurs_premiers n =
  let rec decomp d n =
    if n = 1 then []
    else if d * d > n then [n]
    else if n mod d = 0 then d :: decomp d (n / d)
    else decomp (d + 1) n in
  decomp 2 n

Colb-Seton > je ne cherche pas à diminuer le mérite de candide qui est un bon pédagogue et pratique très bien le C (ce genre de connaissances se fait rare sur le forum), mais l'attribution que tu lui fais n'est pas correcte. Cet algorithme a été proposé en premier par 4drien, plus haut sur la page que tu cites. J'ai même explicitement donné son nom, un peu en dessous, pour que les gens fassent plus attention à sa méthode, avant de donner moi-même une implémentation de l'algorithme (qui a été reprise par candide qui propose la sienne), puis une explication complète (la seule sur le topic).

candide est effectivement utile dans ces discussions, et il connaissait certainement déjà l'algorithme qui fait partie du folklore, mais si tu cherches à attribuer des idées à des gens, au sein d'un topic, il faut le faire correctement : c'est 4drien qui le premier a proposé cette méthode.

Au temps pour moi j'ai pas fais attention, je corrige .

Je pense plutôt que le "d * d" permet tout juste d'économiser un nombre d'appels à decomp égal à la différence des deux plus grands facteurs premiers du nombre à décomposer.

Citation : EMC1

Je pense plutôt que le "d * d" permet tout juste d'économiser un nombre d'appels à decomp égal à la différence des deux plus grands facteurs premiers du nombre à décomposer.

Si on appelle decomp sur un nombre premier `p` avec la condition "d * d > n", il va faire environ `sqrt(p)` appels. Si on met "d > n", il en fera environ `p`.
Qu'est-ce que tu appelles "différence des deux plus grands facteurs" dans le cas d'un nombre premier, qui n'a donc qu'un seul facteur premier ?

Je pense plutôt que le nombre d'appels à decomp est généralement le suivant avec d*d :
Soit f le nombre de facteurs premiers du nombre n et af son deuxième facteurs le plus grand :
Nombre d'appels : f-1 + af -2 +1 (f+af-2).
Tandis que af est le plus grand facteur quand avec "d" à la place de "d * d".

Mais effectivement, dans le cas d'un nombre premier, il y a sqrt(n) appels (arrondi par défaut) avec "d*d" contre n avec "d".

Edit : plus précisément, af est le premier nombre après le deuxième plus grand facteur tel que af * af > n, mais c'est généralement af + 1 ...

Une implémentation du tri rapide en Scala:

def triRapide(l:List[Int]): List[Int] = l match{
      case Nil => Nil
      case (x :: xs) => val (l1, l2) = xs.partition(_ < x)
                       triRapide(l1) ::: x :: triRapide(l2)
}

Edit: Une version générique:

def triRapide[T](inf: (T,T) => Boolean)(l: List[T]) : List[T]= l match{
    case Nil => Nil
    case (x::xs) => val (l1, l2) = xs.partition(inf(_, x))
    triRapide(inf)(l1) ::: x :: triRapide(inf)(l2)
}

Edit 2 : balises scala

Implémentation du tri fusion, encore en Scala:

def triFus[T](inf: (T,T) => Boolean)(l: List[T]) : List[T] = {
    def fusion(l1: List[T], l2: List[T]) : List[T] = (l1, l2) match {
      case (Nil, _) | (_, Nil) => l1 ::: l2
      case (x :: xs, y :: ys)  => if (inf(x, y)) x :: fusion(xs, l2)
                                 else y :: fusion(l1, ys)
    }
    val n = l.length/2
    if (n == 0) l
    else {
      val (l1, l2) = l splitAt n
      fusion(triFus(inf)(l1), triFus(inf)(l2))
    }
}

Edit: balise scala

Construction d'un ABR à partir d'une liste (Scala):

sealed abstract class Arbre{
  def +:(x: Int) : Arbre = this match{
    case Vide => Noeud(x, Vide, Vide)
    case Noeud(v, g, d) => if(x < v) Noeud(v, x +: g, d) else Noeud(v, g, x +: d)
  }
}
case class Noeud(v: Int, gauche: Arbre, droite: Arbre) extends Arbre
case object Vide extends Arbre

object Arbre {
  def listeVersABR(l: List[Int])=(l :\ Vide.asInstanceOf[Arbre])(_ +: _)
}

Recherche dichotomique en scala

def dicho[T <% Ordered[T] ](x: T,t: Array[T]) = {
    def entre(d: Int, f: Int) : Option[Int] = {
      if (d > f) return None
      val m = (f + d) / 2
      if (t(m) == x) Some(m)
      else if (t(m) < x) entre(m + 1, f)
      else entre(d, m-1)
    }
    entre(0, t.length)
}

Einstein++: Pourquoi ne laisses-tu pas scala inférer les types là où c'est possible ? En éliminant les déclarations de types inutiles et en ajoutant quelques espaces le code serait beaucoup moins dense et plus agréable à lire.

Tri : Tri bidirectionnel

Principe et Complexité

Citation : shareman

L'une des variantes les plus connues du tri à bulles est sans doute le tri bidirectionnel ou tri Boustrophedon. D'après Wikipédia, "on qualifie de boustrophédon le tracé d'un système d'écriture qui change alternativement de sens ligne après ligne, à la manière du bœuf marquant les sillons dans les champs, de droite à gauche puis de gauche à droite". Le principe du tri à bulles bidirectionnel est justement de parcourir la liste à trier dans un sens puis dans l'autre donc en alternant le sens de passage à chaque tour. Cette technique augmente légèrement la rapidité de l'algorithme car certains éléments de la liste à trier se trouvent encore dans le buffer lors d'un passage, mais la complexité reste en O(n²).

Merci copier-coller et Shareman
Le tri à bulles

TI-basic Implémentation

:Input "MAX: ",M
:Input "Longueur",L
//L1 est la liste d'origine
//L2 est la liste pour trier
:DelVar L1
:DelVar L2
:L->dim(L1)
:L->dim(L2) 
:1->D
//La prochaine ligne calcule approximativement le nombre des pas a faire
:int(L*L/2+L)->F
:ClrHome
:Output(1,6,"/")
:Output(1,7,F)
:Output(2,1,"Remplissage aléatoire")
:For(A,1,L)
:randInt(0,M)->L1(A)
:L1(A)->L2(A)
:D+1->D
:Output(1,1,D)
:End
:1->C:1->Ø
//Le Ø est à côté du Z
:L-1->E:1->S
:0->T:0->R
//Dans la prochaine ligne, vous ajoutez des espaces apres "droite" 
//jusqu'à il n'y a plus le texte précèdent (moi il y a 11 espaces)
:Output(2,1,"tri droite           ")
//Le != signifie différent de 
:While C!= 0
:0->C
:If Ø=1:Then
:Output(2,1,"tri droite")
:For(A,S,E)
:T+1->T
:If L2(A)>L2(A+1):Then
:L2(A)->Z
:L2(A+1)->L2(A)
:Z->L2(A+1)
:R+1->R
:C+1->C
:End
:D+1->D
:Output(1,1,D)
:End
:0->Ø
:E-1->E
:End
:If Ø=0:Then
:Output(2,1,"tri gauche")
:For(A,E,S,-1)
:T+1->T
:If L2(A)>L2(A+1):Then
:L2(A)->Z
:L2(A+1)->L2(A)
:Z->L2(A+1)
:C+1->C
:R+1->R
:End
:D+1->D
:Output(1,1,D)
:S+1->S
:1->Ø
:End
:End
:ClrHome
:Output(1,1,"Le tri a dure")
:Output(2,1,D)
:Output(2,6,"étapes")
:Pause
:ClrHome
:Output(1,1,"Liste d'origine)
:Disp "
:Pause L1
:Output(3,1,"Liste trie")
:Disp "
:Pause L2
:ClrHome
:Output(1,1,"Le tri a dure")
:Output(2,1,F-D)
:Output(2,5,"etapes en")
:Output(3,1,"moins que prevu")
:Output(5,1,T)
:Output(5,6,"tests")
:Output(6,1,R)
:Output(6,6,"changements")
:Pause
:ClrHome

Je ne parle pas bien français donc s'il y a des fautes d'orthographes ou des phrases mal formulé, dites-le moi.

Un mauvais algorithme dans un mauvais langage. Il y en a pour tous les gouts !

J'ai pris ce langage parce que j'ai fait le programme sur la calculatrice en maths.
Pourquoi l'algorithme est mauvais?

Citation : Dirtcrusher

Pourquoi l'algorithme est mauvais?

Parce qu'il y en a des meilleurs.

Tu ferais mieux de suivre tes cours de maths.

Ben sans doute parce qu'il est quadratique, donc très peu performant...

Citation : yoch

Ben sans doute parce qu'il est quadratique, donc très peu performant...

Citation : victor

Parce qu'il y en a des meilleurs.

D'accord, Lequel vous me proposez?

Citation : Maxibolt

Tu ferais mieux de suivre tes cours de maths.

Je ne suis pas un savant, mais les maths de seconde sont trop facile.

Citation : Dirtcrusher

Citation : yoch

Ben sans doute parce qu'il est quadratique, donc très peu performant...

Citation : victor

Parce qu'il y en a des meilleurs.

D'accord, Lequel vous me proposez?

Tri fusion, tri rapide, tri par tas... (cf. Wikipédia)

"Je ne suis pas un savant, mais les maths de seconde sont trop faciles"

Parles-en à ton prof et fais des exos difficiles dessus

Citation : Dirtcrusher

Citation : yoch

Ben sans doute parce qu'il est quadratique, donc très peu performant...

Citation : victor

Parce qu'il y en a des meilleurs.

D'accord, Lequel vous me proposez?

J'ai présenté un "mauvais tri" ressemblant au tiens (temps quadratique) et un "bon tri" par comparaison (temps quasi-linéaire) dans le tutoriel d'algorithmique. N'hésite pas à jeter un oeil !

Citation : Maxibolt

"Je ne suis pas un savant, mais les maths de seconde sont trop faciles"

Parles-en à ton prof et fais des exos difficiles dessus

Je fait des exos de premier maintenant...

Citation : bluestorm

J'ai présenté un "mauvais tri" ressemblant au tiens (temps quadratique) et un "bon tri" par comparaison (temps quasi-linéaire) dans le tutoriel d'algorithmique. N'hésite pas à jeter un oeil !

Merci beaucoup! Maintenant je comprends pourquoi le tri bidirectionnelle est mauvais.