Java Heaven

Búsqueda Binaria

Escrito por javaheaven 24-04-2011 en General. Comentarios (1)

El algoritmo de búsqueda binaria es un excelente método para buscar datos dentro de una estructura(generalmente un arreglo unidimencional). Se le da el nombre de búsqueda binaria por que el algoritmo divide en dos el arregelo, aludiendo al concepto de bit, el cual puede tener dos estados.

La única condición para usar este algoritmo es que los datos dentro del arreglo estén ordenados de menor a mayor.

La solución mas fácil para realizar una busqueda es por fuerza bruta, pero este método puede resultar bastante ineficiente cuando se tiene una gran cantidad de datos, ya que habria que buscar posición por posición hasta encontrar el dato que queremos.

El código por fuerza bruta es bastante sencillo:

for(int i=0; i<Arreglo.length; i++)
             if(Arreglo[i] == elemento)
                 System.out.println("\nElemento encontrado en la posicion: " + i);


Solo se recorre todo el arreglo y verificamos si la posición i es igual al dato que queremos buscar, el código anterior se puede mejorar simplemente agregandole una bandera, pero aun asi no es lo suficientemente bueno.

El algoritmo de busqueda binaria es el siguiente:

 1. Se declaran los índices superior e inferior. El inferior en 0 y el superior con el
     tamaño del arreglo menos 1.

 2. Se calcula el centro del arreglo con la siguiente formula:
     centro = (superior + inferior) / 2

 3. Verificamos si el arreglo en la posición centro es igual al dato que buscamos. Si es
     igual significa que encontramos el dato y retornamos centro.

 4. Si son diferentes verificamos si el arreglo en la posición centro es mayor al dato que
     que queremos buscar. Si es mayor actualizamos superior: superior = centro - 1, si
     no actualizamos inferior:
inferior = centro + 1.

 5. Volvemos al paso 2.

Si cuando ya no se cumpla la condicón del ciclo y no se encontro el dato retornamos -1
indicando que el dato no se encuentra en el arreglo.


Supongamos que tenemos el arreglo {2, 3, 5, 7, 9, 11, 14, 18, 22, 25} y queremos buscar el dato 18, entonces el inferior toma el valor de 0 y superior el valor de 9 (ya que es tamaño del arreglo menos 1).

Calculamos el centro,
centro = (superior + inferior) / 2
                             
centro = (9 + 0) / 2
                             
centro = 4         
división entera(ignorando la parte decimal).

Arreglo en la posición centro es 9 (Arreglo[centro] = 9) ya que se empieza a contar desde 0.

Comprobamos si
arreglo en la posición centro es igual al dato que queremos buscar Arreglo[centro] = dato,  como Arreglo[centro] = 9 y dato = 18. no son iguales por lo tanto ahora verificamos si es mayor, en este caso no lo es entonces actualizamos inferior = centro + 1, esto hace que podamos descartar todos los datos del centro hacia atras, esto reduce nuestro arreglo a {11, 14, 18, 22, 25}. Y así seguiremos hasta que Arreglo[centro] = dato.

Como se puede notar este método es bastante eficiente en arreglos grandes, por ejemplo supongamos que tenemos un arreglo de 10000 datos, y estamos buscando un dato que se encuentra en la posición 6000, solo en la primera vuelta del ciclo ya se pueden descartar los primeros 5000 valores, en cambio por fuerza bruta se tendrian que realizar esos 6000 ciclos para poder localizar el dato.

El código completo quedaría así:

public class BusquedaBinaria
{
    public static int busquedaBinaria(int[] Arreglo, int elemento)
    {
        int i = 0, centro = 0, posicion = 0, inferior = 0, superior = Arreglo.length-1;
       
        while(inferior <= superior)
        {
            centro = (superior + inferior) / 2;
             
              if (Arreglo[centro] == elemento)
                 return centro;
                 
              else
                 if (Arreglo[centro] > elemento)
                       superior = centro - 1;
                 else
                       inferior = centro + 1;
        }
 
          return -1;
    }
   
    public static void main (String[] args)
    {
        java.util.Scanner Leer = new java.util.Scanner(System.in);
       
        System.out.print("Tamaño del arreglo: ");
        int tamañoArreglo = Leer.nextInt();
       
        int[] Arreglo = new int[tamañoArreglo];
       
        for(int i=0; i<Arreglo.length; i++)
            Arreglo[i] = Leer.nextInt();
       
        System.out.print("Elemento a buscar: ");
        int elemento = Leer.nextInt();
       
        int posicion = busquedaBinaria(Arreglo, elemento);
       
        if(posicion == -1)
            System.out.println("\nElemento no encontrado");
        else
            System.out.println("\nElemento " + elemento + " encontrado en la posición " + posicion);
    }
}


También lo pueden descargar de aquí:

Fuerza bruta: http://www.megaupload.com/?d=IWGQ7OII
Búsqueda binaria: http://www.megaupload.com/?d=RF6VXSYU

