En este ejemplo tenemos una aplicación simple que pide un número y lo convierte a binario utilizando un algoritmo recursivo con una variable externa.
Lo primero que tenemos que saber es cómo convertir un número de base 10 a binario, (base 2). Para ello, se divide el número deseado entre 2 y cada resultado de la división tantas veces como sea necesario hasta obtener el número indivisible, el 1. Luego se toman el último resultado, 1 y todos los restos de las divisiones, viendo la imagen va a quedar mucho más claro el concepto.
A continuación veremos el código en Java necesario para pedir el número en base 10 y devolverlo en binario, por supuesto que se pueden agregar validaciones, de hecho hay que agregar validaciones para asegurarnos que el usuario ingrese un número, pero ese no es el objetivo de este post.
import java.io.BufferedReader;
import java.io.InputStreamReader;
class binario
{
public static void main(String[] args)
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader rdr = new BufferedReader(isr);
System.out.print("Ingrese un número entero: ");
String buffer = "0";
try
{
buffer = rdr.readLine();
}
catch(java.io.IOException e) // Es obligatorio manejar la IOException, si se omite no compila
{
System.out.println(e);
}
int dec = Integer.parseInt(buffer);
System.out.print("El valor binario correspondiente es: ");
if(dec == 0)
System.out.println(dec); // Cero en cualquier base es cero
else
System.out.println(obtenerBinario(dec)); // llamamos a la func. recursiva
}
static String aux = ""; // variable auxiliar utilizada para almacenar el resto de cada división
static String obtenerBinario(int decimal)
{
if(decimal == 1) // Límite de la recursividad
return Integer.toString(decimal) + aux; // Devolvemos 1 y los restos anteriores
else
{
aux = aux + Integer.toString(decimal % 2); //guardamos el resto en la variable auxiliar
return obtenerBinario(decimal / 2); // hacemos el llamado recursivo con el resultado de la división
}
}
}Además del algoritmo para convertir los números, vale la pena ver la forma en que se lee la entrada estándar, utilizando un BufferedReader, pero eso lo veremos con mayor profundidad en otro post.
}
Un Corte de Control es un algoritmo muy usado a la hora de listar datos. Actualmente es más factible obtener los datos con una consulta SQL, pero el Corte de Control aún es una técnica válida.
Un Corte de Control se compone de 3 partes básicas: principio, cuerpo y fin, en pseudo código sería así:
while(i < cantidadElementos)
{
principio; // inicializar variables y condiciones, obtener datos, etc.
cuerpo; // recorrer los datos respetando la condición.
fin; // mostrar los datos.
}En nuestro ejemplo tendremos datos de alumnos y cursos, la estructura es como si fuese una base de datos, entonces nuestras tablas tendrían la siguiente estructura:
| Alumnos |
Cursos |
| ID |
int |
ID |
int |
| IDCurso |
int |
Descripción |
string |
| Nombre |
string |
|
|
Y nosotros necesitamos hacer un Corte de Control por ID de Cursos (criterio del corte) para listar los alumnos agrupados por curso, entonces el algoritmo se vería de la siguiente manera:
static void corteDeControl()
{
// -- principio del corte
int i= 0; // variable utilizada para iterar en la lista de cursos
int IDCursoAnterior = 0; // variable con la condición del corte
Dictionary<int, List<alumno>> resultado = new Dictionary<int, List<alumno>>(); // resultado del corte
Console.WriteLine("\n\nListado de alumnos por curso\n"); // imprimir encabezado
// -- cuerpo del corte
while (i < DS.Cursos.Count)
{
IDCursoAnterior = DS.Cursos[i].ID; // condición del corte
while (i < DS.Cursos.Count && DS.Cursos[i].ID == IDCursoAnterior) // mientras se cumpla la condición del corte
{
foreach (alumno a in DS.Alumnos) // buscar los alumnos que pertenezcan a ese curso
{
if (a.IDCurso == IDCursoAnterior)
{
if (resultado.ContainsKey(IDCursoAnterior))
{
resultado[IDCursoAnterior].Add(a);
}
else
{
List<alumno> lista = new List<alumno>();
lista.Add(a);
resultado.Add(IDCursoAnterior, lista);
}
}
}
i++; // siguiente iteración
}
}
//fin del corte
imprimir(resultado); // mostrar el listado
}Resumiendo, en pseudo código, el cuerpo del corte de control se vería más o menos así:
while(i < cantidadElementos)
{
IDAnterior = items[i]; // condición del corte
while(i < cantidadElementos && IDActual = IDAnterior)
{
// proceso datos
}
i++;
}Puedes descargar una solución de Visual Studio 2005 con el ejemplo (25.93 KB).
}
Siguiendo con el tema Recursividad, ahora vamos a ver un ejemplo en C++ que es otro de los clásicos a la hora de aprender algoritmos recursivos, el cálculo del factorial de un número.
El factorial de un número n, se define como el producto de todos los números naturales comprendidos entre 1 y n, o sea que el factorial de 3 es 1 x 2 x 3 = 6. Por definición además, el factorial de 0 es 1.
Veamos lo anterior con ejemplos y a continuación la función iterativa para realizar el cálculo del factorial en C++.
- 3! = 3 x 2 x 1
- n! = n x (n-1) x (n-2) … x 1
int factorial(int n) {
int i;
int fact = 1;
for(i = 1; i <= n; i++) {
fact = fact * i;
}
return fact;
}
Ahora si analizamos un poco más podemos ver que n! = n x (n-1)! (para n > 0), de donde surge la recursividad, ahora veamos un ejemplo y luego la función recursiva.
- 4! = 4 x 3 x 2 x 1
- 4! = 4 x 3!
- 3! = 3 x 2 x 1
- 3! = 3 x 2!
- 2! = 2 x 1
int factorial(int n) {
if(n == 0) {
return 1;
}
else
{
return n * factorial(n-1);
}
}}
El método de la burbuja o método de intercambio directo es el algoritmo de ordenación más simple. El mismo compara los elementos a ordenar de a pares, cada uno con su siguiente y si están en el orden equivocado los intercambia y el proceso debe realizarse varias veces hasta que la lista esté totalmente ordenada, pero al ser un algoritmo tan simple, a pesar de ser efectivo, el mismo no es muy eficiente, su orden es n2
Por ejemplo en la lista [3,1,2,0] se harán los siguientes movimientos: (en negrita los elementos comparados)
| # de comparación |
Estado inicial |
Estado final |
| 1 |
3,1,2,0 |
1,3,2,0 |
| 2 |
1,3,2,0 |
1,2,3,0 |
| 3 |
1,2,3,0 |
1,2,0,3 |
| 4 |
1,2,0,3 |
1,2,0,3 |
| 5 |
1,2,0,3 |
1,0,2,3 |
| 6 |
1,0,2,3 |
1,0,2,3 |
| 7 |
1,0,2,3 |
0,1,2,3 |
Ahora vamos a ver la función en Python para implementar el método de la burbuja:
def ordenar(items):
i = 0 # Inicializar las variables
j = 0
for i in range(len(items)): # recorrer toda la lista
for j in range(len(items) -1): # recorrer toda la lista haciendo las comparaciones
if items[j] > items[j+1]: # comparar
aux = items[j]
items[j] = items[j+1]
items[j+1] = aux}
