Ejemplos capítulos 10 y 11

Ejemplo 11.1

En el capítulo 10 sobre los arrays vimos cómo ordenarlo usando el método de la burbuja. Hay muchas formas de ordenar un array pero el objetivo suele ser siempre el mismo: poder localizar o al menos determinar si existe, un determinado valor dentro del array.

Hay varios métodos de búsqueda, pero el más conocido, es el de la "Búsqueda binaria" o "Busca dicotómica". Se trata además, un método muy bueno de búsqueda, ya que el tiempo de búsqueda dismiluye exponencialmente con el número de iteraciones.

La idea es sencilla, se elige el elemento central del rango en el que debemos buscar. Pueden pasar tres cosas:

  • Que el elemento elegido sea el buscado, con lo que ha terminado la búsqueda.
  • Que el elemento elegido sea menor que el buscado, en ese caso, tomaremos el elemento siguiente al elegido como límite inferior de un nuevo rango, y repetiremos el proceso.
  • Que el elemento elegido sea mayor. Ahora tomaremos el elemento anterior al elegido como nuevo límite superior de un nuevo rango, y repetiremos el proceso.

El proceso termina cuando encontramos el elemento, o cuando el rango de búsqueda resulte nulo, y la búsqueda habrá fracasado.

// Búsqueda binaria
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream> 
using namespace std;

int Binaria(int*, int, int, int);

int tabla[] = {
      1,   3,  12,  33,  42,  43,  44,  45,  54,  55,
     61,  63,  72,  73,  82,  83,  84,  85,  94,  95,
    101, 103, 112, 133, 142, 143, 144, 145, 154, 155,
    161, 163, 172, 173, 182, 183, 184, 185, 194, 195
};

int main() {
    int pos;
    int valor=141;

    pos = Binaria(tabla, valor, 0, sizeof(tabla)/sizeof(tabla[0])-1);
    if(pos > 0) cout << "Valor " << valor << " encontrado en posicion: " << pos << endl;
    else cout << "Valor " << valor << " no encontrado" << endl;
    return 0;
}

/* Función de búsqueda binaria:
   Busca el "valor" dentro del vector "vec" entre los márgenes
   inferior "i" y superior "s" */
int Binaria(int* vec, int valor, int i, int s) {
    int inferior = i;
    int superior = s;
    int central;

    do {
        central = inferior+(superior-inferior)/2;
        if(vec[central] == valor) return central;
        else if(vec[central] < valor) inferior = central+1;
        else superior = central-1;
    } while(superior >= inferior);
    return -1;
}

Ejecutar este código en codepad.

En el capítulo 24 veremos otro modo de implementar esta función, usando recursividad.

Ejemplo 11.2

Ya sabemos que el tamaño de los números enteros está limitado en C++. Con enteros de 64 bits con signo, el número más grande es 9223372036854775808, es decir, 19 dígitos.

En general, veremos que esto es más que suficiente para casi todas nuestras aplicaciones, pero es posible que a veces necesitemos más dígitos.

Hacer un programa que pueda sumar numeros enteros sin signo, almacenados en forma de cadena. La longitud de la cadena se almacenará en una constante cadmax de modo que pueda cambiar a nuestra conveniencia. En principio, usaremos 32 caracteres. Si el resultado no cabe en cadmax caracteres, retornar con false para indicar un error de desbordamiento. Si el resultado es correcto, retornar true.

Piensa sobre el problema, a partir de este punto lo analizaremos y sacaremos conclusiones para diseñar nuestro programa.

Lo primero que hay que tener en cuenta es que almacenamos los números en forma de caracteres, lo que es poco eficaz, pero es un ejercicio...

Cada carácter es un dígito, y para hacer la suma, empezaremos a sumar dígito a dígito, empezando por la derecha. Así, '1'+'1' debe dar '2'. Pero ya sabemos que se trata de códigos ASCII, de modo que si sumamos normalmente, tendremos que restar el valor ASCII de '0':

cout << char('1'+'1') << endl;

El resultado de esta operación es 'b'.

cout << char('1'+'1'-'0') << endl;

Y el resultado de esta es '2'.

Hay otro problema añadido. Si la suma de los dígitos es mayor que '9', no tendremos un dígito:

cout << char('7'+'8'-'0') << endl;

