Partage

Algorithmes divers multi-langage

tris, pathfinder, calcul, matrice, etc.

<< 1 ... 3 4 5 ... 9 >>

9 juillet 2009 à 16:44:29

Calcul de factorielle (déjà expliqué) mais en PHP :

<?php

/*
	Paramètre : un entier dont on cherche la factorielle.
	Type de retour : un entier.
*/

function fact($n) { //n est un entier
	if($n == 0) return 1;

	return $n * fact($n - 1);
}

/*
	Utilisation de bcmath pour gérer de grand nombres.
	Paramètre : $n le nombre dont on cherche la factorielle, sous forme de chaîne de caractère.
	Type de retour : une chaîne de cractère.
*/

function bcfact($n) {
	if($n == '0') return '1';
	
	return bcmul($n, bcfact(bcsub($n, '1')));
}

?>

Et en javascript :

function fact(n) {
	if(n == 0) return 1;
	
	return n * fact(n - 1);
}

bluestorm

9 juillet 2009 à 21:35:17

Pour information, le tutoriel d'algorithmique parle du parcours en largeur. La présentation est censée être accessible au plus grand nombre, ce qui n'est pas forcément facile, et les commentaires sont les bienvenus.

Yannshu

17 juillet 2009 à 10:31:26

Tri : Tri a bulle

Principe

Le tri a bulle est un algorithme de tri qui consiste a faire remonter successivement les éléments d'une liste pour les trier selon un ordre voulu.
Un compteur parcourt la liste d'élément a trier, et compare les maillons 2 a 2. En fonction de cette comparaison, on décide de swap les deux maillons ou non. Une fois la liste parcourue, on recommence cette operation jusqu'a ce qu'il n'y ai plus aucun swap de fait dans un parcours. Ce tri est tres simple a implementer.

Complexité

La complexite du tri a bulle est en moyenne quadratique. Elle varie entre O(n) dans le plus simple des cas, et entre O(n²) dans le pire des cas, n étant le nombre d'élément a trier.
Ceci fait de lui un des plus mauvais des algorithme de tri, ce pour quoi il est très rarement utilise en milieu professionnel.

Plus d'info :
Wikipedia
Un tutoriel par Shareman

[C] Implémentation

Tri d'un tableau d'int a une dimension.

void    swap(int *tab, int c, int c2)
{
  int   tmp;

  tmp = tab[c];
  tab[c] = tab[c2];
  tab[c2] = tmp;
}

void    ord(int *tab)
{
  int   c;
  int   c2;

  c = 0;
  while (tab[c])
    {
      c2 = c;
      while (c2 > 0 && tab[c2] < tab[c2 -1])
        {
          swap(tab, c2, c2 - 1);
          c2--;
        }
      c++;
    }
}

Tri d'un tableau d'un tableau a deux dimensions.

void    swap(char **tab, int c, int c2)
{
  char  *tmp;

  tmp = tab[c];
  tab[c] = tab[c2];
  tab[c2] = tmp;
}

void    bubble_sort(char **tab)
{
  int   c;
  int   c2;

  c = 0;
  while (tab[c])
    {
      c2 = c;
      while (c2 > 0 && strcmp(tab[c2], tab[c2 - 1]) < 0)
        {
          swap(tab, c2, c2 - 1);
          c2--;
        }
      c++;
    }
}

Découvrez un petit jeu Android bien sympa : http://www.siteduzero.com/forum/sujet/appli-jeu-android-cube-racer

shareman

19 juillet 2009 à 16:50:24

Ta définition du principe du tri à bulles n'est pas complète. Il faut préciser qu'on réitère le processus de parcours que tu décris tant qu'au moins une permutation a été faite lors du dernier passage. Ensuite, il ne serait peut-être pas trop mal d'ajouter un lien vers l'article wikipédia ou ce tutoriel, mais là c'est à toi de voir.

