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.

Creeu un nou arxiu del tipus C anomenat m3p03.c i escriviu el següent codi:

//m3p03.c - Algorisme d'Euclides -

 

#include <stdio.h>

#include <stdlib.h>

 

 

int mcd(int,int);

 

int main(){

 

    int n,m;

 

    system("clear");

    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));

    return 0;

}

 

int mcd(int m,int n){

    int r;

 

    while(n>0){

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

    }

    return m;

}

 

 

Captura de l'execució del programa.

 

 

 

Explicació del programa

Anem a analitzar la funció mcd(). En primer lloc imaginem que m és més petit que n. En aquest cas, la primera vegada que passa pel bucle s'intercanvien aquestes dues variables i passa a ser m més gran que n. En el cas que m sigui més gran que n s'executa l'algorisme explicat al principi fins que la divisió sigui exacta, llavors surt del bucle i torna el valor de m.

    while(n>0){

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

    }

    return m;

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

Imaginem que comencem amb m=20 i n=12. Veurem un esquema dels valors de les diferents variables al començament de cada bucle:

  bucle

 m n r
1 20 12 ?
2 12 8 8
3 8 4 4
4 4 0 0

El cas n=20 i m=12 seria:

  bucle

 m n r
1 12 20 ?
2 20 12 12
3 12 8 8
4 8 4 4
5 4 0 0