El resultado de esta suma es '?'. No es que el compilador no sepa sumar. Lo que pasa es que se ha producido un desbordamiento. 7+8 son 15, es decir, 5, "y nos llevamos 1". Ese 1 es un desbordamiento o acarreo. Es decir, debemos tener en cuenta el acarreo en la suma del siguiente dígito. La operación se complica un poco más:

int acarreo=0;
int resultado = char('7'+'8'-'0'+acarreo);
if(resultado < '9') { resultado-=10; acarreo = 1; }
else acarreo = 0;
cout << resultado << endl;

El segundo detalle a considerar es que empezar a recorrer cadenas desde la derecha no es tan simple como pueda parecer al principio, sobre todo si las cadenas tienen distinta longitud.

const unsigned int cadmax = 32;
typedef char numero[cadmax];
numero suma;
numero n1 = "8988989";
numero n2 = "7763";

Si queremos sumar n1 y n2, deberemos empezar por los dígitos '9' y '3', respectivamente, es decir, por n1[6] y n2[3]. El resultado se almacena en la posición 6 de la cadena suma. Pasamos al siguiente dígito: n1[5] y n2[2], etc. Cuando llegamos a n1[3] y n2[0] tropezamos con un problema. El siguiente dígito de n2 no existe. Cuando pase eso, para cualquiera de las dos cadenas, deberemos tomar el valor '0' para esos dígitos.

Aún hay otro inconveniente que debemos salvar. Por ejemplo:

const unsigned int cadmax = 32;
typedef char numero[cadmax];
numero suma;
numero n1 = "9";
numero n2 = "3";

En este caso, el resultado de '9'+'3' es '2' y el acarreo queda con valor 1. La cadena resultante contiene "2", que evidentemente es un resultado erróneo. En este caso, deberemos desplazar todos los dígitos de suma a la derecha, y añardir el dígito '1' al principio.

Por último, hay un caso especial más. Supongamos que el resultado de la suma de los dos números no cabe en el número de caracteres usado para almacenarlos. En ese caso, debemos retornar false.

El resultado es un programa como este:

// Sumar números enteros sin signo almacenados en cadenas
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream>

using namespace std;

const unsigned int cadmax = 32;
typedef char numero[cadmax];

bool Sumar(numero, numero, numero);
int max(int, int);

int main()
{
    numero n1="999999999999999999";
    numero n2="1";
    numero suma;

    Sumar(n1, n2, suma);
    cout << n1 << " + " << n2 << " = " << suma << endl;
    return 0;
}

bool Sumar(numero n1, numero n2, numero r) {
    // Primero, buscar los dígitos de la derecha:
    char c1,c2;
    int acarreo = 0;
    int lon1=strlen(n1);
    int lon2=strlen(n2);
    // Colocar el terminador de la cadena resultado:
    r[max(lon1, lon2)] = 0;
    // Hacer la suma, digito a digito:
    do {
        lon1--;
        lon2--;
        if(lon1 < 0) c1 = '0'; else c1 = n1[lon1];
        if(lon2 < 0) c2 = '0'; else c2 = n2[lon2];
        r[max(lon1, lon2)] = acarreo+c1+c2-'0';
        if(r[max(lon1, lon2)] > '9') { r[max(lon1, lon2)]-=10; acarreo=1; }
        else acarreo = 0;
    } while(lon1 > 0 || lon2 > 0);

    // Desbordamiento:
    if(acarreo) {
        if(strlen(r) < cadmax) {
            for(int i=strlen(r)+1; i > 0; i--) r[i] = r[i-1];
            r[0] = '1';
            return false;
        }
    }
    return true;
}

int max(int a, int b) {
    if(a > b) return a;
    return b;
}

Ejecutar este código en codepad.

Ejemplo 11.3

Seamos más inteligentes con el uso de recursos. Usando caracteres, cada byte puede almacenar sólo diez valores diferentes. Una cadena de 32 bytes puede almacenar números positivos sin signo hasta 1032 dígitos (eso sin tener en cuenta el caracter nulo usado como fin de cadena). Pero si aprovechamos cada bit, con cada carácter hay 256 posibilidades, en lugar de 10, y el resultado es que podemos almacenar números hasta 25632, o lo que es lo mismo, 2256. Eso significa, enteros con 77 dígitos significativos.

