domingo, 31 de octubre de 2010

Deitel_C++_3.32 (Máximo Común Divisor en C++)

_____________________________________________________________________________________
3.32 El máximo común divisor (mcd) de dos enteros es el entero más grande que divide cada uno de los números. Escriba una función mcd que devuelva el máximo común divisor de dos enteros.
_____________________________________________________________________________________
solución:
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 gcd se ordenan los números al final, de tal manera que al principio del ciclo la variable u es siempre el número mayor y la variable v 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 GCD                                 *
  *                                                                            *
  *  RECIBIR UN PAR DE NUMEROS COMO ARGUMENTOS                                 *
  *  U  =  EL NUMERO MAYOR                                                     *
  *  V  =  EL NUMERO MENOR                                                     *
  *                                                                            *
  *  MIENTRAS U > V                                                            *
  *        SI U ES DIVISIBLE ENTRE V                                           *
  *        {                                                                   *
  *        EL MAXIMO CUMUN DIVISOR ES V (LA FUNCION DEVUELVE EL CONTROL)       *
  *        }                                                                   *
  *                                                                            *
  *        DE LO CONTRARIO (SI U NO ES DIVISIBLE ENTRE V)                      *
  *        {                                                                   *
  *        EL NUEVO MAYOR U = ANTIGUO MENOR                                    *
  *        EL NUEVO MENOR v = ANTIGUO MAYOR - ANTIGUO MENOR                    *
  *                                                                            *  
  *        SI V > U {                                                          *   
  *        NUEVO MAYOR = V                                                     *
  *        NUEVO MENOR = U  }                                                  *
  *        }                                                                   *
  *                                                                            *          
  *++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/                         
 
#include <iostream>                             
using namespace std;             
                              
////////////////////////////////////////////////////////////////
// PROTOTIPO DE FUNCION GCD
////////////////////////////////////////////////////////////////
int gcd (int,int);             
               
               
///////////////////////////////////////////////////////////////
// FUNCION MAIN
///////////////////////////////////////////////////////////////

int main()              
               
{               
               
int number1, number2, mcd;            
               
cout <<endl<<endl<<"Introduzca un par de enteros para saber su maximo comun divisor."<< endl;     
cin >> number1>> number2;            
              
if (number1 == number2)                           
mcd = number1;             
                              
if (0 == number1 || 0== number2)         
mcd = (0 == number1)? number2:number1;          
               
                              
else
{   //Abre else           
if (number1 > number2)            
mcd = gcd (number1, number2);           
               
else                              
mcd = gcd (number2, number1);           
               
}  //Cierra else             
               
cout <<"\nEl maximo comun divisor es:" << mcd << endl;      
               
return 0;              
                              
}               
               
/////////////////////////////////////////////////////////
// FUNCION GCD QUE CALCULA EL MAXIMO COMUN DIVISOR
/////////////////////////////////////////////////////////

int gcd (int u, int v)          
                           
{  // Abre gcd              
int temp;              
               
while (u>v)              
               
{  // Abre while              
if (0 == u%v)            
return v;              
               
temp = u;             
u = v;             
v = temp - u;           
               
if (v > u) {temp=v; v=u;u = temp; }       
}   // Cierra while
                               
}   // Cierra gcd
               

No hay comentarios:

Publicar un comentario

Related Posts Plugin for WordPress, Blogger...