Calcul du pgcd de 2 nbres par soustraction (avec les calcules intermédiaires)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 5 546 fois - Téléchargée 30 fois

Contenu du snippet

Bas ce code permet,comme l'explique le titre, de calculer le PGCD de deux nombres entiers avec la méthode de la soustraction et avec tous les calcules intermédiaires.

Je sais que ce n'est pas follichon, mais bon je suis débutant et j'ai eu à mes débuts du mal à trouver des codes sources clairs , bien expliqués et surtout à mon niveau.
Donc je pense quil en faut kan même, et que entre autre celui ci pourra bien servir à ceux qui débute.

Source / Exemple :


////////////////////////////////////////////////////////////////////////////
///////////        Fais avec Dev c++ 4 par Gulius        //////////////////
//////////    Il existe bcp d'autres solutions et surement      /////////
/////// des plus faciles mais bon je suis débutant donc j'essaye.////
///////////////////////////////////////////////////////////////////////////

#include <iostream> // pour utiliser les entrées et sorties cout et cin
using namespace std;

int main()          //Début de la fonction principale
{
    int a, b, pg, pp, res; //Définition des variables
    cout << "Ce Programme calcule"    //Message d'explication
    << " le PGCD de deux nombres . \n" 
    << "Entrez deux nombres a et b :\n " 
    <<"Entrez a : " << endl;
    cin >> a;                // Entrée du 1er nombre
    cout << "Entrez b : " << endl;
    cin >> b;                //Entrée du seconde nombre
    cout << " " << endl;
    
    if (a<b) pp=a, pg=b;        // On regarde quel est le plus gd 
    else if (b<a) pp=b, pg=a;  //nombre des 2 et on les places ds 
    else                      //deux variable pp et pg
    { pg=a, pp=b;            //(pp= plus petit et pg= plus grand
   
     cout << "\nCes deux nombres sont egaux donc " // Si les 2 nbres 
    << "leurs PGCD est ce meme nombre ." << endl; // sont déjà egaux,
    }                // on indique que leur PGCD est ce même nombre
                                                                                       
    
    while(true)      // boncle infinie (j'aurais pu faire avec un for 
                    // ou un while "fini" )
    {   res = pg-pp; // On calcule (plus grand nbr) - (le plus petit)
        
        if (pp!=pg) // si pp est différent de pg, on indique
        {           // le résultat du clacul
        cout << pg << "-" << pp << "= " << res << endl;
        if(res>pp) pg=res; // on change les variables celon 
        else if(res<pp) pg=pp, pp=res; //le plus grand nombre
        else  pp=res, pg=pp;           // de res et de pp.
        }  //Puis on les replace ds pg et pp et on recommence
        else                        
        {                                       
         cout << pg << "-" << pp << "= 0"<< endl; 
         break;  //On casse la boucle si pp==pg
        }
        
    }
   
                        /*On indique le résultat*/
    cout << "Le PGCD de " << a << " et " << b << " est " << pp << " " << endl;    
    if(res==1) cout << "Ces deux nombres sont donc premiers. " << endl;
    
    system("pause");
    return 0;
}

Conclusion :


Le code a été donc édité et compilé with devc++4 et pi voila tout;
N'hésitez pas à me faire part de vos remarques et tout et tout....merci

A voir également

Ajouter un commentaire

Commentaires

Messages postés
337
Date d'inscription
jeudi 19 décembre 2002
Statut
Membre
Dernière intervention
15 avril 2006

ah oui...je voulais rajouter pour ceux qui s'interesse a l'algo AKS pour les premiers que bout de code est tres interressant vu kil permet de trouver le PGCD d'un tres grand nombre et d'un petit très rapidemment

@+
Messages postés
337
Date d'inscription
jeudi 19 décembre 2002
Statut
Membre
Dernière intervention
15 avril 2006

Salut,


je ne connaissais pas cette algo pour les pgcd il a l'air de tendre vite vers le nombre chercher...

Seulement niveau performance ton code est pas top...

si j'ai bien compris tu dois chercher remplacer le plus grand par le reste de la division et jusqu'à ce que ce reste soit nul...l'opérateur modulo est "%"

Je trouvais cette algo tres interressant et je me suis permis de l'accélérrer de facon assez significative... le voici, il y a 3 méthode, celle presente plus haut, la mienne en c++ et la meme en ASM...les mesure sont avec :

#include <windows.h>
#include // pour utiliser les entrées et sorties cout et cin
using namespace std;

int PGCDXbY(int pp, int pg)
{
int res=1;
while (res)
{
res = pg % pp;
pg = pp;
pp = res;
};
return pg;
}
int PGCDXbYasm(int pp, int pg)
{
__asm{
mov eax, pg;
mov ebx, pp;
boucle:
xor edx,edx;
div ebx;
mov eax, ebx;
mov ebx, edx;
test edx, edx;
jne boucle;
mov pg, eax;
mov pp, ebx;
}
return pg;
}
int PGCD(int pp, int pg)
{
int res=1;
while(true) // boncle infinie (j'aurais pu faire avec un for
// ou un while "fini" )
{
res = pg-pp; // On calcule (plus grand nbr) - (le plus petit)
if (res) // si pp est différent de pg, on indique
{ // le résultat du clacul
if(res>pp) pg=res; // on change les variables celon
else if(res> a; // Entrée du 1er nombre
cout << "Entrez b : " << endl;
cin >> b; //Entrée du seconde nombre
cout << " " << endl;

if (a<b) pp=a, pg=b; // On regarde quel est le plus gd
else if (b<a) pp=b, pg=a; //nombre des 2 et on les places ds
else //deux variable pp et pg
{ pg=a, pp=b; //(pp= plus petit et pg= plus grand

cout << "\nCes deux nombres sont egaux donc " // Si les 2 nbres
<< "leurs PGCD est ce meme nombre ." << endl; // sont déjà egaux,
} // on indique que leur PGCD est ce même nombre
/*On indique le résultat*/
itération = 100
for (int j=0;j<5;j++)
{
tps=0;
for(int i=0;i<itération;i++)
{
__asm
{
rdtsc;
mov cycle,eax;
}
res=PGCD(pp, pg);
__asm
{
rdtsc;
sub eax,cycle;
add tps,eax;
}
};
tps /= itération;

cout << "Le PGCD de " << a << " et " << b << " est " << res << " en " << tps << "cycle" << endl;

tps=0;
for(int i=0;i<itération;i++)
{
__asm
{
rdtsc;
mov cycle,eax;
}
res=PGCDXbYasm(pp, pg);
__asm
{
rdtsc;
sub eax,cycle;
add tps,eax;
}
};
tps /= itération;

cout << "Le PGCD(XbY ASM) de " << a << " et " << b << " est " << res << " en " << tps << "cycle" << endl;

tps=0;
for(int i=0;i<itération;i++)
{
__asm
{
rdtsc;
mov cycle,eax;
}
res=PGCDXbY(pp, pg);
__asm
{
rdtsc;
sub eax,cycle;
add tps,eax;
}
};
tps /= itération;

cout << "Le PGCD(XbY) de " << a << " et " << b << " est " << res << " en " << tps << "cycle" << endl << endl;

};
system("pause");
return 0;
}

Voila J'espere que g pas code de connerie... il fait 5 fois chaque code pour avoir une meilleur idée des perormance à cause de la gestion d threads windows.

@+

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.