Escribamos el programa anterior aprovechando cada bit. Por comodidad, usaremos el modo de almacenamiento Little-Endian.

Nota: en un ordenador hay dos formas ordenadas de almacenar números de más de un byte (desordenadas hay más).
La primera forma es la que usamos nosotros para escribir números sobre el papel o en una pantalla: primero el de mayor peso, y al final, el de menor peso. En el número 1234, el '1' tiene mayor peso (1000) que el 4 (1). A esta forma se le llama "Big-Endian", y es la que usan (en binario) los procesadores de la familia de Motorola.
La segunda forma es la contraria: primero el de menor peso, y al final, el de mayor. A esta forma se le llama "Little-Endian, y es la que usan los procesadores de la familia Intel. En esta forma, un número de 32 bits como 0xa3fda382 se guarda como 82, a3, df, a3, usando posiciones de memoria consecutivas.

El formato Little-Endian tiene la ventaja, para nosotros, de que es más facil sumar números usando índices que crecen en el orden natural, de menor a mayor. La desventaja es que, cuando se usan enteros con signo, éste se almacena en el último lugar.

La aritmética binaria hace que, además, nuestro programa sume correctamente tanto números positivos como negativos, algo que no pasaba en el ejemplo anterior.

La rutina de suma se simplifica notablemente, aunque no será tan sencillo visualizar los resultados. Además, deberemos usar unsigned char para almanenar los datos, con el fin de que los resultados de las sumas no se convientan en negativos al sumar ciertos valores positivos.

typedef unsigned char numero[cadmax];
...
bool Sumar(numero n1, numero n2, numero r) {
    int acarreo = 0;
    int c;

    for(unsigned int i = 0; i < cadmax; i++) {
        c = acarreo+n1[i]+n2[i];
        if(c > 0xff) { c-=256; acarreo=true; }
        else acarreo=false;
        r[i] = c;
    }
    return !acarreo;
}

Evidentemente, visualizar en pantalla números almacenados en este formato es un problema. Tendremos que calcular el módulo de dividir entre 10 sucesivamente para obtener los dígitos decimales de derecha a izquierda. Hasta ahora sólo sabemos sumar, lo que convierte este problema en algo no trivial.

Ejemplo 11.4

Vamos a trabajar ahora un poco con estructuras. Crearemos una estructura sencilla para almacenar fracciones:

struct fraccion {
    int num;
    int den;
};

Ya dije que sería sencilla.

Bueno, este ejemplo consiste en crear un programa que simplifique fracciones, o más concretamente, que use una función que devuelva una fracción simplificada de la que proporcionamos como parámetro de entrada.

Repasemos un poco. Para cada fracción existe un número infinitos de equivalencias, basta multiplicar el numerador y el denominador por un mismo número:

  1     2     3     4      5
 --- = --- = --- = --- = ---- = ...
  2     4     6     8     10

Simplificar una fracción significa expresarla de la forma más simple, es decir, para los valores mínimos de numerador y denominador.

Para ello necesitamos encontrar el máximo común divisor (MCD) del numerador y del denominador, es decir, el mayor número entero que divide tanto al numerador como al denominador.

Generalmente, el método consiste en descomponer en factores primos los dos números y seleccionar todos los comunes. Su producto será el MCD.

Esto es lo que haremos con nuestro programa:

// Simplificación de fracciones
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace <i>std</i>;

struct fraccion {
    int num;
    int den;
};

fraccion Simplificar(fraccion);

int MCD(int, int);

int main() {
    fraccion f, s;
    f.num = 1204;
    f.den = 23212;

    s = Simplificar(f);
    cout << "Simplificar(" << f.num << "/" << f.den << ") = "; 
    cout << s.num << "/" << s.den << endl;

    return 0;
}

fraccion Simplificar(fraccion f) {
    int mcd = MCD(f.num,f.den);
    f.num /= mcd;
    f.den /= mcd;
    return f;
}

int MCD(int n1, int n2) {
    // Buscar los factores primos que dividen tanto a n1 como a n2
    int resultado = 1; // El 1 siempre es un CD
    int factor = 2;    // Empezamos en 2

    while(factor <= n1 || factor <= n2) {
        while(!(n1 % factor) && !(n2 % factor)) {
            resultado *= factor;
            n1 /= factor;
            n2 /= factor;
        }
        if(factor == 2) factor++;  // Si factor es 2, el siguiente primo es 3
        else factor+=2;            // Si no, elegimos el siguiente número impar
    }
    return resultado;
}

