Sedgewick2.6 (Un Caso Particular del Algoritmo de Euclides)

Ejercicio 2.6  Obtener los valores que toman u y v cuando se invoca mcd con la llamada inicial mcd(12345, 56789).

   #include <iostream>
   using namespace std;

   int mcd(int u = 12345, int v = 56789);

 
   int main()

  {

   cout <<"\n\nSe muestran los valores que toma la funcion mcd cuando se invoca";
   cout <<" con los parametros ";
   cout       <<"12345 y 56789 " << endl;

   int m;

   m = mcd();

   cout <<"\nEl maximo comun divisor es: " << m << endl;

   return 0;

  }

  int mcd ( int u, int v)

  {

   int t;

   while ( u > 0 )

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

    cout <<"u vale: " << u << "\tv vale: " << v << endl;

   }

  u = u - v;

  }

  return v;

  }

Sedgewick2.5 (Convertir de Decimal a Binario en C++)

Este programa en C++ recibe un  entero decimal y lo convierte a binario. Es interesante analizar este problema mediante el mapeo de Bernoulli, el cual hace posible realizar esta conversión de otra manera. En tanto preparo ese programa, aquí va esta versión.

El algoritmo consta de los siguientes pasos:

1) Expresar el número x como una combinación lineal de potencias de dos

x = a0*2^0 + a1*2^1 + a2*2^2 + a3*2^3 + .....

Y entonces,

mientras x != 0 se hace lo siguiente

{

Si x es impar, entonces

      el siguiente coeficiente ai es 1

      se resta 1 a x

      se divide x entre 2

Si x es par, entonces

       el siguiente coeficiente ai es 0

       se divide x entre 2

}

 

Tal vez un ejemplo sencillo sea más ilustrativo, sea x = 5

5 = a0*2^0 + a1*2^1 + a2*2^2 + a3*2^3 + ....

como el numero x es impar, entonces a0 = 1

restando 1 en ambos lados de la ecuación se tiene

4 =  a1*2^1 + a2*2^2 + a3*2^3 + ....

después se divide entre 2 ambos lados

2 =  a1*2^0 + a2*2^1 + a3*2^2 + ....

en este caso x es par, por lo cual a1 = 0

se divide todo entre 2 y queda

1 = a2*2^0 + a3*2^1 +.....

en este caso x es impar, asi que a2 = 1

se resta 1 en ambos lados y se cumple la condición de que el número x es 0. El resultado es:

a0 = 1

a1 = 0

a2 = 1

y los otros coeficientes son cero. De esta forma se ha mostrado cómo convertir de decimal a binario un número. Este algoritmo es bastante sencillo, sin embargo imprimir el equivalente binario en forma correcta es bastante más complicado. El problema es que cuando escribimos lo hacemosde izquierda a derecha, pero los números en un sistema posicional deben escribirse de derecha a izquierda, esto crea un problema con la impresión en pantalla. He decidido no complicar el programa e imprimir el número en orden inverso con una advertencia al usuario.

 #include <iostream>
 using namespace::std;
 
 // Prototipo de funcion
 void Binario(int x);

 ///////////////////////////////
 // FUNCION MAIN
 ///////////////////////////////

 int main()
 {    // Abre main
 int numero;

 cout <<"\nIntroduzca un numero entero";
 cout <<" y se imprimira su equivalente en binario. " <<endl;
 cin >> numero;

 // Se llama a la funcion Binario
 Binario(numero);

 return 0;  
 }    // Cierra main

 /////////////////////////////
 // FUNCION BINARIO
 /////////////////////////////

 void Binario( int x )
 {    // Abre funcion Binario

 cout << "\nEste numero en binario se ha imprimido invertido";
 cout << "\nLEASE AL REVES!" <<endl;

 while ( 0 != x )
 {  // Abre while
 if ( 0 != x % 2 )
 {   // Abre if
 cout << "1";
 
 x -= 1;
 x /= 2;
 
 }   // Cierra if

 else // Si el numero es par
 {  // Abre else
 cout <<"0";
 
 x /= 2;
 }  // Cierra else
 }  // Cierra while

 cout <<endl <<endl;

 }    // Cierra funcion Binario

 

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

Sedgewick2.8 (Máximo Común Divisor de Tres Números)

 //Ultima modificacion: 1 de julio de 2010
 //Este programa usa el ejemplo que viene en el capitulo 2 del libro de
 //Sedgewick, solo hay que hacer una pequena modificacion al algoritmo de
 //Euclides.
 //Nota: Este ingenioso algoritmo fue desarrollado por el matematico Euclides
 //y esta presente en los Elementos. Su problema consistia en encontrar, dada
 // dos varas de longitudes distintas, la longitud de una tercera vara con la
 // cual pudiera medirse las dos anteriores, de tal forma que esta entrara un
 // numero entero de veces tanto en una como en otra.


 #include <iostream>
 using namespace std;

 int mcd(int, int, int);


 int main()

 {
 int a, b, c, mayor, comun;

 cout << "\n\nEste programa calcula el maximo comun divisor de tres numeros. " << endl;
 cout << "Introduzca tres enteros: "<<endl;
 cin >> a >> b >> c;


 mayor = a;

 if ( b > mayor )

 {

 mayor = b;
 b = a;

 }

 if ( c > mayor )

 {

 mayor = c;
 a = mayor;

 }


 comun = mcd(mayor, b, c);

 cout <<"\nEl maximo comun divisor es: "
      <<comun << endl;

 return 0;

 }

 int mcd(int z, int u, int v)

 {
 int t, maximo;

 while (u > 0)

 {
 if (u < v)

 {
 t = u;
 u = v;
 v = t;

 if(0 == z%v)
 maximo = v;

 }

 u = u - v;

 }

 return maximo;

 }