Win3x.Org

Windows & DOS Community

[Résolu] Calcul d'un PGCD

Post Reply   Page 1 of 1  [ 4 posts ]
Author Message
Pierreblinux
Post subject: [Résolu] Calcul d'un PGCD
Posted: 30 Apr 2011 15:06
 
 
Bonjour,
Wikipédia wrote:
En arithmétique élémentaire, le plus grand commun diviseur, abrégé en général PGCD, de deux nombres entiers naturels est le plus grand entier naturel qui divise simultanément ces deux entiers.
Étant donné que parfois j'ai pas grand chose à faire, j'ai fais un programme permettant de calculer un PGCD.
Il utilise l'algorithme des différences: PGCD (a; b) = PGCD (b; a-b)
Il tourne dans une console
#include <stdio.h>
#include <stdlib.h>
int main()
{
    printf ("Calcul d'un PGCD\n");
    printf ("Par Fujiweb, utilise l'algorithme des différences\n");
    printf ("Entrez le plus grand nombre: ");
    unsigned long premier;
    scanf ("%d", &premier);
    //On a récupéré a
    printf ("Entrez le plus petit nombre: ");
    unsigned long second;
    scanf ("%d", &second);
    //Idem pour b
    unsigned long trois;
    //Servira plus tard, ce sera a-b
    do
    {
        trois = premier - second;
        //car PGCD (a;b) = PGCD (b;a-b) si a > b
        printf ("premier %d, second %d, différence %d\n", premier, second, trois);
        //On affiche pas à pas les calculs durant les passages dans la boucle
        if (second > trois)
        {
            premier = second;
            second = trois;
        }
        else
        {
            premier = trois;
        }
        //Pour pouvoir refaire le calcul, on fais bien attention à que premier > second, pour pas foirer le calcul
    } while (trois != 0); //Quand trois = 0, le PGCD a été trouvé
    printf ("Le PGCD est: %d\n", premier);//On l'affiche
    return 0;
}
ATTENTION: L'algorithme utilisé est certe simple à programmer, mais peut être lent pour certains calculs, Je suis en train d'en faire un avec celui d'Euclide, il est plus rapide: PGCD (a; b) = PGCD (b; r), où r est le reste de a par b ( a % b = r). Je précise que ça sert à rien, la librairie math.h peut le faire :mrgreen:


Top
Quote
Galley-La Compagnie
Post subject: Re: Calcul d'un PGCD [fr]
Posted: 30 Apr 2011 18:05
Membre d'honneur
User avatar
Offline
 
Posts: 608
Joined: 19 Jun 2009 17:30
 
A la limite, un algorithme d'Euclide posé sur une feuille et voilà. :mrgreen:

_________________

[ img ]


Top
Profile Quote
Pierreblinux
Post subject: Re: Calcul d'un PGCD [fr]
Posted: 30 Apr 2011 18:40
 
 
Je voulais faire celui d’Euclide, mais il buggait, donc j'ai fais ça ;)


Top
Quote
Dr Frankenstein
Post subject: Re: Calcul d'un PGCD [fr]
Posted: 03 May 2011 19:45
Membre d'honneur
Offline
 
Posts: 418
Joined: 28 Oct 2004 01:31
 
/* Implémentation de l'algorithme d'Euclide en C.
    Carl Tessier (Dr Frankenstein), 3 mai 2011 */

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

unsigned int gcd(unsigned int a, unsigned int b)
{
    if(!a || !b)
    {
        errno = EDOM;
        return 0;
    }

    if(a < b)
    {   /* Échanger */
        a ^= b;
        b ^= a;
        a ^= b;
    }

    while(b)
    {
        unsigned int old_b = b;
        b = a % b;
        a = old_b;
    }

    return a;
}

int main(void)
{
    errno = 0;
    printf("%u\n", gcd(1071, 462));

    if(errno) perror("Erreur dans le calcul");

    return EXIT_SUCCESS;
}
EDIT: Échangé l'ordre des tests des arguments.

_________________

Introducing Windows 95.
It lets you use more than eight characters to name your files. Imagine that. ~Apple.


Top
Profile
Display: Sort by: Direction:
Post Reply   Page 1 of 1  [ 4 posts ]
Return to “Questions et problèmes résolus”
Jump to:
cron