Ejecutar este código en codepad.

Ejemplo 11.5

Siguiendo con este tema, ahora que sabemos simplificar fracciones, vamos a hacer un programa que las sume.

Volviendo al repaso, recordemos que sólo es posible sumar dos fracciones si tienen el mismo denominador. En ese caso, basta con sumar los numeradores, y mantener el denominador común.

Generalmente, se usan dos métodos para sumar dos fracciones. Uno consiste en calcular el mínimo común denominador de las dos fracciones, recalcular los numeradores de las dos fracciones equivalentes, y finalmente sumarlas.

   n1     n2     n1*mcd/d1     n2*mcd/d2     n1*mcd/d1+n2*mcd/d2
  ---- + ---- = ----------- + ----------- = ---------------------
   d1     d2        mcd           mcd               mcd

El segundo método consiste en encontrar un común denominador más sencillo, que es directamente el producto de los denominadores, y simplificar, si es posible, la fracción resultante:

   n1     n2     n1*d1*d2/d1     n2*d1*d2/d2     n1*d2     n2*d1     n1*d2+n2*d1
  ---- + ---- = ------------- + ------------- = ------- + ------- = ------------- => Simplificar
   d1     d2        d1*d2           d1*d2        d1*d2     d1*d2        d1*d2

Usaremos este segundo método:

// Suma de fracciones
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;

struct fraccion {
    int num;
    int den;
};

fraccion Simplificar(fraccion);
fraccion Sumar(fraccion, fraccion);
int MCD(int, int);

int main() {
    fraccion f, g, s;

    f.num=10;
    f.den=3;
    g.num=5;
    g.den=6;
    s = Sumar(f, g);
    cout << "Sumar(" << f.num << "/" << f.den << "," << g.num << "/" << g.den << ") = ";
    cout << s.num << "/" << s.den << endl;

    return 0;
}

fraccion Simplificar(fraccion f) {
    int mcd = MCD(f.num,f.den);
    f.num /= mcd;
    f.den /= mcd;
    return f;
}

int MCD(int n1, int n2) {
    // Buscar los factores primos que dividen tanto a n1 como a n2
    int resultado = 1; // El 1 siempre es un CD
    int factor = 2;    // Empezamos en 2

    while(factor <= n1 || factor <= n2) {
        while(!(n1 % factor) && !(n2 % factor)) {
            resultado *= factor;
            n1 /= factor;
            n2 /= factor;
        }
        if(factor == 2) factor++;  // Si factor es 2, el siguiente primo es 3
        else factor+=2;            // Si no, elegimos el siguiente número impar
    }
    return resultado;
}

fraccion Sumar(fraccion f1, fraccion f2) {
    fraccion resultado;

    resultado.num = f1.num*f2.den+f1.den*f2.num;
    resultado.den = f1.den*f2.den;
    return Simplificar(resultado);
}

Ejecutar este código en codepad.

Comentarios de los usuarios (12)

Fabian
2010-09-03 17:26:44

En el Ejemplo 11.1 estas usando punteros cuando aún no lo has mensionado (creo), yo hice el mismo ejemplo pero en lugar de:

int Binaria(int*, int, int, int);

yo he puesto:

int Binaria(int [], int, int, int);

y más abajo en la función he puesto:

