Partage
  • Partager sur Facebook
  • Partager sur Twitter

Algorithmes divers multi-langage

tris, pathfinder, calcul, matrice, etc.

    23 novembre 2009 à 14:47:48

    Oui c'est vrai qu'on peut aussi tirer le nombre lui-même :p
    J'ai remis mon code et je poste le nouveau ^^

    /* 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 = sz-1; i > 0; i--) {
    		/* On tire un nombre aléatoire entre 0 et i */
    		a = ((float) rand() / RAND_MAX) * (i + 1);
    		/* On échange les valeurs */
    		tmp = tab[i];
    		tab[i] = tab[a];
    		tab[a] = tmp;
    	}
    }
    

    • Partager sur Facebook
    • Partager sur Twitter
      23 novembre 2009 à 14:50:01

      Le code est encore faux :-°

      Edit : il y avait ( .. rand() .. ) * i + 1
      • Partager sur Facebook
      • Partager sur Twitter
        23 novembre 2009 à 14:58:05

        Mais non :D
        Désolé des petites fautes d'inattention ^^ (mais bon le principal c'est que je comprenne mes erreurs :) )
        Au final sur un truc tout bête j'aurais appris des trucs ^^
        Merci à toi :D
        • Partager sur Facebook
        • Partager sur Twitter
          18 décembre 2009 à 15:33:25

          Algorithme de tri : Quick Sort


          Mauvaise implémentation, je corrige dés que possible.

          Principe


          L'algorithme quicksort est un algorithme récursif qui choisit une valeur pivot, elle place toutes les valeurs plus grandes que le pivot à droite et le reste à droite. Enfin on applique la même méthode à la partie supérieure du tableau (valeurs plus grandes que le pivot) puis à la partie inférieure.

          Complexité


          La complexité de Quick Sort est en O(n*log(n)) mais dans le pire des cas sa complexité deviens en O(n²)

          [C] Implémentation



          void
          swap (void **v, int i, int j) {
              void *tmp = v[i];
              v[i] = v[j];
              v[j] = tmp;
          }
          
          void
          _qsort (void **v, int left, int right,
                  int (*comp)(void*, void*)) {
              int i, last;
          
              if (left >= right) {
                  return;
              }
              swap(v, left, (left+right)/2);
              last = left;
              for (i=left+1 ; i <= right ; i++) {
                  if ((*comp)(v[i], v[left]) < 0) {
                      swap(v, ++last, i);
                  }
              }
              swap(v, left, last);
              _qsort(v, left, last-1, comp);
              _qsort(v, last+1, right, comp);
          }
          

          • Partager sur Facebook
          • Partager sur Twitter
            5 janvier 2010 à 14:09:11

            Je ne suis pas tout à fait d'accord avec ton tri Lithrein.
            Tu considères que ta fonction 'comp' retourne quelque chose si les valeurs sont supérieures ou inférieures et tu ne fais rien si elle retourne 0.
            Le problème c'est que la fonction 'comp' retourne (normalement) une valeur négative si le paramètre testé est inférieur, nulle si le paramètre est égal, et supérieure si le paramètre est supérieur.
            Ensuite ça ne fonctionne que sur un tableau de pointeurs, il ne serait pas mieux de faire une fonction 'générique' ? (comme la fonction standard)
            Je pense que tu as un problème ici :

            for (i=left+1 ; i <= right ; i++)
            

            Il aurait fallu mettre < et pas <= ;)
            • Partager sur Facebook
            • Partager sur Twitter
              5 janvier 2010 à 18:38:54

              Merci Pouet_forever, il y avait en effet une erreur.
              La faute se situait en fait ici :
              if ((*comp)(v[i], v[left]))
              

              J'oublier de tenir compte du retour de la fonction de comparaison.
              if ((*comp)(v[i], v[left]) < 0)
              
              • Partager sur Facebook
              • Partager sur Twitter
                11 janvier 2010 à 11:45:41

                Algorithme de tri : Quicksort


                Principe


                L'algorithme de tri Quicksort est un algorithme rapide se basant sur la méthode "diviser pour régner". Il consiste à choisir un "pivot" au sein de la liste pour pouvoir diviser le reste en deux nouvelles listes, l'une contenant des éléments plus petits que le pivot et l'autre des éléments plus grands. La liste ordonnée est la concaténation suivante : Liste_elements_ppetit + pivot + Liste_elements_pgrand. On applique le tri aux deux listes ainsi obtenus et ainsi de suite jusqu'à tomber sur une liste contenant un seul élément ou une liste vide.

                Complexité


                La complexité moyenne de cet algorithme est en O(n log(n)). Toutefois, la complexité dans le pire des cas est en O(n²).

                [Python] Implémentation


                def quicksort(list):    
                    if len(list) == 1 or list==[]:
                        return list    
                    pivot = list[0]
                    return quicksort([pp for pp in list[1:] if pp < pivot])\
                            + [pivot] + \
                            quicksort([pg for pg in list[1:] if pg >= pivot])
                


                Le code présenté est ici est écrit dans un style très fonctionnel (récursivité, compréhension de liste).
                Attention au fait que les listes de Python ne sont ni de vraies listes, ni de vrais tableaux.


                [Erlang] Implémentation



                -module(quicksort).
                
                -export([part/4,tri/1]).
                
                part(L,L2,[],P) ->
                        {L , L2};
                part(L,L2,[T|Q],P) when T>P ->
                        part([T|L],L2,Q,P);
                part(L,L2,[T|Q],P) ->
                        part(L,[T|L2],Q,P).
                
                tri([]) ->
                        [];
                tri([T|Q]) ->
                        {G,P}=part([],[],Q,T),
                        tri(P)++[T|tri(G)].


                On peut aussi faire plus simple avec la compréhension de liste :

                -module(quicksort).
                
                -export([tri/1]).
                
                tri([]) ->
                        [];
                tri([T|Q]) ->        
                        tri([X || X <- Q, X<T])++[T|tri([X || X <- Q,X>=T])].


                [Prolog] Implémentation



                tri([T|Q],LT):-     %T est le pivot, Q le reste de la liste,LT la liste triée
                        part(Q,P,G,T),  %partition de la liste en deux sous-listes
                        tri(P,P2),   %tri de la liste des éléments plus petits
                        tri(G,G2),   %tri de la liste des éléments plus grands
                        append(P2,[T|G2],LT). %LT est défini par cette concaténation
                tri([],[]). %Cas particulier : tri d'une liste vide
                
                %partition d'une liste en deux sous-listes l'une contenant les éléments plus grand que le pivot et l'autre le reste :
                
                part([T|Q],P,[T|G],PV):-
                        T>PV,!,
                        part(Q,P,G,PV).
                part([T|Q],[T|P],G,PV):-
                        part(Q,P,G,PV).
                part([],[],[],_).
                • Partager sur Facebook
                • Partager sur Twitter
                  20 janvier 2010 à 17:33:57

                  A propos du tri rapide en Prolog, on gagne du temps et des inférences en utilisant le principe des différences de listes quiévite en particulier l'utilisaton coûteuse du append :
                  quicksort(Xs,Ys) :- quicksort_dl(Xs,Ys-[]).
                  
                  quicksort_dl([X|Xs],Ys-Zs)  :-
                  	partition_dl(Xs,X,Littles,Bigs),
                  	quicksort_dl(Littles,Ys-[X|Ys1]),
                  	quicksort_dl(Bigs,Ys1-Zs).
                  
                  quicksort_dl([],Xs-Xs).
                  
                  partition_dl([X|Xs],Y,[X|Ls],Bs) :-
                  	   X =< Y, !, partition_dl(Xs,Y,Ls,Bs).
                  
                  partition_dl([X|Xs],Y,Ls,[X|Bs]) :-
                  	   partition_dl(Xs,Y,Ls,Bs).
                  
                  partition_dl([],_Y,[],[]).
                  
                  On gagne un peu moins de 20 % :

                  18 ?- test.
                  % 4,225,551 inferences, 1.234 CPU in 1.241 seconds (99% CPU, 3423231 Lips)
                  % 5,306,982 inferences, 1.578 CPU in 1.571 seconds (100% CPU, 3362840 Lips)

                  Le premier tri est avec les différences de listes, le deuxième avec append.

                  Intéressante aussi est une version utilisant les DCG, trouvée sur Wilkipedia :
                  partition([], _, [], []).
                  partition([X|Xs], Pivot, Smalls, Bigs) :-
                      (   X @< Pivot ->
                          Smalls = [X|Rest],
                          partition(Xs, Pivot, Rest, Bigs)
                      ;   Bigs = [X|Rest],
                          partition(Xs, Pivot, Smalls, Rest)
                      ).
                  
                  quicksortWP([])     --> [].
                  quicksortWP([X|Xs]) -->
                      { partition(Xs, X, Smaller, Bigger) },
                      quicksortWP(Smaller), [X], quicksortWP(Bigger).
                  


                  La version est plus coûteuse en terme d'inférences mais plus rapide en exécution :
                  26 ?- test.
                  % 4,248,439 inferences, 1.250 CPU in 1.248 seconds (100% CPU, 3398751 Lips)
                  % 4,249,942 inferences, 1.016 CPU in 1.019 seconds (100% CPU, 4184558 Lips)
                  true.

                  La première est la version DL, la seconde la version DCG.

                  PS : Il y a à chaque fois 100 0000 nombres inférieurs à 100 000 à trier.
                  • Partager sur Facebook
                  • Partager sur Twitter

                  Le crayon la gomme et le papier sont les meilleurs outils du programmeur !

                    12 février 2010 à 18:14:13

                    Petite contribution :

                    Calculs Divers :PPCM


                    [C] Implémentation :



                    #include <stdio.h>
                    #include <stdlib.h>
                    
                    int pgcd(int a, int b)
                    {
                            return (a % b) ? pgcd(b, a % b) : b;
                    }
                    
                    int ppcm(int a, int b)
                    {
                            return a*b / pgcd(a, b);
                    }
                    
                    int main(void)
                    {
                            printf("%d", ppcm(10,5));
                            return 0;
                    }
                    

                    C'est plus pour remplir un peu le PPCM :p .
                    • Partager sur Facebook
                    • Partager sur Twitter
                      12 février 2010 à 19:27:45

                      Et c'est quoi le PPCM ? '-_- perso je ne connais pas ... un petit lien et explications sont le bienvenue.

                      Sans connaître ça, ton code fait des calculs inutiles :-°
                      • Partager sur Facebook
                      • Partager sur Twitter
                        12 février 2010 à 19:45:21

                        Citation : Pouet_forever

                        Et c'est quoi le PPCM ? '-_- perso je ne connais pas ... un petit lien et explications sont le bienvenue.

                        Sans connaître ça, ton code fait des calculs inutiles :-°



                        Il suffisait de regarder la première implémentation proposée pour avoir l'explication ici.
                        • Partager sur Facebook
                        • Partager sur Twitter
                          12 février 2010 à 20:58:34

                          Ok désolé ^^
                          Il manque néanmoins la valeur absolue.
                          • Partager sur Facebook
                          • Partager sur Twitter
                            15 février 2010 à 20:18:21

                            Calculs divers : Calcul de factorielle


                            Complexité


                            La complexité est en O(N).

                            [Prolog] Implémentation


                            fac(0,1).
                            fac(N,F):- 
                                    N2 is N - 1,
                                    N2 >= 0,
                                    fac(N2,F2),
                                    F is N * F2.


                            [Forth] Implémentation


                            : FAC2 DUP IF TUCK * SWAP 1 - RECURSE ELSE 1 + * THEN ;
                            : FAC 1 SWAP FAC2 ;


                            Edit :
                            Je me permet d'ajouter une implémentation en BF pour laquelle j'aimerais bien avoir votre avis.


                            [Brainf*ck] Implémentation


                            +++++    Le nombre dont on souhaite obtenir la factorielle.
                            >+<[[->>+>+<<<]>>>[-<<<+>>>]<
                            [-<[->>+>+<<<]>>>[-<<<+>>>]<<]        Multiplication
                            <[-]>>[-<<+>>]<<<-]
                            >        Cette case contient la factorielle.


                            • Partager sur Facebook
                            • Partager sur Twitter
                            Anonyme
                              15 février 2010 à 23:28:57

                              EMC1 :
                              Pour le Forth :

                              : fac ( n -- n! ) 1 swap 1+ 1 ?do i * loop ;

                              C'est pas récursif mais c'est one-liner, et pas moins puissant.

                              Au risque de me répéter, arrêtez d'utiliser ce topic. Si vous voulez être utiles, contribuez à Rosetta Code.
                              • Partager sur Facebook
                              • Partager sur Twitter
                                16 février 2010 à 12:20:27

                                Citation : victor

                                Au risque de me répéter, arrêtez d'utiliser ce topic. Si vous voulez être utiles, contribuez à Rosetta Code.


                                Pourquoi ?
                                • Partager sur Facebook
                                • Partager sur Twitter
                                Anonyme
                                  16 février 2010 à 12:51:31

                                  Citation : Colb-Seton

                                  Citation : victor

                                  Au risque de me répéter, arrêtez d'utiliser ce topic. Si vous voulez être utiles, contribuez à Rosetta Code.


                                  Pourquoi ?


                                  Parce qu'il est inutile.
                                  Il est très nettement moins complet que Rosetta Code. Du coup, dans l'intérêt de tout le monde, l'intelligence dicte de participer à Rosetta Code.

                                  (Jamais ce topic n'atteindra le quart du Rosetta.)
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    16 février 2010 à 13:13:48

                                    Parce que ce topic est moins bien que Rosetta, il n'a pas le droit d'exister ? Après tout, le SdZ a bien le droit d'avoir une ptite base de donnée ^^ .
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      16 février 2010 à 13:39:18

                                      I apologize for the English; I can't speak French, and can only barely read it.

                                      I run RosettaCode.org, and while I appreciate victor's interest and enthusiasm, I should point out that RC isn't the only programming chrestomathy on the web. We even have a page dedicated to listing other sites an efforts with similar aims: http://rosettacode.org/wiki/Help:Similar_Sites

                                      I've added this forum thread to that page. That's not to say that people here aren't welcome to contribute to RC; they are. I just don't want anyone to think that it has to be the only programming chrestomathy out there. (Though I certainly wouldn't mind it being the best!)
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                      Anonyme
                                        16 février 2010 à 17:05:37

                                        mikemol > Thanks for adding a link to this page on RC.

                                        I will translate your post for our members :

                                        Citation : mikemol

                                        Je m'excuse pour l'anglais; je ne peux pas parler français et ne peux qu'à peine le lire.

                                        Je gère RosettaCode.org, et bien que j'apprécie l'intérêt et l'enthousiasme de victor, je me dois de préciser que RC n'est pas le seul site du genre. Nous avons même une page dédiée à lister les autres sites ou efforts dont l'objectif est similaire: http://rosettacode.org/wiki/Help:Similar_Sites

                                        J'ai ajouté ce topic à cette page. Cela ne veut pas dire que les zéros ne sont pas invités à contribuer à RC, au contraire ils le sont. Je veux juste que personne ne pense que RC devrait être le seul site du genre. (Bien que ça ne me dérangerait certainement pas qu'il soit le meilleurs!)



                                        When I first ran into RC, I was obviously looking for an algorithm in a specific language. What I liked most was the wiki, and I contributed some code since.

                                        When thinking about a programming chrestomathy, I want it to be the most complete it can be. Since some members down here have some programming skills, I thought it would be preferable for everybody to contribute to your website instead of feeding this small-untested-unsorted-unpractical forum-version.

                                        I know I have been a little harsh on this topic, but it's only because I know how things works here : sometimes yelling louder than the others is THE way.
                                        I may as well start doing it myself and add every snippet from this thread to RC. I don't know yet. We'll try to have a constructive argument about this and take a decision on this thread.
                                        Anyway, thank you for your intervention

                                        Et maintenant en français :

                                        La première fois que je suis tombé sur Rosetta Code, j'étais à la recherche d'un exemple d'implémentation d'un algo dans un langage spécifique. Ce qui m'a le plus plu, c'était l'idée de wiki, et depuis j'y ai à plusieurs reprises contribué.

                                        Quand je pense à un site proposant des algos dans plusieurs langages, j'ai envie qu'il soit pratique et complet, le plus complet possible. Vu que certains zéros sont compétents niveau prog, je pense qu'il est préférable pour tous (ici et ailleurs) qu'ils contribuent à RosettaCode plutôt qu'à ce topic incomplet, pas testé, pas classé et pas pratique.

                                        Peut-être que je ferai le boulot moi-même et que j'ajouterai sur RC les snippets trouvés sur ce topic. Je ne sais pas encore. Peut-être que les contributeurs à ce topics devraient se manifester et donner leur avis, et qu'on pourrait avoir une discussion constructive à ce sujet.
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          24 février 2010 à 18:20:42

                                          Calculs divers : Distance de Levenshtein



                                          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é


                                          Temporelle : <math>\(O((m+1)\times(n+1))\)</math> où <math>\(m\)</math> et <math>\(n\)</math> représente respectivement la longueur de la première et de la seconde chaîne.
                                          Spatiale : <math>\(O(m + n + 2)\)</math> (il faudrait confirmation)

                                          Implémentation : C++


                                          #include <string>
                                          
                                          int levenshtein(const string &a, const string &b) {	
                                          	const int aSize = a.size(), bSize = b.size();
                                          	int cost = 0, d, e, f;
                                          	int *prev = new int[bSize + 1], *curr = new int[bSize + 1];
                                          	
                                          	for(int j = 0; j <= bSize; ++j) {
                                          		curr[j] = j;
                                          	}
                                          
                                          	for(int i = 1; i <= aSize; ++i) {
                                          		swap(prev, curr);
                                          		curr[0] = i;
                                          		
                                          		for(int j = 1; j <= bSize; ++j) {
                                          			if(a[i - 1] == b[j - 1]) {
                                          				cost = 0;
                                          			}
                                          			
                                          			else {
                                          				cost = 1;
                                          			}
                                          			
                                          			d = prev[j] + 1;
                                          			e = curr[j - 1] + 1;
                                          			f = prev[j - 1] + cost;
                                          		
                                          			curr[j] = (d < e) ? (d < f ? d : f) : (e < f ? e : f);
                                          		}
                                          	}
                                          	
                                          	int r = curr[bSize];
                                          	delete[] prev;
                                          	delete[] curr;
                                          	return r;
                                          }
                                          


                                          Édité suite aux remarques de lmghs.
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            24 février 2010 à 18:57:16

                                            Ce code est du C99 -- à cause du VLA. En gros, seul gcc l'acceptera, et g++ si on lui dit d'ignorer ce qui n'est pas standard.
                                            Une version C++ qui consomme moins de mémoire fut présentée ici: http://www.siteduzero.com/forum-83-463 [...] enshtein.html
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                            C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
                                              25 février 2010 à 16:52:32

                                              Là c'est valide en C++ ?
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                25 février 2010 à 17:41:21

                                                Oui, mais tu ne gagnes pas grand chose par rapport aux vecteurs (à part un risque de fuite en cas de chaine trop longue). Certes, tu ne paies pas le RAZ propre aux vecteurs, mais tu alloues 3 int au lieu de les mettre sur la pile. Le résultat peut être pire. Tu paies aussi un strlen que tu connais certainement déjà ; quitte à être en C++ autant utiliser des std::string.

                                                Si tu dois l'utiliser en boucle et que l'allocateur de tes vecteurs gèrent mal les pools le mieux (en termes de perfs, tout en restant dans les limites du standard (cf les posts de galopin sinon)) est de sortir les vecteurs de la fonction qui se contentera juste de faire un resize sur ce nouveau paramètre.
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
                                                  26 février 2010 à 20:59:01

                                                  J'ai remis une version avec des strings qui sera surement la plus pratique pour ceux qui passeront ici, s'ils veulent une version plus rapide suffit de lire un peu le topic pour avoir une idée de ce qu'il faut faire.

                                                  Citation

                                                  Le résultat peut être pire


                                                  Après de rapides tests ça n'est pas "peut être", mais "est pire".

                                                  Citation

                                                  Tu paies aussi un strlen que tu connais certainement déjà


                                                  Yeap je l'avais caché mais pas utilisé :euh:

                                                  Pour ce qui est des pools, en en utilisant un pour les tableaux (donc appel à new seulement si on a besoin d'un tableau > que celui dont on dispose déjà) c'est en effet très rapide (puisque moins d'appel à new/delete) niveau temps je passes d'une dizaine de minutes à 7min 30s (25% de gagné). Par contre c'est pas super propre (du moins de la manière dont je l'ai fait => c'est global, mais bon comme c'est pour un besoin précis c'est pas trop grave).
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    27 février 2010 à 2:56:39

                                                    Il n'est pas impossible que ton implémentation de vector implémente déjà un pool pour toi. Parfois c'est le cas.
                                                    Après il y a toujours moyen de gratter des pouillèmes en faisant sauter le branchement conditionnel.
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                    C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
                                                      5 mars 2010 à 10:35:50

                                                      Citation : jaguar001

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

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

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

                                                      ...

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




                                                      Salut,

                                                      Je trouve cette méthode très peu fiable, car un débordement est très vite arrivé.

                                                      Exemple :
                                                      printf("%f\n", arrondir(1234.56789,10000000000));
                                                      

                                                      sortie:
                                                      -1.522967


                                                      Personnellement, je verrais plutôt quelque chose du genre :

                                                      #include <math.h>
                                                      
                                                      double arrondi (double nb, size_t nbdec)
                                                      {
                                                          return nb - fmod(nb, 1./pow(10.,nbdec));
                                                      }
                                                      


                                                      J'ai modifié le prototype de la fonction, le deuxième paramètre représente ici le nombre de décimales voulu (question de gout).
                                                      Avec ton prototype, le code est encore plus simple :
                                                      return nb - fmod(nb, 1./precision);


                                                      Il existe surement d'autres recettes, je n'ai pas encore cherché.


                                                      EDIT:

                                                      A la réflexion, le code ci-dessus n'a pas grand intérêt, sachant que l'on peut généralement régler la précision a l'affichage (printf).
                                                      De plus, j'ai confondu troncature et arrondi. Le prototype de jaguar001 correspond mieux a l'arrondi, car on peut faire par exemple arrondir(1234.56789,20); pour avoir une précision de l'ordre de 0.05.

                                                      Il m'a semblé plus intéressant de donner une fonction qui arrondisse a la précision la plus proche. Comme par exemple l'arrondi classique des supermarchés 11.92 -> 11.90 et 11.93 -> 11.95.

                                                      Et voici le code avec un exemple (le prototype a encore changé) :
                                                      #include <math.h>
                                                      
                                                      double arrondi (double nb, double prec)
                                                      {
                                                          double reste = fmod(nb, prec);
                                                          return (2*reste >= prec) ? nb-reste+prec : nb-reste;
                                                      }
                                                      
                                                      int main (void)
                                                      {
                                                          printf("%f\n", arrondi(11.92,0.05));
                                                          printf("%f\n", arrondi(11.93,0.05));
                                                          return 0;
                                                      }
                                                      


                                                      EDIT 2:

                                                      2e methode :

                                                      double arrondi (double nb, double prec)
                                                      {
                                                          nb += prec/2;
                                                          return nb - fmod(nb, prec);
                                                      }
                                                      
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        7 mars 2010 à 0:00:47

                                                        Dites, pour calculer une racine carré ça vous convient ça :
                                                        def racine(x):
                                                            if x < 0:
                                                                x = -x
                                                                print "-%si" % (x**(1.0/2.0))
                                                            else:
                                                                print x**(1.0/2.0)
                                                        

                                                        Si les instructions pour x < 0 vous plaise pas, j'peux changer.
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          7 mars 2010 à 11:34:19

                                                          Aucun interet, tu utilises l'opérateur puissance de ton langage...
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            14 mars 2010 à 9:00:31

                                                            Conversion base 10 vers base n (langage C)



                                                            Écrit dans une chaine :
                                                            void uintToStringInBase (unsigned n, char* str, unsigned base)
                                                            {
                                                                if (n >= base)
                                                                    uintToStringInBase (n/base,str+1,base);
                                                                else
                                                                    *(str+1) = 0;  /* termine la chaine */
                                                                *str = '0' + n%base;
                                                            }
                                                            


                                                            Affiche dans la console :
                                                            void putUintInBase(unsigned n, unsigned base)
                                                            {
                                                                if (n >= base)
                                                                    putUintInBase(n/base, base);
                                                                putchar('0' + n%base);
                                                            }
                                                            

                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              14 mars 2010 à 9:38:41

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

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

                                                              Je pense que ce genre d'algorithmes n'a pas vraiment de sens si on ne prend pas une représentation adaptée des données, qui :
                                                              - soit adaptée pour stocker des nombres potentiellement grands
                                                              - soit adatpée pour stocker des bases potentiellement grandes
                                                              • 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