Algo

[plutot C++]reduire une fraction

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [plutot C++]reduire une fraction

lunarnet76

:pt1cable: Salut a tous! :bounce:
J'ai un enorme probleme... j'ai fait par moi-meme plusieurs algorithmes de reduction de fraction mais... g toujours des problemes pour les grands nombre (genre 1054479878/154564561) alors quelqu'un aurait il un algorithme a me proposé?
parce que j'ai beau cherché ils sont tous assez "gourmand"!
Merci!!!
:bounce:

Publicité

lunarnet76

héhé je sens que je vais me faire lynché car je vais répondre a ma question ... g retrouvé un vieux fichier avec un algorithme parfait ou quasiment :

Code :

void reduirefraction(int& num,int& den){
if (num==0||den==0){
num=0;
den=1;
return;
}
if (den<0){
den*=-1;
num*=-1;
}
if (den==1)return;
int sgn=(num<0?-1:1);
int g=pgcd(sgn*num,den);
num/=g;
den/=g;
}

mais en fait j'ai un probleme pour avoir l'algorithme du plus grand commun denominateur!!!

Message édité par lunarnet76 le 16-08-2004 à 03:07:10

dividee

L'algo d'Euclide:

Code :

int pgcd(int i, int j)
{
if (i<j) swap(i,j);
if (j == 0) return i;
return pgcd(j, i%j);
}

Tu peux facilement le transformer en itératif si tu veux; je l'ai mis en récursif car c'est plus court à écrire...

Edit: grrr.. Comment on fait pour indenter proprement dans ce forum ?

Message édité par dividee le 16-08-2004 à 04:53:09

Ace17

Version plus compacte :

Code :

int pgcd(int i, int j)
{
if(j == 0)
return i;
else
return pgcd(j, i%j);
}

Message édité par Ace17 le 16-08-2004 à 10:47:21

dividee

Oui mais tu introduis la précondition i>=j, ce qui ne fait que repousser une partie du code vers le client...

Ace17

dividee a écrit :

Oui mais tu introduis la précondition i>=j, ce qui ne fait que repousser une partie du code vers le client...

Non, faux. Evidemment que ca marche meme si j est supérieur a i!

Message édité par Ace17 le 16-08-2004 à 14:32:49

dividee

Tu as raison :jap: . Si j>i, i%j == i et le premier appel récursif se charge de faire l'échange... J'aurais du le voir :sweat:

lunarnet76

merci !!!
j'avais

Code :

int pgcd(int a,int b){
int c;
while (b != 0){
c = a%b;
a = b;
b = c;
}
return abs(a);
}

lunarnet76

euh en fait j pense que mon algo est meilleur parce qu'il n'y a pas de récurrence...
vous pensez pas?

lunarnet76

dividee a écrit :

L'algo d'Euclide:
Tu peux facilement le transformer en itératif si tu veux;

:pt1cable: :bounce: j'avais pas comprit ce que ca voulait dire, lol, g vu un mot compliqué alors j'ai pas cherché!!!

FORUM HardWare.fr

Programmation

Algo

[plutot C++]reduire une fraction

Sujets relatifs
[Oracle 8.1.7] : réduire la taille d'un datafile	[VB Excel] Comment inhiber les boutons "fermer","reduire"...
comment reduire un programme dans la systray?	Filemaker : script pour reduire une image
comment réduire la taille d'un datafile RBS ?	fonction de simplification de fraction ??
reduire taille de fichier word	Vos trucs pour réduire la taille de votre executable
Comment reduire l'espace entre...	Comment réduire ce bout de code ?
Plus de sujets relatifs à : [plutot C++]reduire une fraction

Page générée en 0.051 secondes