0
Ejemplos capítulo 24
Ejemplo 24.1
En el capítulo 11 sobre los estructuras vimos un programa de ejemplo para implementar el método de Búsqueda binaria o Busca dicotómica. También mencionamos que volveríamos a ver ese problema usando recursividad.
Bien, ese momento ha llegado.
Recordemos la idea: 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
// Mayo 2015 Tutoriales En Linea
#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;
if(superior <= inferior) return -1;
central = inferior+(superior-inferior)/2;
if(vec[central] == valor) return central;
else if(vec[central] < valor) return Binaria(vec, valor, central+1, superior);
return Binaria(vec, valor, inferior, central-1);
} |
Ejecutar este código en codepad.
Ejemplo 24.2
Veamos otro problema común que se suele resolver aplicando recursividad.
El algoritmo de Euclides sirve para calcular el máximo común divisor de dos números.
El mcd se define así:
Dados dos enteros a y b distintos de 0, decimos que el entero d mayor o iguak a 1 es un mcd de a y b si d divide a a y a b, y para cualquier otro entero c tal que c divida a a y a b, entonces c también divide a d.
El algoritmo de Euclides parte de la proposición de, siendo a y b dos enteros distintos de cero, el mcd de a y b es el mismo que el de b y r, donde r es un entero mayor o igual que cero y menor que b, se calcula como el resto de la división entera entre a y b.
La ventaja es que r es un entero de menor que a. El algoritmo aprovecha esto para calcular el mcd de forma recursiva.
mcd(a,b)
- si a < b, retornar mcd(b,a)
- si b == 0, retornar a
- retornar mcd(b, a % b)
La implementación es realmente sencilla:
|
// Algoritmo de Euclides
//Mayo 2015 Tutoriales En Linea
#include <iostream>
using namespace std;
int mcd(int, int);
int main() {
int a, b;
a = 364332;
b = 30252;
cout << "mcd(" << a << ", " << b << ")= " << mcd(a,b) << endl;
return 0;
}
int mcd(int a, int b) {
if(a < b) return mcd(b,a);
if(b == 0) return a;
return mcd(b, a % b);
} |
Ejecutar este código en codepad.
Ejemplo 24.3
Con este algoritmo podemos recodificar el ejemplo 11.4, para simplificar fracciones:
|
// Simplificación de fracciones
//Mayo 2015 Tutoriales En Linea
#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 d= mcd(f.num,f.den);
f.num /= d;
f.den /= d;
return f;
}
int mcd(int a, int b) {
if(a < b) return mcd(b,a);
if(b == 0) return a;
return mcd(b, a % b);
} |
Ejemplo 24.4
Veamos como hacer un cambio de base de decimal a cualquier otra base, usando un algoritmo recursivo.
|
// Decimal a binario
//Mayo 2015 Tutoriales En Linea
#include <iostream>
using namespace std;
void DecimalBinario(int, int);
int main() {
DecimalBinario(65536,2);
cout << endl;
DecimalBinario(65536,3);
cout << endl;
DecimalBinario(65536,8);
cout << endl;
DecimalBinario(65536,10);
cout << endl;
DecimalBinario(65536,16);
cout << endl;
return 0;
}
void DecimalBinario(int n, int base) {
if(n >= base) DecimalBinario(n/base, base);
cout << char((n%base < 10) ? '0'+n%base : 'A'+n%base-10);
} |
Ejecutar este código en codepad.
Ejemplo 24.5
Un último ejemplo, vamos a crear un programa para sumar los dígitos de un número entero, de forma recursiva, claro.
|
// Sumar los dígitos de un número
//Mayo 2015 Tutoriales En Linea
#include <iostream>
using namespace std;
int SumaDigitos(int);
int main() {
cout << 32890123 << ": " << SumaDigitos(32890123) << endl;
return 0;
}
int SumaDigitos(int n) {
if(n < 10) return n;
return n%10+SumaDigitos(n/10);
} |
Ejecutar este código en codepad.
Comentarios