A estos les implemente un método para ver el tiempo en que tardan en ejecutarse los programas, en arreglos chicos no se nota mucho la diferencia, pero cuando son arreglos grandes el tiempo se reduce drasticamente.

Para probar les dejo un bloc de notas con 10000 datos ordenados, solo copienlos y pegenlos cuando se los pida el programa.

Datos de prueba: http://www.megaupload.com/?d=L2HI8FMS

Generar números aleatorios

Escrito por javaheaven 08-02-2011 en General. Comentarios (1)

Generar números aleatorios es algo muy común dentro de la encriptación de datos, generar claves o simplemente como ejercicio. Para generar un número aleatorio usaremos el método random() de la clase Math.

El método random() nos devuelve un numero entre 0.0 y 0.9 de tipo double, para usarlo simplemente hay que llamarlo y asignarle el valor devuelto a una variable de tipo double:

  double numero = Math.random();

Ya que el método random() genera un número entre 0.0 y 0.9, si quieres generar un numero mas grande solo deberás multiplicar el resultado, por ejemplo si quieres generar un número entre 0 y 6.

  double numero = Math.random()*6+1;

Hay que notar que se debe sumar 1 al límite ya que de otro modo este no aparecería, en otras palabras si no le sumara 1 solo generaría números entre 0 y 5.

También debemos recordar que el número será de tipo double, así que si quieres que sea de tipo entero basta con hacer un casting:

  int numero = (int)(Math.random());

Vamos a hacer un ejemplo un poco más útil, en el que yo puedo ingresar el límite que quiera y generara un número entre 0 y el límite:

import java.util.Scanner;

public class GenerarAleatorios
{
    public static void main (String[] args)
    {
        Scanner Leer = new Scanner(System.in);
       
        System.out.print("Limite: ");
        int limite = Leer.nextInt()+1;

        int numero = (int)(Math.random() * limite);
       
        System.out.println("Número generado: " + numero);
    }
}


Descarga el código de aqui: http://www.megaupload.com/?d=O2C7Y7HY

Obtener fecha y hora del sistema

Escrito por javaheaven 24-01-2011 en General. Comentarios (0)

Java posee la clase Calendar, que se encuentra en el paquete Util. Por medio de esta clase es posible obtener la fecha(día, mes año) y la hora(hora, minuto, segundo), de una manera bastante fácil. Mostrar la fecha en alguna aplicación le dará un toque más profesional.

En realidad existen varias formas de obtener la fecha, pero esta es la más fácil, consiste en instanciar la clase Calendar, esto sería solo con una línea así:

  Calendar calendario = Calendar.getInstance();

Bien ahora necesitamos algunas variables para guardar estos valores, llamare a estas variables año, mes, dia, hora, minuto y segundo. Estas deben ser de tipo entero.

Para obtener los datos usaremos el método get(). Por medio del objeto calendario que ya habíamos creado podemos acceder a las variables YEAR, MONTH, DATE, HOUR, MINUTE, SECOND.

 *NOTA: Si quieres mostrar la hora en formato de 24 horas tendrás que usar la variable 
             HOUR_OF_DAY.

 *NOTA: A la variable MONTH le tienes que sumar 1, porque al igual que un arreglo se
            empieza a contar desde 0.

Aquí está un ejemplo completo sobre el uso de Calendar:


import java.util.Calendar;

public class Fecha
{
    public static void main (String[] args)
    {
        Calendar Calendario = Calendar.getInstance();
       
        String año = Integer.toString(Calendario.get(Calendar.YEAR));
        String mes = Integer.toString(Calendario.get(Calendar.MONTH) + 1);
        String dia = Integer.toString(Calendario.get(Calendar.DATE));
        String hora = Integer.toString(Calendario.get(Calendar.HOUR));
        String minuto = Integer.toString(Calendario.get(Calendar.MINUTE));
        String segundo = Integer.toString(Calendario.get(Calendar.SECOND));
       
        System.out.print("Año: " + año + "\nMes: " + mes + "\nDia: " + dia + "\nHora: " + hora + "\nMinuto: " + minuto + "\nSegundo: " + segundo);
    }
}


Para probarlo solo copia todo el código o si prefieres descárgalo desde aquí:
http://www.megaupload.com/?d=XDN4Z1TO

Si quieres saber más de la clase Calendar le puedes echar un ojo a la API, ahí podrás ver todos sus métodos y otras funciones, aquí te dejo el link:
http://download.oracle.com/javase/1.4.2/docs/api/java/util/Calendar.html

Método para calcular Pi

Escrito por javaheaven 23-01-2011 en General. Comentarios (0)

El número Pi es un numero irracional y se define como la relación entre la circunferencia y su diámetro. Tantas veces hemos visto esa constante, pero alguna vez se preguntaron ¿Cómo se calcula?

Bien, en realidad existen varios métodos para calcularlo, la forma en que lo voy a hacer es la siguiente. Este método se basa en una serie que se define asi:

                      4 - (4/3) + (4/5) - (4/7) + (4/9) - (4/11) ......... = Pi

