1. Accueil
  2. Tous les snippets
  3. Snippets C / C++ / C++.NET
  4. Fonction itérative(très rapide) pour trouver le pgcd et le ppcm [tout compilateur]

Fonction itérative(très rapide) pour trouver le pgcd et le ppcm [tout compilateur]

Soyez le premier à donner votre avis sur cette source.

Snippet vu 11 638 fois - Téléchargée 36 fois

Commenter

Contenu du snippet

Deux petit fonction utile pour certain algo.

Point fort :
- avec deux nombre entre 999 millions et 100 millions le programme met une seconde(xp2400+) pour executer l'operation 1 million de fois. Bref, c'est rapide.

REMARQUE : La fonction PGDC avait d'abort été fait en récursif puis suite au conseil de BruNews je l'ai refaite en itératif.

Source / Exemple : 


#include <stdio.h>
#include <stdlib.h>

//La fonction PGDC en récursif
/*
long PGCD(long a, long b, long r)
{
    if (!r) return b;
    PGCD(b,r,b%r);
}


  • /


//La fonction PGDC en itératif

long PGCD(long a, long b)
{
    long r;
   
    r=a%b;

    while(r)
    {
      a=b;
      b=r;
      r=a%b;
    }    
    return b;
}

long PPCM(long a, long b)
{
    return (a*b)/PGCD(a,b);
}

int main()
{
    printf("%d\n",PGCD(731371571,775515735));  //,731371571%775515735
    printf("%d\n",PPCM(731371571,775515735));
    system("pause");
}

Conclusion :


Compatible tout compilateur avec quelque petite adaptation au pire.

A voir également

Ajouter un commentaire Commentaires
cs_nEUrOne
Messages postés
41
Date d'inscription
dimanche 17 novembre 2002
Statut
Membre
Dernière intervention
14 avril 2004
3 mars 2003 à 13:14
BruNews: y'a pas un moyen d'enlever le modulo ?
BruNews
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
 19
2 mars 2003 à 23:36
Et une derniere forme en 64 bits pour varier.
typedef unsigned _int64 _ui64_;

_ui64_ Pgcd(_ui64_ nbr1, _ui64_ nbr2) // plus grand commun diviseur
{
_ui64_ tmp;
if(!nbr1 || !nbr2) return 0xFFFFFFFFFFFFFFFF; // si erreur
if(nbr1 < nbr2) {tmp nbr1; nbr1 nbr2; nbr2 = tmp;}
for(;;) {
if((tmp nbr1 % nbr2) 0) return nbr2;
nbr1 nbr2; nbr2 tmp;
}
}
ciao...
BruNews
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
 19
2 mars 2003 à 23:26
DWORD __stdcall euclid(DWORD x, DWORD y)
{
DWORD t;
if(!x || !y) return 0xFFFFFFFF;
do {
if(x < y) {
t x; x y; y = t;
}
x -= y;
} while(x);
return y;
}

ou en + meticuleux

__declspec (naked) DWORD __stdcall euclid(DWORD x, DWORD y)
{
__asm {
mov ecx, [esp+4] ; x
mov eax, [esp+8] ; y
or ecx, ecx
jz short euclERR
or eax, eax
jz short euclERR
euclNEXT:
cmp ecx, eax
mov edx, eax
jae short noswap
mov eax, ecx
mov ecx, edx
noswap:
sub ecx, eax
jnz short euclNEXT
ret 8
euclERR:
or eax, -1
ret 8
}
}
et d'autres versions a la pelle. Recursion n'est pas a bannir, mais faut toujours regarder si pas moyen de l'enlever.
ciao...
TheBabyCool
Messages postés
34
Date d'inscription
dimanche 2 septembre 2001
Statut
Membre
Dernière intervention
4 mars 2003
2 mars 2003 à 23:00
???
BruNews
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
 19
2 mars 2003 à 22:29
Supprime recursivite et vitesse *= 2 au moins.
ciao...
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (TheBabyCool)