Ensuite, je trouve la partie sur la complexité également incomplète. Premièrement, il faut préciser que le tri à bulles est quadratique dans le cas moyen. En ne parlant que de la complexité au pire des cas, comment ferais-tu la différence entre un tri rapide et un tri à bulles ? Ensuite, quand tu dis "il est très rarement utilisé en milieu professionnel", hum, en fait il n'est jamais utilisé en milieu professionnel.

Je trouve aussi que l'implémentation que tu présentes n'est pas "adaptée" à ce topic. Premièrement d'une manière générale : tu proposes ici de trier un tableau de chaînes de caractères, et je trouve que c'est déjà trop "spécialisé" comme tri, il faut impérativement prendre quelque chose de plus basique, comme un simple tableau d'int. Puis en y regardant de plus près, l'implémentation n'est pas triviale du tout, et on ne va pas pouvoir l'adapter facilement pour trier un autre type. Je trouve ça assez dommage.

Je te demande donc avant de référencer ta présentation sur le premier post de compléter la partie "principe" ainsi que la partie "complexité" comme dit précédemment et de proposer und autre implémentation, soit pour un tableau d'entiers, soit de manière polymorphe (void*) (ce qui serait encore la meilleure chose à faire).

yoch

2 août 2009 à 4:35:00

Bonjour,

