viernes, 7 de enero de 2011

Sedgewick2.1 (Algorimo de Euclides en C++)

Máximo común divisor de dos números usando el algoritmo de Euclides
Este programa utiliza el hecho de que el máximo común divisor de un par de enteros es igual al máximo común divisor de el número menor y la diferencia entre el mayor y el menor. De esta forma el problema se puede ir reduciendo cada vez. Por ejemplo, el mcd(54,48) = mcd(48,6) = 6
o mcd(54,14) = mcd(14,40) = mcd(14, 26) = mcd(14, 12) = mcd(12, 2) = 2
Hay que observar que en la diferencia de los números puede ser mayor que el número menor (como la diferencia de 54 y 14, que es mayor a 14). Por sencillez, en el ciclo while de la función mcd se ordenan los números al final, de tal manera que al principio del ciclo la variable x es siempre el número mayor y la variable y es el menor.

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 * ESTE PROGRAMA CALCULA EL MAXIMO COMUN DIVISOR DE DOS NUMEROS +
 *                                                              +
 * LO QUE RECIBE: DOS NUMEROS ENTEROS                           +
 * LO QUE DEVUELVE: EL MAXIMO COMUN DIVISOR                     +
 *                                                              +
 * +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

 /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  *                                                                            *
  *                               ALGORITMO:                                   *
  *                                                                            *
  *                      EN EL BLOQUE PRINCIPAL:                               *
  *  PEDIR DOS NUMEROS                                                         *
  *  RECIBIR LOS DOS NUMEROS                                                   *
  *                                                                            *
  *  SI LOS NUMEROS SON IGUALES                                                *
  *  EL MAXIMO CUMUN DIVISOR ES CUALQUIERA DE LOS NUMEROS                      *
  *                                                                            *
  *  SI ALGUNO DE LOS DOS NUMEROS ES IGUAL A CERO                              *
  *     EL MAXIMO COMUN DIVISOR ES EL NUMERO DISTINTO DE CERO                  *
  *                                                                            *
  *  DE LO CONTRARIO (CORRESPONDIENTE AL SI INMEDIATAMENTE PRECEDENTE)         *
  *     CALCULAR ES MAXIMO COMUN DIVISOR DE LOS NUMEROS (MEDITANTE GCD         *
  *____________________________________________________________________________*
  *  
  *                                                                            *
  *                          EN LA FUNCION MCD                                 *
  *                                                                            *
  *  RECIBIR UN PAR DE NUMEROS COMO ARGUMENTOS                                 *
  *  X  =  EL NUMERO MAYOR                                                     *
  *  Y  =  EL NUMERO MENOR                                                     *
  *                                                                            *
  *  MIENTRAS X > Y                                                            *
  *        SI X ES DIVISIBLE ENTRE Y                                           *
  *        {                                                                   *
  *        EL MAXIMO CUMUN DIVISOR ES X (LA FUNCION DEVUELVE EL CONTROL)       *
  *        }                                                                   *
  *                                                                            *
  *        DE LO CONTRARIO (SI U NO ES DIVISIBLE ENTRE Y)                      *
  *        {                                                                   *
  *        EL NUEVO MAYOR U = ANTIGUO MENOR                                    *
  *        EL NUEVO MENOR v = ANTIGUO MAYOR - ANTIGUO MENOR                    *
  *                                                                            *  
  *        SI Y > X {                                                          *   
  *        NUEVO MAYOR = Y                                                     *
  *        NUEVO MENOR = X  }                                                  *
  *        }                                                                   *
  *                                                                            *          
  *++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/  
#include <iostream>
 using namespace std;

 int mcd(int, int );

 int  main()
 {          /*Abre main */

   int x, y;

   cout <<"\n\nIntroduzca tantos pares de numeros positivos  como quiera " <<endl;
   cout <<"para saber su maximo comun divisor. " << endl;
   cout << "\n(Teclee una letra para terminar). " << endl;

   while ( cin >> x && cin >> y )

   if ( x > 0 && y > 0 )
   cout << x << " " << y << " " << " su maximo comun divisor es : " << mcd(x,y) << endl;

   return 0;
  }     /*Cierra main */


 //////////////////////////////////////////////////////////////////
 // FUNCION MCD
 //////////////////////////////////////////////////////////////////

  int mcd(int u, int v)

  {
   int t;

   while ( u > 0)
   {

   if ( u < v )
   {
    t = u;
    u = v;
    v = t;
   }

   u = u - v;
  }
  
  return v;
  }

No hay comentarios:

Publicar un comentario

Related Posts Plugin for WordPress, Blogger...