int Binaria(int vec[], int valor, int i, int s) {

Al final el resultado es el mismo, pero porque usar punteros aqui?? que beneficios tiene?

Alejandro
2010-09-14 18:03:57

Hola, decirte que es lo mismo int[], que int*, ambos son punteros, ya que el nombre de un vector simplemente es un puntero que apunta al primer elemento del vector.

Saludos

Salvador Pozo
2010-09-14 18:17:02

Tienes razón, Fabian. He usado punteros antes de explicarlos.

En la siguiente revisión moveré ese ejemplo a capítulos posteriores.

Gracias.

Martín
2011-02-14 07:05:08

La verdad que en el 11.1 no entendi como usa lo de inferior y superior, y porque el valor de superior es sizeof(tabla)/sizeof(tabla[0])-1

Steven
2011-02-14 07:49:46

Hola Martín,

Las variables 'inferior' y 'superior' son usadas como índices en el array 'vec'. Inicialmente, 'inferior' es el índice del primer elemento, que es el índice 0; y 'superior' es el índice al último elemento, que en este caso es 39. En este ejemplo, en lugar de indicar 39 explícitamente hemos decidido calcularlo para que sirva para cualquier caso en general. Por eso hemos escrito:

sizeof(tabla)/sizeof(tabla[0]) - 1

Te aconsejo que consultes el capítulo 10 acerca de este uso de 'sizeof' con arrays. El enlace es: http://c.conclase.net/curso/?cap=010#Array_operadores

El algoritmo en 'Binaria()' básicamente va dividiendo el array en mitades. Si no encontramos el valor que buscamos, entonces elegimos la primera mitad, si el valor es menor al valor central, o elegimos la segunda mitad, porque el valor que buscamos es mayor que el central. Esto significa que tenemos un subarray y por tanto sigue siendo un array con un índice inferior y otro superior. Por lo tanto, volvemos a aplicar la misma estrategia: volvemos a subdividir el array en dos mitades a la búsqueda de un valor clave.

Los índices 'inferior' y 'superior' nos sirven para "seleccionar", por así decirlo, el subarray que nos interesa investigar. Obviamente, en cada iteración, el subarray a procesar se va reduciendo de tamaño. Esto significa que los índices 'inferior' y 'superior' se van acercando entre sí.

Espero que esto aclare las dudas.

Steven

Martín
2011-02-15 04:31:49

Clarisimo...

Ahora me surge otra duda.

Tratando a "inferior" y "superior" como enteros, 0 y 39, el resultado de central no seria un entero.

A menos que sea que 39 habla de la posición y restando la posición 0, quedo en la 38, consiguiendo al dividirlo la posición 19 y sumandole la posición 0, consigo la 20, que tendría sentido.

Siendo de la segunda forma, ¿Por que son considerados asi "inferior" y "superior", haciendo referencia a posición?

Se ve que en algo colgué por acá =P

Ahora con lo que me dijo entiendo como funciona, solo me queda la duda que comente ahí arriba...

Steven
2011-02-18 19:49:19

Hola Martín,

Primeramente, sí podemos dividir enteros. Según las reglas semánticas de C++ de los operadores aritméticos, el tipo del dato resultante de la operación concuerda con el tipo homogéneo de sus operandos; por ejemplo,

<int> + <int>  =>  <int>
<float> * <float>  =>  <float>
<unsigned long int> / <unsigned long int>  =>  <unsigned long int>

Por lo tanto, sí se pueden dividir enteros, resultando en un cociente entero. Por ejemplo, 39/2 = 19.

En cuanto a los índices, necesitamos 'inferior' y 'superior' porque son constantemente actualizados. Si te fijas, el algoritmo se basa en un bucle 'do/while'.

Espero haber aclarado las dudas.

Steven

jadr
2011-07-31 21:16:56

¡Hola!

El ejemplo 11.2 no compila tal y como se ve en la web. Necesita incluir la librería cstring para poder usar la función srtlen.

La línea 39 acaba en un extraño carácter '\'. Sobra ese caracter y falta el siguiente código:

{r[max(lon1, lon2)]-=10; acarreo=1;}

Un saludo

Carlitos
2011-11-07 17:02:08

Un MCD para el ejercicio de las fracciones un pelín más eficiente:

int MCD( int a, int b ){
	int r;
	while( true ){
		r = a%b;
		if( !r ) return b;
		else{
			a = b;
			b = r;
		}
	}
}
Diego
2013-01-27 03:03:15

En el ejemplo 11.1 existe un error en la condicion del if que está en el int main(), simplemente debería ser "mayor que" (>).

En el codepad está correcto.

elvis
2015-10-13 04:42:16

hola necesitos este ejercicio .. que me ejecute en falcon c++

Diseño del prototipo en lenguaje C++ que

muestre un menú con las siguientes

opciones:

1.Registro de datos paciente

2.Registro médico

3.Consultas

4.Informes

5.Salir

Victor Vidal Garcia
2015-11-13 03:51:26

hola necesitos este ejercicio .. que me ejecute en falcon c++

Diseño del prototipo en lenguaje C++ que

muestre un menú con las siguientes

opciones:

1.Registro de datos paciente

2.Registro médico

3.Consultas

4.Informes

5.Salir