Enrere Mòdul 3
Fonaments de Programació. Llenguatge C/C++---
Pràctica  Resum teòric Exercicis
Pràctica d'ampliació

 
Algorisme d'Euclides

Un dels algorismes més coneguts i més senzills que es poden posar com exemple de sentències de control de flux és l'algorisme d'aquest gran matemàtic i filòsof de l'antiguitat. Aquest algorisme es fa servir per calcular el màxim comú divisor de dos nombres enters.

 

Desenvolupament de la pràctica

L'algoritme d'Euclides per calcular el màxim comú divisor de dos nombres enters és el següent:

Donats dos nombres enters m i n ( suposant m>=n) es divideix m entre n. Si la resta r de la divisió és 0, el divisor n és el MCD, en cas contrari, n es converteix en dividend i r en divisor. Tornem a fer la divisió i repetim el mateix procés. 

En el següent programa es crea una funció anomenada mcd() que fa servir aquest algorisme.

Definiu un projecte nou anomenat m3p03 i afegiu-li un arxiu de font C/C++ anomenat m3p03.cpp. Escriviu el següent codi:

//m3p03.cpp: Algorisme d'Euclides

 

#include<stdio.h>

 

int mcd(int,int);

 

void main(){

 

    int n,m;

    printf("Introduïu dos nombres enters separats per un
            espai\n");

    scanf("%d %d",&n,&m);
    printf("\n\nmcd(%d,%d) = %d\n",n,m,mcd(n,m));

}

 

 

int mcd(int m,int n){

    int r;

 

    r=(m>n)?n:m;
    m=(m>n)?m:n;
    n=r;
    while(m>0){

        r=m%n;
        n=m;
        m=r;

    }

    return n;

}

Explicació del programa

Anem a analitzar la funció mcd(). En primer lloc assigna a la variable m el número més gran de entre els arguments de la funció i a n  el més petit. Això es fa en aquestes tres línies que fan servir l'operador ternari:

        r=(m>n)?n:m;
        m=(m>n)?m:n;
        n=r;

A continuació, hi ha una sentència while amb tot l'algorisme d'Euclides explicat abans:

    while(m>0){

       r=m%n;
       n=m;
       m=r;

    }

    return n;

Recordeu que l'expressió % torna la resta de la divisió entera entre m i n. Aquest bucle acaba en el moment que aquesta resta sigui 0.