Como se puede observar se parte del número 4 y a este se le van restando y sumando alternadamente (4/siguiente número impar, empezando del 3). Teóricamente si se repite este proceso "infinitamente" llegaremos al número Pi.

Pongo "infinitamente" entre comillas porque para una computadora repetir un proceso infinitamente es imposible, esto es por cuestiones de memoria, así que debemos definir un límite a la hora de hacer los cálculos.

Para el siguiente programa use un arreglo de un tamaño de 10000000, este arreglo hará la función del denominador, por lo tanto en la primera posición del arreglo estará un 3, en la segunda un 5....y así sucesivamente. También hare uso de una variable de tipo double a la que llamare Pi y la inicializare en 4, para empezar el cálculo.

Después de llenar el denominador, llamare al método que calcula Pi, este método tiene dos partes, una que resta y otra que suma. En cada vuelta del ciclo tiene que sumar o restar, pero no hacer las dos en un ciclo, para controlar esto se usa variable con una funición de bandera que puede tomar dos valores 1 o 0, si es 0 resta y si es 1 suma.

Cuando se cumple el ciclo significa que ya se ha calculado Pi.

Muy bien basta de tanta teoria, asi que aqui esta el codigo:


public class CalcularPi
{
    static int denominador[] = new int[10000000]; //Para modificar la presición ajusta  
                                                                   //este valor
   
    public static void LlenarDenominador()
    {
        int j = 0;
       
        for(int i=0; i<20000000; i++) //Para modificar la presición ajusta este
                                               //valor(Deberá ser el doble que el de arriba)
        {
            if(i%2 != 0)
            {
                denominador[j] = i;
                j++;
            }
        }
    }
   
    public static double Calcular(double Pi)
    {
        int i = 0, bandera = 0;

        while(i<9999999)//Para modificar la presición ajusta este valor(Debera ser el 
                               //tamaño de denominador-1)
        {
            if(bandera == 0)
            {
                Pi -= 4.0 / denominador[i+1];
                i++;
                bandera = 1;
            }
           
            else
            {
                Pi += 4.0 / denominador[i+1];
                i++;
                bandera = 0;
            }
        }
       
        return Pi;
    }  
       
    public static void main (String[] args)
    {
        double Pi = 4;
       
        LlenarDenominador();
        Pi = Calcular(Pi);
       
        System.out.print(Pi);
    }
}



Descarga el código de aquí: http://www.megaupload.com/?d=2ZHHM2U0

Contar número de vocales de una cadena

Escrito por javaheaven 19-01-2011 en General. Comentarios (5)

Contar el número de vocales de una cadena es un ejercicio clásico para los que están aprendiendo a programar. Es un método bastante simple aunque si no conoces bien los ciclos tal vez se pueda complicar.

La lógica es la siguiente, lo primero es leer la cadena, como lo hemos estado haciendo últimamente utilizando la clase Scanner, enseguida de leerla es convertir toda la cadena en minúsculas para esto solo le pasamos el método toLowerCase (igual se puede convertir a mayúsculas con el metodo toUpperCase) esto es para evitarnos problemas ya que solo necesitamos saber si es vocal o no, sin importar si es mayuscula o minuscula.

Después la cadena ya en minúscula entrara a un ciclo for, que se repetirá el número de caracteres que tenga la cadena, para esto necesitamos saber la longitud de la cadena usando el método length. La cabecera del ciclo for quedaría así:

for(int i=0; i<Cadena.length(); i++)


Esto se lee, repetir desde que i = 0 hasta que i sea menor a la longitud de la cadena, y vamos a repetir de uno en uno.

Dentro del ciclo estará una condición if que será la que estará comprobando si el caracter es o no vocal, esta condición quedaría así:

if(Cadena.charAt(i) == 'a' || Cadena.charAt(i) == 'e' || Cadena.charAt(i) == 'i' || Cadena.charAt(i) == 'o' || Cadena.charAt(i) == 'u')


   *Recuerden que el método charAt() nos devuelve el caracter que se encuentra en la 
     posición que especifiquemos de la cadena.

Si se cumple esta condición significa que el caracter si es vocal, entonces ya solo quedaría incrementar un contador. El código completo quedaría así:

import java.util.Scanner;

public class ContarVocales
{
    public static void main (String[] args)
    {
        Scanner Leer = new Scanner(System.in);
       
        System.out.print("Cadena: ");
        String Cadena = Leer.nextLine(); // Leer cadena
        Cadena = Cadena.toLowerCase(); // Pasar a minuscula la cadena
       
        int ContadorVocales = 0;
       
        for(int i=0; i<Cadena.length(); i++)
        {
            if(Cadena.charAt(i) == 'a' || Cadena.charAt(i) == 'e' || Cadena.charAt(i) == 'i' || Cadena.charAt(i) == 'o' || Cadena.charAt(i) == 'u')
                ContadorVocales++;
        }
       
        System.out.print("Numero de vocales: " + ContadorVocales);
    }
}