0
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 cax de modo que pueda cambiar a nuestra conveniencia. En principio, usaremos 32 caracteres. Si el resultado no cabe en cax 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 cax = 32;
typedef char numero[cax];
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 cax = 32;
typedef char numero[cax];
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ñadir 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 cax = 32;
typedef char numero[cax];
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) < cax) {
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[cax];
...
bool Sumar(numero n1, numero n2, numero r) {
int acarreo = 0;
int c;
for(unsigned int i = 0; i < cax; 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:
| 11 // Simplificación de fracciones
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;
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);
}
|
Comentarios