Signalons tout d'abord l'existence de cette page (je ne sais pas trop ce qu'elle vaut, certaines implémentations ne sont franchement pas terribles).

J'aimerais ajouter des implémentations de tris en C (mon langage préféré).

Tri rapide en C :

void quick_sort (int* tab, size_t sz)
{
    int *fin, *gauche, *droite, *pivot;
    int tmp;
    fin = tab+sz-1;
    if (tab < fin)
    {
        pivot = gauche = tab, droite = fin;
        /* Partitionnement */
        do
        {
            while (gauche < droite && *droite > *pivot)
                droite--;
            /* swap */
            tmp = *gauche;
            *gauche = *droite;
            *droite = tmp;
            pivot = droite;
            while (gauche < droite && *gauche <= *pivot)
                gauche++;
            /* swap */
            tmp = *droite;
            *droite = *gauche;
            *gauche = tmp;
            pivot = gauche;
        }
        while (gauche < droite);
        quick_sort(tab, gauche-tab);
        quick_sort(gauche+1, fin-gauche);
    }
}

Tri fusion en C (rapide mais couteux en mémoire):

void _merge_sort(int* tab, int* tab_cpy, const size_t sz)
{
    size_t n, i, j, mid;
    /* swap & divide */
    mid = sz/2;
    if (mid > 1) _merge_sort(tab_cpy, tab, mid);
    if (sz-mid > 1) _merge_sort(tab_cpy+mid, tab+mid, sz-mid);
    /* merge */
    int* tab_cpy2 = tab_cpy+mid;
    for (n=0, i=0, j=0; i<mid && j<sz-mid; n++)
        tab[n] = (tab_cpy[i] < tab_cpy2[j]) ? tab_cpy[i++] : tab_cpy2[j++];
    while (i<mid)
        tab[n++] = tab_cpy[i++];
    while (j<sz-mid)
        tab[n++] = tab_cpy2[j++];
}

void merge_sort (int* tab, size_t sz)
{
    int* tab_cpy = malloc(sz * sizeof *tab);
    /* copy */
    size_t i;
    for (i=0; i<sz; i++)
        tab_cpy[i] = tab[i];
    _merge_sort(tab, tab_cpy, sz);
    free(tab_cpy);
}

shareman

2 août 2009 à 12:24:27

Très intéressantes contributions.

J'en profite pour signaler que le code présenté sur ce post provoque à l'exécution des fuites de mémoire. Je vais demander à un modérateur d'éditer le code (enfin, si Floooder ne le fait pas avant ;)).

Einstein++

20 août 2009 à 3:00:10

il n' y a rien en Java ici?? c'est décevant

voici une implémentation du tri selection d'une ArrayList :

public static void triSelection(ArrayList<Integer> l,int debut,int fin){
        if(fin<=debut) return;
        else{
            int aux=l.lastIndexOf(Collections.min(l.subList(debut, fin)));
            if (l.get(debut).compareTo(l.get(aux))>0) Collections.swap(l,debut,aux );
            triSelection(l,debut+1,fin);
        }
    }

tri insertion :

public static void triInsertion(ArrayList<Integer> l){
        for(int i=1;i<l.size();i++){
            for(int j=i;j>0;j--)
                if(l.get(j).compareTo(l.get(j-1))<0) Collections.swap(l,j-1,j);
        }
    }

tri rapide:

public static void triRapide(ArrayList<Integer> l,int debut,int fin){
        if(debut<fin){
            int pivot=debut;
            for(int i=debut;i<fin;i++)
                if(l.get(i).compareTo(l.get(pivot))<0){
                    Integer aux=l.get(i);
                    l.remove(i);
                    l.add(debut, aux);
                    pivot++;
                }
            
            triRapide(l,debut,pivot);
            triRapide(l,pivot+1,fin);
        }
    }

PS: je n'ai pas utilisé des tableaux pour ne pas avoir des implémentations presque identiques à celles en C

Voici un code qui compare les vitesses des 3 tris (j'ai été choqué par la vitesse du tri rapide pour les grandes listes :waw:

)

public class ComparaisonDesTris{
    
    public static void triSelection(ArrayList<Integer> l,int debut,int fin){
        if(fin<=debut) return;
        else{
            int aux=l.lastIndexOf(Collections.min(l.subList(debut, fin)));
            if (l.get(debut).compareTo(l.get(aux))>0) Collections.swap(l,debut,aux );
            triSelection(l,debut+1,fin);
        }
    }
    public static void triInsertion(ArrayList<Integer> l){
        for(int i=1;i<l.size();i++){
            for(int j=i;j>0;j--)
                if(l.get(j).compareTo(l.get(j-1))<0) Collections.swap(l,j-1,j);
        }
    }
    public static void triRapide(ArrayList<Integer> l,int debut,int fin){
        if(debut<fin){
            int pivot=debut;
            for(int i=debut;i<fin;i++)
                if(l.get(i).compareTo(l.get(pivot))<0){
                    Integer aux=l.get(i);
                    l.remove(i);
                    l.add(debut, aux);
                    pivot++;
                }
            
            triRapide(l,debut,pivot);
            triRapide(l,pivot+1,fin);
        }
    }
    
    public static long time(){
        return System.currentTimeMillis();
    }
    public static void main(String[] args){
        long n=500;
        long d;
        System.out.println("n=="+n+" :");
        ArrayList<Integer> l1=new ArrayList<Integer>();
        for(int i=0;i<n;i++)
            l1.add((int)(Math.random()*100));
        ArrayList<Integer> l2=new ArrayList<Integer>();
        l2.addAll(l1);
        ArrayList<Integer> l3=new ArrayList<Integer>();
        l3.addAll(l1);
        d=time();
        triSelection(l1,0,l1.size());
        d=time()-d;
        System.out.println("Selection : "+d);
        d=time();
        triInsertion(l2);
        d=time()-d;
        System.out.println("Insertion : "+d);
        d=time();
        triRapide(l3,0,l3.size());
        d=time()-d;
        System.out.println("Rapide : "+d);
        n=2000;
        System.out.println("n=="+n+" :");
        for(int i=0;i<n;i++)
            l1.add((int)(Math.random()*100));       
        l2.addAll(l1);        
        l3.addAll(l1);
        d=time();
        triSelection(l1,0,l1.size());
        d=time()-d;
        System.out.println("Selection : "+d);
        d=time();
        triInsertion(l2);
        d=time()-d;
        System.out.println("Insertion : "+d);
        d=time();
        triRapide(l3,0,l3.size());
        d=time()-d;
        System.out.println("Rapide : "+d);
    }
}

</span>

Einstein++

21 août 2009 à 8:49:07

Suite de Fibonacci par exponentiation de matrice :

public static long[] produitMat(long[]m1,long[]m2) throws Exception{
        if ((m1.length!=4)||(m2.length!=4)) throw new Exception("taille non valide");
        long[]aux=new long[4];
        aux[0]=m1[0]*m2[0]+m1[2]*m2[1];
        aux[1]=m1[1]*m2[0]+m1[3]*m2[1];
        aux[2]=m1[0]*m2[2]+m1[2]*m2[3];
        aux[3]=m1[1]*m2[2]+m1[3]*m2[3];
        return aux;
    }
    public static long[] puissanceMat(long[] m,int n)throws Exception{
        if ((m.length!=4)) throw new Exception("taille non valide");
        if(n<0) throw new Exception("puissance negative");
        long[] aux=new long[4];
        if(n==0){
            aux[0]=aux[3]=1;
            aux[1]=aux[2]=0;
            return aux;
        }
        else if (n%2==0){
            aux=puissanceMat(m,n/2);
            return produitMat(aux,aux);
        }
        else{
            
            return produitMat(m,puissanceMat(m,n-1));
        }
    }
    public static long expFibo(int n){
        if(n==0) return 0;
        long[] t=new long[4];
        
        t[0]=t[1]=t[2]=1;
        t[3]=0;
        try {
            t = puissanceMat(t, n);
        } catch (Exception ex) {
            //rien a faire puisque l'exception ne sera jamais lancée
        }
        return t[1];
       
    }

et voici une autre solution pour ceux qui aiment se compliquer la vie (comme moi

) : on crée une classe Matrice et une classe MatriceCarree qui en hérite puis on utilise cette dernière dans le calcul du néme terme de la suite

class DiemensionsNonValidesException extends Exception{
    
}
class Matrice{
    private int lignes;
    private int colonnes;
    public int[][] val;
    Matrice(int lignes,int colonnes){
        this.lignes=lignes;
        this.colonnes=colonnes;
        val=new int[lignes][colonnes];
    }
    public int getLinges(){
        return lignes;
    }
    public int getColonnes(){
        return colonnes;
    }
    public static Matrice somme(Matrice m1,Matrice m2)throws DiemensionsNonValidesException{
        if ((m1.colonnes!=m2.colonnes)||(m1.lignes!=m2.lignes)) throw new DiemensionsNonValidesException();
        int[][] val=new int[m1.lignes][m1.colonnes];
        for(int i=0;i<m1.lignes;i++)
            for(int j=0;j<m2.colonnes;j++)
                val[i][j]=m1.val[i][j]+m2.val[i][j];
        Matrice resultat=new Matrice(m1.lignes,m1.colonnes);
        resultat.val=val;
        return resultat;
    }
    public static Matrice produit(Matrice m1,Matrice m2)throws DiemensionsNonValidesException{
        if (m1.colonnes!=m2.lignes) throw new DiemensionsNonValidesException();
        int[][] val=new int[m1.lignes][m2.colonnes];
        for(int i=0;i<m1.lignes;i++)
            for(int j=0;j<m2.colonnes;j++)
                for(int k=0;k<m1.colonnes;k++)
                    val[i][j]+=m1.val[i][k]*m2.val[k][j];
        Matrice resultat=new Matrice(m1.lignes,m2.colonnes);
        resultat.val=val;
        return resultat;
    }
    @Override
    public  String toString(){
        String s=new String("[");
        for(int i=0;i<lignes;i++){
              for(int j=0;j<colonnes;j++){
                   s+=val[i][j];
                   if(j!=colonnes-1)s+=",";
              }
              if(i!=lignes-1) s+="|";
        }
        return s+"]";
    }
}
class MatriceCarree extends Matrice{
    int dim;
    MatriceCarree(int dim){
        super(dim,dim);
        this.dim=dim;
    }
    public int getDim(){
        return dim;
    }
    public static MatriceCarree carre(MatriceCarree m){
        MatriceCarree resultat=new MatriceCarree(m.dim);
        try {
            resultat.val = produit(m, m).val;
        } catch (DiemensionsNonValidesException ex) {
            //rien a faire puisque l'exeption ne sera jamais lancee
        }
        return resultat;
    }
    public static MatriceCarree puissance(MatriceCarree m, int n){
        if(n==0){
            MatriceCarree resultat=new MatriceCarree(m.dim);
            for(int i=0;i<resultat.dim;i++)
                resultat.val[i][i]=1;
            return resultat;
        }
        if(n%2==0) return carre(puissance(m,n/2));
        else{
            MatriceCarree resultat=new MatriceCarree(m.dim);
            try {
               resultat.val=produit(m,puissance(m,n-1)).val;
            } catch (DiemensionsNonValidesException ex){}
            return resultat;

        }
    }
}

</span>

lmghs

25 août 2009 à 14:34:54

Pour les algos en C++, je ne peux que vous inviter à consulter Elements of Programming de Stepanov et McJones.
Le code des algos est disponible sur le site, et le contenu du livre devrait être consultable depuis safari.InformIT.

yoch

7 septembre 2009 à 16:20:20

Bonjour,

Encore quelques contributions pour les tris en langage C :

Avec les tableaux

Tri par tas

void heapsort (int* heap, size_t sz)
{
    size_t n, i, j, k, heap_sz;
    int tmp;
    /* cree un tas (maximum en tete) */
    for (heap_sz=1; heap_sz < sz; heap_sz++)
    {
        for (n = heap_sz; n; n = k)
        {
            k = (n-1)/2;
            if ( heap[n] > heap[k] )
            {
                /* swap */
                tmp = heap[n];
                heap[n] = heap[k];
                heap[k] = tmp;
            }
            else
                break;
        }
    }
    /* trie le tableau */
    while (heap_sz--)
    {
        /* swap(tete,queue) */
        tmp = heap[0];
        heap[0] = heap[heap_sz];
        heap[heap_sz] = tmp;
        /* tamise l'arbre */
        for (n = 0; (i=2*n+1) < heap_sz; n = k)
        {
            j = i+1;
            if (j < heap_sz && heap[i] < heap[j])
                k = j;
            else
                k = i;
                
            if (heap[n] < heap[k])
            {
                /* swap */
                tmp = heap[n];
                heap[n] = heap[k];
                heap[k] = tmp;
            }
            else
                break;
        }
    }
}

Tris sur listes

définition des listes

typedef struct _list
{
    int val;
    struct _list *next;
} LIST;

Tri rapide sur listes en C :

/* tri rapide sur une liste chainée - choix du pivot naïf */
LIST* _quick_sort (LIST* list, LIST* end)
{
    LIST *pivot, *tmp, *next, *prec, *suiv;
    if ( list != end && list->next != end )
    {
        /* partitionnement (fin liste 'prec' : 'pivot'; fin liste 'suiv' : 'end') */
        pivot = list, prec = pivot, suiv = end;
        for ( tmp=list->next; tmp != end; tmp=next )
        {
            next = tmp->next;
            if (tmp->val > pivot->val)
                tmp->next = suiv, suiv = tmp; /* ajoute la cellule a la liste 'suiv' */
            else
                tmp->next = prec, prec = tmp; /* ajoute la cellule a la liste 'prec' */
        }
        /* appels recursifs */
        prec = _quick_sort (prec, pivot);
        suiv = _quick_sort (suiv, end);
        /* recolle la liste */
        pivot->next = suiv;
        return prec;
    }
    return list;
}

LIST* quick_sort (LIST* list)
{
    return _quick_sort (list, NULL);
}

Tri fusion sur listes en C :

/* fusionne deux listes - pose problèmes sur très grosses listes */
LIST* fusion (LIST* list1, LIST* list2)
{
    if (list1 == NULL)
        return list2;
    else if (list2 == NULL)
        return list1;
    else if (list1->val < list2->val)
    {
        list1->next = fusion (list1->next, list2);
        return list1;
    }
    else
    {
        list2->next = fusion (list1, list2->next);
        return list2;
    }
}

/* tri fusion sur liste chainée */
LIST* _tri_fusion (LIST* list1, unsigned n)
{
    unsigned median = 0, i;
    LIST *list2 = NULL, *tmp;

    if ( n > 1)
    {
        /* merge */
        median = n/2;
        for (list2=list1, i=median; --i; list2=list2->next);
        tmp = list2->next, list2->next = NULL, list2 = tmp;

        /* sort */
        if (median > 1)
            list1 = _tri_fusion (list1, median);
        if (n-median > 1)
            list2 = _tri_fusion (list2, n-median);
        list1 = fusion (list1, list2);
    }
    return list1;
}

static unsigned nb_elements (LIST* list)
{
    unsigned ret = 0;
    while (list != NULL)
        list = list->next, ret++;
    return ret;
}

/* tri fusion sur liste chainée */
LIST* tri_fusion (LIST* list)
{
    return _tri_fusion (list, nb_elements (list));
}

EDIT : petite correction du quick sort (élimination de variables) + orthographe.

colbseton

8 septembre 2009 à 20:35:09

Bonjour,

Calculs divers : Réduction de fractions

Principe

Pour simplifier une fraction de la forme a/b. On calcule le PGCD de a et de b. Notons ce PGCD p.
On a donc PGCD(a;b) = p.
Donc la fraction peut se réduire comme ceci -> a/b = (a/p)/(b/p).

[C] Implémentation

L'implémentation est assez similaire à mon explication.

#include <stdlib.h>

int 
pgcd(int m,int n)
{
        if((m % n) == 0)
                return n;
        return pgcd(n, m % n);
}

void 
reduc(int m, int n, int a)
{
        if(n == a)
                printf("%d\n\n", m/a);
        else
                printf("%d/%d\n", m/a, n/a);
}

int 
main(void)
{
        int m = 32, n = 12;
        reduc(m, n, pgcd(m,n));
        return 0;
}

Ps : C'est le 100e post de ce topic !

colbseton

16 septembre 2009 à 19:55:19

Calculs divers : PPCM

[Python] Implémentation

Le PPCM en Python à l'aide du PGCD :

def pgcd(a,b):
          if a % b == 0 : return b
          return pgcd(b, a%b)
def ppcm(a, b):
          return (a*b) / pgcd(a, b)

[OCaml] Implémentation

Même principe qu'en Python :

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

Les codes ont l'air de fonctionner.

shareman

6 octobre 2009 à 21:08:34

Topic mis à jour (enfin) !

Merci pour ces intéressantes contributions.

Stalker

14 octobre 2009 à 16:24:30

Je pose une fonction pour Delphi(application graphique et console) au sujet de "Inverser une liste chaînée".

Function Inverser_Texte(Texte_A_Inverser : String): String;
Var
  i : Cardinal;
  Texte_Inverser : String;
Begin
  Texte_Inverser := '';

  For i := Length(Texte_A_Inverser) downto 1 Do
  Begin
    // Pour laisser la main à Windows si le mot à retourner est long
    Application.ProcessMessages; // A enlever si application console
    Texte_Inverser := Texte_Inverser + Texte_A_Inverser[i];
  End;

  Result := Texte_Inverser;
End;

Réviser avec simplicité votre vocabulaire avec Revisuic. Inscrivez-vous sur Studyuik et gérez vos données scolaire !

shareman

14 octobre 2009 à 16:33:07

Stalker : La fonction que tu présentes ne résout pas convenablement le problème : elle est en O(n²) (alors que ce qui nous intéresse pour cet algo est bien la complexité linéaire) et utilise String , ce qui ne convient naturellement pas ici.

Stalker

14 octobre 2009 à 16:57:46

Ah mince désolé. J'avais mal compris, je me suis trop accroché sur ceci :

Citation : Shareman

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.

et je n'ai pas fait attention au "O(n)", j'enlève ma fonction de ce post ?

Réviser avec simplicité votre vocabulaire avec Revisuic. Inscrivez-vous sur Studyuik et gérez vos données scolaire !

shareman

14 octobre 2009 à 17:11:44

Bah tu en fais ce que tu veux. Merci néanmoins pour ta participation.

Tu peux par contre tenter d'implémenter l'algorithme autrement, pour que je puisse le référencer.

Stalker

14 octobre 2009 à 17:17:48

Je n'ai jamais vu le "O(n)" et même sur wikipédia beaucoup de peine à comprendre donc je ne pense pas réussir tout de suite à contribuer mais ça ne veut pas dire que j'abandonne

Réviser avec simplicité votre vocabulaire avec Revisuic. Inscrivez-vous sur Studyuik et gérez vos données scolaire !

shareman

14 octobre 2009 à 17:25:01

Tu n'as pas nécessairement besoin de maîtriser en détail la notation "grand O". Tu peux tout de même comprendre en quoi un algorithme peut être plus rapide qu'un autre. Observe les implémentations déjà proposées du renversement linéaire de liste (en O(n) où n est la taille de la liste) et essaye de transposer l'idée en Delphi.

Stalker

14 octobre 2009 à 17:32:47

Je vais essayer de regarder tout ça en tout cas je comprend 3/4 du code

. Et j'ai remarquer que tout est fait en mémoire notamment grâce au pointeurs mais pas tout le temps

Réviser avec simplicité votre vocabulaire avec Revisuic. Inscrivez-vous sur Studyuik et gérez vos données scolaire !

shareman

14 octobre 2009 à 17:35:05

Oui, ça c'est le code C. L'implémentation OCaml est encore différente.

Stalker

14 octobre 2009 à 17:36:37

Mais tu peux juste m'expliquer ce que signifie "->" et le next c'est pour prendre le prochain caractère ?

Réviser avec simplicité votre vocabulaire avec Revisuic. Inscrivez-vous sur Studyuik et gérez vos données scolaire !

shareman

14 octobre 2009 à 18:10:19

Le -> permet d'accéder aux membres d'une instance de structure à partir d'un pointeur sur cette dernière. Mais pourquoi parler de "caractère" ? Je crois que tu confonds chaîne de caractères et liste chaînée.

Stalker

14 octobre 2009 à 18:29:04

Oui c'est ça, alors je suis encore plus à côté de la plaque :'(

Réviser avec simplicité votre vocabulaire avec Revisuic. Inscrivez-vous sur Studyuik et gérez vos données scolaire !

Anonyme

18 novembre 2009 à 23:47:13

Sans vouloir faire l'emmerdeur, ce topic, il sert à quelque chose ou c'est un duplicata de http://rosettacode.org/wiki/Main_Page en moins bien?

D'ailleurs, si un de vous le sent bien, il peut s'amuser à balancer les codes trouvés sur ce topic directement dans le wiki de rosettacode.

Anonyme

21 novembre 2009 à 21:10:18

JE sais pas si le but de ce topic est comment afficher une chaine à l'envers mais bon moi j'ai ça :

void chaineEnvers(char *tab)
{
    for(i=strlen(chaine);i>0;i--){
        printf ("%c",chaine[i]);
    }
}

Pouet_forever

23 novembre 2009 à 12:53:25

Impressionnant j'avais jamais vu ce topic fort intéressant

Mélange aléatoire d'une séquence

[C] Implémantation

/* Le srand devra être appelé avant l'appel de la fonction */
void shuffle(int *tab, size_t sz) {
	int a, tmp, i;
	/* On pacrours le tableau */
	for (i = 0; i < sz; i++) {
		/* On tire un nombre aléatoire entre 0 et sz-1 */
		a = ((float) rand() / RAND_MAX) * sz;
		/* On échange les valeurs */
		tmp = tab[i];
		tab[i] = tab[a];
		tab[a] = tmp;
	}
}

bluestorm

23 novembre 2009 à 13:24:23

Edit : Je me souvenais bien qu'on en avait déjà parlé ! Cet algorithme faux a déjà été traité en début de topic.

Cet algorithme est faux, la répartition n'est pas uniforme. Il suffit de tester tous les tirages aléatoires possibles sur un tableau à 3 éléments, pour voir que toutes les permutations ne sortent pas avec la même probabilité.

Voici un code de test en OCaml :

let swap tab i j =
  if i <> j then
    let temp = tab.(i) in
    tab.(i) <- tab.(j);
    tab.(j) <- temp

let shuffle_pouet tab =
  let len = Array.length tab in
  for i = 0 to len - 1 do
    swap tab i (Random.int len)
  done

let mesure shuffle len nb_iterations =
  let compte = Hashtbl.create len in
  for i = 1 to nb_iterations do
    let tab = Array.init len (fun i -> i) in
    shuffle tab;
    let ancien = try Hashtbl.find compte tab with Not_found -> 0 in
    Hashtbl.replace compte tab (ancien + 1)
  done;
  let cmp (t, n) (t', n') =
    match compare n n' with
      | 0 -> compare t t'
      | d -> d in
  List.sort cmp (Hashtbl.fold (fun k n acc -> (k, n) :: acc) compte [])

Résultat :

# mesure shuffle_pouet 3 10_000;;
- : (int array * int) list =
[([|2; 0; 1|], 1457); ([|2; 1; 0|], 1541); ([|0; 1; 2|], 1544);
 ([|1; 0; 2|], 1753); ([|1; 2; 0|], 1818); ([|0; 2; 1|], 1887)]

On remarque qu'en partant du tableau [0 1 2], les distributions [2 0 1], [2 1 0] et [0 1 2] sortent nettement moins souvent que les distributions [1 0 2], [1 2 0] et [0 2 1].

Il y a un bon algorithme de mélange de tableau en temps linéaire, le voici (la fonction "swap" vient du code précédent) :

let shuffle tab =
  let len = Array.length tab in
  for i = len - 1 downto 1 do
    swap tab i (Random.int (i + 1))
  done

Comment savoir si un algorithme de mélange de tableau est correct ? La bonne façon de faire est de se prouver qu'il marche : comment démontreriez-vous que votre algorithme renvoie toutes les permutations du tableau de départ avec la même probabilité ?

C'est très facile à montrer avec le mien : le premier élément (placé dans la dernière case du tableau) est choisi parmi tous les éléments, puis le suivant (placé dans l'avant-dernière case) parmi tous ceux qui n'ont pas encore été choisis, et ainsi de suite. Ainsi, il n'y a aucun conflit entre les différents tirages aléatoires, et chaque élément a bien été choisi au hasard parmi les éléments du tableau d'entrée (simple preuve par récurrence).

Si vous ne voyez pas comment prouver la correction de votre algorithme aléatoire, c'est sans doute qu'il est faux. En général, un test sur un assez grand nombre d'itérations suffit à le démasquer, mais certains font de bonnes approximations de répartitions et il peut être difficile de s'en apercevoir sans rédiger une vraie preuve (qu'il est faux).

Pouet_forever

23 novembre 2009 à 14:22:41

Ah oui effectivement je n'avais pas pensé à ce point là

Je n'avais pas vu la remarque que tu avais faite en début de topic, je n'ai pas tout lu :honte:

J'édite

bluestorm

23 novembre 2009 à 14:28:03

Non justement :
- tu devrais laisser ton ancien code, afin que les gens puissent lire le code faux et ne pas tomber dans le panneau la prochaine fois
- le nombre aléatoire doit être tiré entre 0 et i inclus, et pas 0 et i-1, donc ton code est encore faux

<< 1 ... 3 4 5 ... 9 >>