[plutot C++]reduire une fraction

reduire une fraction [plutot C++] - Algo - Programmation

Marsh Posté le 16-08-2004 à 02:13:56    

: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:  

Reply

Marsh Posté le 16-08-2004 à 02:13:56   

Reply

Marsh Posté le 16-08-2004 à 02:46:32    

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 :
  1. void reduirefraction(int& num,int& den){
  2. if (num==0||den==0){
  3.  num=0;
  4.  den=1;
  5.  return;
  6. }
  7. if (den<0){
  8. den*=-1;
  9. num*=-1;
  10. }
  11. if (den==1)return;
  12. int sgn=(num<0?-1:1);
  13. int g=pgcd(sgn*num,den);
  14. num/=g;
  15. den/=g;
  16. }


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
Reply

Marsh Posté le 16-08-2004 à 04:51:06    

L'algo d'Euclide:

Code :
  1. int pgcd(int i, int j)
  2. {
  3.     if (i<j) swap(i,j);
  4.     if (j == 0) return i;
  5.     return pgcd(j, i%j);
  6. }


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
Reply

Marsh Posté le 16-08-2004 à 10:47:01    

Version plus compacte :

Code :
  1. int pgcd(int i, int j)
  2. {
  3. if(j == 0)
  4.   return i;
  5. else
  6.   return pgcd(j, i%j);
  7. }


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

Marsh Posté le 16-08-2004 à 14:14:03    

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

Reply

Marsh Posté le 16-08-2004 à 14:32:36    

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
Reply

Marsh Posté le 16-08-2004 à 16:02:02    

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:

Reply

Marsh Posté le 18-08-2004 à 02:43:47    

merci !!!
j'avais  

Code :
  1. int pgcd(int a,int b){
  2. int c;
  3. while (b != 0){ 
  4.        c = a%b;
  5.        a = b;
  6.        b = c;     
  7.     }
  8. return abs(a);
  9. }


Reply

Marsh Posté le 18-08-2004 à 02:57:32    

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

Reply

Marsh Posté le 18-08-2004 à 03:21:41    

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é!!!

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed