dont ask to ask
|
Reprise du dernier message de la page précédente :
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 
|
Trance forever :)
|
Oui c'est vrai qu'on peut aussi tirer le nombre lui-même 
J'ai remis mon code et je poste le nouveau 
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13 | /* 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;
}
}
|
Tuto sur le préprocesseur C
Pourquoi en vieillissant les biscuits durs deviennent mous et les biscuits mous deviennent durs ?
Est-ce que le mot «tumeur» a été inventé par un médecin qui aime l'humour noir? 
warning: target of assignment not really an lvalue; this will be a hard error in the future
|
dont ask to ask
|
Le code est encore faux 
Edit : il y avait ( .. rand() .. ) * i + 1
|
Trance forever :)
|
Mais non 
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
Tuto sur le préprocesseur C
Pourquoi en vieillissant les biscuits durs deviennent mous et les biscuits mous deviennent durs ?
Est-ce que le mot «tumeur» a été inventé par un médecin qui aime l'humour noir?
warning: target of assignment not really an lvalue; this will be a hard error in the future
|
日本へ行きたい。
|
Algorithme de tri : Quick Sort
Mauvaise implémentation, je corrige dés que possible.
Secret (cliquez pour afficher)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
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | 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);
}
|
Édité
le 12/02/2010 à 20:45:19
par Lithrein
|
Trance forever :)
|
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 :
Code : C | for (i=left+1 ; i <= right ; i++)
|
Il aurait fallu mettre < et pas <=
Tuto sur le préprocesseur C
Pourquoi en vieillissant les biscuits durs deviennent mous et les biscuits mous deviennent durs ?
Est-ce que le mot «tumeur» a été inventé par un médecin qui aime l'humour noir?
warning: target of assignment not really an lvalue; this will be a hard error in the future
|
日本へ行きたい。
|
Merci Pouet_forever, il y avait en effet une erreur.
La faute se situait en fait ici :
Code : C | if ((*comp)(v[i], v[left]))
|
J'oublier de tenir compte du retour de la fonction de comparaison.
Code : C | if ((*comp)(v[i], v[left]) < 0)
|
Édité
le 05/01/2010 à 18:39:27
par Lithrein
|
|
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
Code : Python | 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
Code : Autre1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| -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 :
Code : Autre1
2
3
4
5
6
7
8
| -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
Code : Autre1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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([],[],[],_). |
Édité
le 13/01/2010 à 16:03:56
par EMC1
|
|
|
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 :
Code : Zcode 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | 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 :
Code : Zcode 1
2
3
4
5
6
7
8
9
10
11
12
13 | 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.
Édité
le 21/01/2010 à 13:20:42
par joel76
|
|
Petite contribution :
Calculs Divers :PPCM
[C] Implémentation :
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | #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 .
|
Trance 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
Tuto sur le préprocesseur C
Pourquoi en vieillissant les biscuits durs deviennent mous et les biscuits mous deviennent durs ?
Est-ce que le mot «tumeur» a été inventé par un médecin qui aime l'humour noir?
warning: target of assignment not really an lvalue; this will be a hard error in the future
|
|
Citation : Pouet_foreverEt 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.
|
Trance forever :)
|
Ok désolé
Il manque néanmoins la valeur absolue.
Tuto sur le préprocesseur C
Pourquoi en vieillissant les biscuits durs deviennent mous et les biscuits mous deviennent durs ?
Est-ce que le mot «tumeur» a été inventé par un médecin qui aime l'humour noir?
warning: target of assignment not really an lvalue; this will be a hard error in the future
|
|
Calculs divers : Calcul de factorielle
Complexité
La complexité est en O(N).
[Prolog] Implémentation
Code : Autre1
2
3
4
5
6
| fac(0,1).
fac(N,F):-
N2 is N - 1,
N2 >= 0,
fac(N2,F2),
F is N * F2. |
[Forth] Implémentation
Code : Autre1
2
| : 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
Code : Autre1
2
3
4
5
| +++++ Le nombre dont on souhaite obtenir la factorielle.
>+<[[->>+>+<<<]>>>[-<<<+>>>]<
[-<[->>+>+<<<]>>>[-<<<+>>>]<<] Multiplication
<[-]>>[-<<+>>]<<<-]
> Cette case contient la factorielle. |
Édité
le 24/02/2010 à 19:55:51
par EMC1
|
est beau !
|
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.
Dans le classement des pays européens les plus innovants, la Suisse est en tête aux côtés du Danemark, de la Finlande, de l’Allemagne, de la Suède et du Royaume-Uni. Selon le TBEI, tous ces pays leaders fournissent dans le domaine de l’innovation des prestations nettement au-dessus de la moyenne par rapport aux autres pays européens. Les résultats pour la Suisse sont extrêmement réjouissants. Ils traduisent clairement les points forts d’une économie compétitive sur le plan international et pouvant compter sur un savoir performant.
T'aimes ça les photos, hein t'aimes ça, hein?
et café-clope de s'exclamer : bien-penseance m'a tuer
et le roi des lents sur son trône, il est suisse ça j'en suis sur
Nowhere to run, Nowhere to hide
Javier Flutine Crew presents : Poneys pom pom tchi !
Citation : 21:44:09 Elentar: mon bac vaut bien quelques chatons
Citation : La pizza 4 saisons enfourne des javiers sauvages
Citation : Makkhdynj'avais gravé mon iPod avec "MakkhPod", mais après coup j'ai regretté puisqu'il était devenu impossible a vendre et j'ai été obligé de le refiler a mon frère...
Soap&Skin Soap&Skin is the name taken by Anja Plaschg Anja Plaschg, an 18 year old Austrian woman, for her spellbinding music. Her music is darkly gothic and seemingly intensely personal, a combination of Bjork, Cat Power and Lisa Gerrard. And definitely Nico – she appeared in ‘Nico - Sphinx aus Eis’ in Berlin last year, she sounds like her a lot, and her titles are very Nico-ish: ‘Thanatos’, ‘Extinguish Me’ and Marche Funèbre’. Looking, on the sleeve, like some rebellious heroine in a Bronte novel, her art appears drawn from her life: the daughter of pig farmers near Graz, she had unconventional looks and ignored music until her teens when she practiced piano and violin compulsively, wrote her own classical pieces for school and enrolled at the Academy of Fine Arts in Vienna when 16.
These songs were composed between 2005 and 2008. Mostly it’s her with piano and electronica backing. ‘Cry Wolf’ has a folky charm, akin to Cat Power, with lovely flutes and piano, while the following ‘Thanatos’ is a polar opposite: “nature’s own delirium/ cause of my oblivion” she sings in a deathly monotone redolent of the Femme Fatale herself. ‘Cynthia’ is gloomy but the darkness hides a sweet melody and 'Turbine Womb' has the same classical elegance as Dead Can Dance, while ‘Spiracle’ has bizarre lyrics but the most accessible construction. This is a haunted debut that paints the most powerful crepuscular tones you’ve heard in a long time.
Anja Plaschg Anja Plaschg
Soap&Skin
|
|
Citation : victorAu risque de me répéter, arrêtez d'utiliser ce topic. Si vous voulez être utiles, contribuez à Rosetta Code.
Pourquoi ?
|
est beau !
|
Citation : Colb-SetonCitation : victorAu 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.)
Dans le classement des pays européens les plus innovants, la Suisse est en tête aux côtés du Danemark, de la Finlande, de l’Allemagne, de la Suède et du Royaume-Uni. Selon le TBEI, tous ces pays leaders fournissent dans le domaine de l’innovation des prestations nettement au-dessus de la moyenne par rapport aux autres pays européens. Les résultats pour la Suisse sont extrêmement réjouissants. Ils traduisent clairement les points forts d’une économie compétitive sur le plan international et pouvant compter sur un savoir performant.
T'aimes ça les photos, hein t'aimes ça, hein?
et café-clope de s'exclamer : bien-penseance m'a tuer
et le roi des lents sur son trône, il est suisse ça j'en suis sur
Nowhere to run, Nowhere to hide
Javier Flutine Crew presents : Poneys pom pom tchi !
Citation : 21:44:09 Elentar: mon bac vaut bien quelques chatons
Citation : La pizza 4 saisons enfourne des javiers sauvages
Citation : Makkhdynj'avais gravé mon iPod avec "MakkhPod", mais après coup j'ai regretté puisqu'il était devenu impossible a vendre et j'ai été obligé de le refiler a mon frère...
Soap&Skin Soap&Skin is the name taken by Anja Plaschg Anja Plaschg, an 18 year old Austrian woman, for her spellbinding music. Her music is darkly gothic and seemingly intensely personal, a combination of Bjork, Cat Power and Lisa Gerrard. And definitely Nico – she appeared in ‘Nico - Sphinx aus Eis’ in Berlin last year, she sounds like her a lot, and her titles are very Nico-ish: ‘Thanatos’, ‘Extinguish Me’ and Marche Funèbre’. Looking, on the sleeve, like some rebellious heroine in a Bronte novel, her art appears drawn from her life: the daughter of pig farmers near Graz, she had unconventional looks and ignored music until her teens when she practiced piano and violin compulsively, wrote her own classical pieces for school and enrolled at the Academy of Fine Arts in Vienna when 16.
These songs were composed between 2005 and 2008. Mostly it’s her with piano and electronica backing. ‘Cry Wolf’ has a folky charm, akin to Cat Power, with lovely flutes and piano, while the following ‘Thanatos’ is a polar opposite: “nature’s own delirium/ cause of my oblivion” she sings in a deathly monotone redolent of the Femme Fatale herself. ‘Cynthia’ is gloomy but the darkness hides a sweet melody and 'Turbine Womb' has the same classical elegance as Dead Can Dance, while ‘Spiracle’ has bizarre lyrics but the most accessible construction. This is a haunted debut that paints the most powerful crepuscular tones you’ve heard in a long time.
Anja Plaschg Anja Plaschg
Soap&Skin
|
|
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 .
|
|
|
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!)
|
est beau !
|
mikemol > Thanks for adding a link to this page on RC.
I will translate your post for our members :
Citation : mikemolJe 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 since I contributed some code.
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 if they were contributing to your website instead of feeding this small-untested-unsorted-unpractical 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 it works.
I may as well start doing it myself and add every snippet from to thread to RC. I don't know yet. We'll try to have a constructive argument about his and take a decision about 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.
Dans le classement des pays européens les plus innovants, la Suisse est en tête aux côtés du Danemark, de la Finlande, de l’Allemagne, de la Suède et du Royaume-Uni. Selon le TBEI, tous ces pays leaders fournissent dans le domaine de l’innovation des prestations nettement au-dessus de la moyenne par rapport aux autres pays européens. Les résultats pour la Suisse sont extrêmement réjouissants. Ils traduisent clairement les points forts d’une économie compétitive sur le plan international et pouvant compter sur un savoir performant.
T'aimes ça les photos, hein t'aimes ça, hein?
et café-clope de s'exclamer : bien-penseance m'a tuer
et le roi des lents sur son trône, il est suisse ça j'en suis sur
Nowhere to run, Nowhere to hide
Javier Flutine Crew presents : Poneys pom pom tchi !
Citation : 21:44:09 Elentar: mon bac vaut bien quelques chatons
Citation : La pizza 4 saisons enfourne des javiers sauvages
Citation : Makkhdynj'avais gravé mon iPod avec "MakkhPod", mais après coup j'ai regretté puisqu'il était devenu impossible a vendre et j'ai été obligé de le refiler a mon frère...
Soap&Skin Soap&Skin is the name taken by Anja Plaschg Anja Plaschg, an 18 year old Austrian woman, for her spellbinding music. Her music is darkly gothic and seemingly intensely personal, a combination of Bjork, Cat Power and Lisa Gerrard. And definitely Nico – she appeared in ‘Nico - Sphinx aus Eis’ in Berlin last year, she sounds like her a lot, and her titles are very Nico-ish: ‘Thanatos’, ‘Extinguish Me’ and Marche Funèbre’. Looking, on the sleeve, like some rebellious heroine in a Bronte novel, her art appears drawn from her life: the daughter of pig farmers near Graz, she had unconventional looks and ignored music until her teens when she practiced piano and violin compulsively, wrote her own classical pieces for school and enrolled at the Academy of Fine Arts in Vienna when 16.
These songs were composed between 2005 and 2008. Mostly it’s her with piano and electronica backing. ‘Cry Wolf’ has a folky charm, akin to Cat Power, with lovely flutes and piano, while the following ‘Thanatos’ is a polar opposite: “nature’s own delirium/ cause of my oblivion” she sings in a deathly monotone redolent of the Femme Fatale herself. ‘Cynthia’ is gloomy but the darkness hides a sweet melody and 'Turbine Womb' has the same classical elegance as Dead Can Dance, while ‘Spiracle’ has bizarre lyrics but the most accessible construction. This is a haunted debut that paints the most powerful crepuscular tones you’ve heard in a long time.
Anja Plaschg Anja Plaschg
Soap&Skin
|
1 23 / 4 5 * 6 - 78 9 - * *
|
Calculs divers : Distance de Levenshtein
Principe
Citation : WikipediaLa 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 :  où  et  représente respectivement la longueur de la première et de la seconde chaîne.
Spatiale :  (il faudrait confirmation)
Implémentation : C++
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | #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.
Édité
le 26/02/2010 à 20:42:55
par cerium50
|
|
|
|
1 23 / 4 5 * 6 - 78 9 - * *
|
|
|
|
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.
|
1 23 / 4 5 * 6 - 78 9 - * *
|
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.
CitationLe résultat peut être pire
Après de rapides tests ça n'est pas "peut être", mais "est pire".
CitationTu paies aussi un strlen que tu connais certainement déjà
Yeap je l'avais caché mais pas utilisé 
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).
|
|
|
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.
|
|
Citation : jaguar001Methode 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é
...
Code : C | 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 :
Code : C | printf("%f\n", arrondir(1234.56789,10000000000));
|
sortie:
Code : Console
Personnellement, je verrais plutôt quelque chose du genre :
Code : C | #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é) :
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14 | #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;
}
|
| double arrondi (double nb, double prec)
{
nb += prec/2;
return nb - fmod(nb, prec);
}
|
Édité
le 06/03/2010 à 19:32:13
par yoch
|
|
|
Dites, pour calculer une racine carré ça vous convient ça :
Code : Python | 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.
Connait => xHTML/CSS/JS/Mirc Scripting (beuark)/Python
A touché à => C/Java (en cours d'apprentissage)/shell/lua/batch (beuark)
Utilise GTK comme Qt, mais a une préférence pour Qt.
Parle à la troisième personne pour faire son Alain Delon
|
|
Aucun interet, tu utilises l'opérateur puissance de ton langage...
|
|
Conversion base 10 vers base n (langage C)
Écrit dans une chaine :
Code : C | 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 :
Code : C | void putUintInBase(unsigned n, unsigned base)
{
if (n >= base)
putUintInBase(n/base, base);
putchar('0' + n%base);
}
|
Édité
le 14/03/2010 à 09:01:56
par yoch
|
dont ask to ask
|
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
|
bluestorm
Twitter
Facebook