jueves, 18 de noviembre de 2010
jueves, 21 de octubre de 2010
EJEMPLOS DE PILAS
Ejercicio de pilas
ESTE EJEMPLO PERMITE CREAR UNA PILA, BORRARLA Y VER LOS DATOS QUE HAY EN ELLA.
miércoles, 13 de octubre de 2010
jueves, 7 de octubre de 2010
jueves, 23 de septiembre de 2010
miércoles, 8 de septiembre de 2010
Busqueda y Ordenamiento.
BUSQUEDAS
Búsqueda Lineal
La búsqueda lineal consiste en recorrer los elementos de búsqueda de principio hasta el final hasta encontrar la palabra a buscar.
Se pide: Codificar el método search que realiza la búsqueda lineal.
/*
* LinealSearch.java
*
* Created on 27 de marzo de 2003, 10:10
*/
/**
* Realiza la búsqueda lineal entre unas palabras cuyos valores se leen
* por entrada estándar (el teclado).
*/
import java.io.*;
import java.util.StringTokenizer;
public class LinealSearch extends Search {
/** Crea una nueva instancia de LinealSearch */
public LinealSearch(String linea) {
super(linea);
} //Constructor
/*
* Devuelve la posicion(+1) del array de elementos ordenados
* donde se encuentra la palabra pasada por argumento.
* Si no lo encuentra, devuelve -1
*/
public int search(String palabra) {
// Escribir código
//...
return -1;
}
/*
* main de prueba:
* Lee una línea de palabras (ordenadas o no) que se ordenarán dentro del constructor.
* Busca dentro de él la palabra que se pasa en la siguiente línea.
*/
public static void main(String [] args) {
String linea, palabra;
BufferedReader lector= new BufferedReader(new InputStreamReader(System.in));
try {
System.out.print("Palabras donde buscar: ");
if(((linea= lector.readLine())!=null)&&(!linea.equals(""))) {
System.out.print("Palabras (ordenadas) donde buscar: ");
LinealSearch linealSearch= new LinealSearch(linea);
System.out.println(linealSearch.toString());
System.out.print("Palabra a buscar: ");
if (((palabra= lector.readLine())!=null)&&(!palabra.equals(""))) {
int posicion=linealSearch.search(palabra);
if (posicion!=-1) {
System.out.println("Palabra encontrada en la posición "+posicion);
}
else {
System.out.println("Palabra " + palabra +" NO encontrada");
System.out.println("Reescriba la palabra: ");
}
} //if palabra
} //if linea
}
catch(Exception e) {
System.err.println(e);
}
}
}
BÚSQUEDA BINARIA
Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes:
Los datos deben estar contenido en un estructura de datos tipo vector
Los datos del vector deben estar ordenados
Una vez que se cuenten son las características descritas, se divide el vector para poder conocer la posición central y se verifica si es el dato que se esta buscando (lineas 9-12), si es el dato que se busca regresa la posición (índice del vector), en caso de que no sea el dato que buscamos se verifica si es mayor o menor que la posición central y se vuelve a redefinir la posición final o inicial según cumpla la condición (lineas 14-18).
Debido a que el vector se encuentra ordenado si el dato que buscamos es mayor a la posición central se descartan todos los datos que se encuentren en la parte inferior, de la misma manera si el dato que buscamos en menor que la posición central definida se descarta la parte superior del vector.
Una vez que encuentre el dato el método regresara la posición en que lo encontró (linea 12), en caso de no encontrar el dato en el vector regresara el valor -1
La implementación de este ejemplo del algoritmo de búsqueda binaria se encuentra en el lenguaje de programación Java.
ORDENAMIENTOS
ORDENAMIENTO DE BURBUJA
El primer ordenamiento que presentamos es quizá el más ampliamente conocido entre los estudiantes que se inician en la programación. Una de las características de este ordenamiento es que es fácil de entender y programar. Aunque, es uno de los algoritmos mas ineficiente.
La idea básica subyacente en el ordenamiento de burbuja es pasar a través del arreglo de datos varias veces en forma secuencial. Cada paso consiste en la comparación de cada elemento en el arreglo con su sucesor (x[i] con x[i+1]) y el intercambio de los dos elementos si no están en el orden correcto. Considérese el siguiente arreglo de datos:
25 57 48 37 12 92 86 33
En el primer paso se realizan las siguientes operaciones:
x[0] con x[1] (25 con 57) no intercambio.
x[1] con x[2] (57 con 48) intercambio.
x[2] con x[3] (57 con 32) intercambio.
x[3] con x[4] (57 con 12) intercambio.
x[4] con x[5] (57 con 92) no intercambio.
x[5] con x[6] (92 con 86) intercambio.
x[6] con x[7] (92 con 33) intercambio.
Así después del primer paso, el arreglo está en el siguiente orden:
25 48 37 12 57 86 33 92
Obsérvese que después del primer paso, el elemento mayor (en este caso 92) está en la posición correcta dentro del arreglo. En general x[n-i] estará en su posición correcta después de la iteración i. El método se lama ordenamiento de burbuja porque cada número “burbujea” con lentitud hacia su posición correcta. El conjunto completo de iteraciones es:
iteración 0 : 25 57 48 37 12 92 86 33
iteración 1: 25 48 37 12 57 86 33 92
iteración 2: 25 37 12 48 57 33 86 92
iteración 3: 25 12 37 48 33 57 86 92
iteración 4: 12 25 37 33 48 57 89 92
iteración 5: 12 25 33 37 48 57 89 92
La implementación de este algoritmo en Java queda como:
void Burbuja(int x[], int n)
{
int b, j, t;
do
{
b = 0;
for(j=0; j
{
if(x[j] > x[j+1])
{
t = x[j];
x[j] = x[j+1];
x[j+1] = t;
b++;
}
}
n--;
}
while(b > 0);
}
ORDENAMIENTO QUICK SORT
El ordenamiento de QuickSort (Ordenamiento Rápido) es un algoritmo del tipo divide y venceraz, es el más rápido de todos los algoritmos para ordenar y además es recursivo.
Código de ejemplo:
public void quicksort(int[] vector, int primero, int ultimo) {
int i = primero, j = ultimo;
int pivote = vector[(primero + ultimo) / 2];
int auxiliar;
do {
while (vector[i] < pivote) {
i++;
}
while (vector[j] > pivote) {
j--;
}
if (i <= j) {
auxiliar = vector[i];
vector[i] = vector[j];
vector[j] = auxiliar;
i++;
j--;
}
} while (i <= j);
if (primero < j) {
quicksort(vector, primero, j);
}
if (ultimo > i) {
quicksort(vector, i, ultimo);
}
}
Como ven le estamos enviando un arreglo de enteros (Pero prodria ser un objeto propio o dado caso un arreglo de char, String, etc) como saben cuando se envia un objeto bajo parametro se modifica la referencia en memoria entonces el objeto siempre será el mismo.
ORDENAMIENTO DE ARREGLOS
El siguiente ejercicio permite apreciar la importancia de descomponer los problemas complejos en subproblemas más simples de resolver. La clase Sorter sirve para ordenar arreglos de números reales.
La clase Sorter se usa de la siguiente manera. Suponga que Ud. ha construido su arreglo mediante la declaración:
double[] array= { 5.0, 10.0, -4.0, 15.0, 13.0, 46.0, -2.0};
Para ordenar arreglo se crea un objeto de la clase Sorter pasando como argumento el arreglo:
Sorter sorter= new Sorter(array);
El objeto construido es un ordenador de arreglos de números reales. En este punto, el objeto sorter y la variable array referencian el mismo arreglo. La construcción de sorter no ordena todavía el arreglo. De hecho, el objeto posee métodos para desplegar el contenido del arreglo en pantalla:
sorter.print();
El resultado de esta invocación será:
5.0 10.0 -4.0 15.0 13.0 46.0 -2.0
Para ordenar el arreglo se invoca el método sort:
sorter.sort();
Después de esta llamada el arreglo referenciado por array se encuentra ordenado. Si ahora se invoca sorter.print(), el resultado estará ordenado:
-4.0 -2.0 5.0 10.0 13.0 15.0 46.0
Ejercicios For,While,Do While,
Pares e Impares con For
Pares e Impares con While
Pares e Impares con Do while
Tablas de Multiplicar con For
Tablas de Multiplicar con While
miércoles, 25 de agosto de 2010
Arreglos:
Arreglos unidimensionales:
Un arreglo unidimensional es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales.
El tipo de acceso a los arreglos unidimensionales es el acceso directo, es decir, podemos acceder a cualquier elemento del arreglo sin tener que consultar a elementos anteriores o posteriores, esto mediante el uso de un índice para cada elemento del arreglo que nos da su posición relativa.
Para implementar arreglos unidimensionales se debe reservar espacio en memoria, y se debe proporcionar la dirección base del arreglo, la cota superior y la inferior.
Ejemplo :
REPRESENTACION EN MEMORIA
Los arreglos se representan en memoria de la forma siguiente:
x : array[1..5] of integer
Para establecer el rango del arreglo (número total de elementos) que componen el arreglo se utiliza la siguiente formula:
RANGO = Ls - (Li+1)donde:
ls = Límite superior del arreglo
li = Límite inferior del arreglo
Para calcular la dirección de memoria de un elemento dentro de un arreglo se usa la siguiente formula:
A[i] = base(A) + [(i-li) * w]
donde :
A = Identificador único del arreglo
i = Indice del elemento
li = Límite inferior
w = Número de bytes tipo componente
Si el arreglo en el cual estamos trabajando tiene un índice numerativo utilizaremos las siguientes fórmulas:
RANGO = ord (ls) - (ord (li)+1)
A[i] = base (A) + [ord (i) - ord (li) * w]
Arreglos Bidimensionales:Este tipo de arreglos al igual que los anteriores es un tipo de dato estructurado, finito ordenado y homogéneo. El acceso a ellos también es en forma directa por medio de un par de índices.
Los arreglos bidimensionales se usan para representar datos que pueden verse como una tabla con filas y columnas. La primera dimensión del arreglo representa las columnas, cada elemento contiene un valor y cada dimensión representa una relación
La representación en memoria se realiza de dos formas : almacenamiento por columnas o por renglones.
x : array [1..5,1..7] of integerPara calcular la dirección de memoria de un elemento se usan la siguiente formula:
A[i,j] = base (A) + [((j - li2) R1 + (i + li1))*w]
x : array [1..5,1..7] of integerPara calcular la dirección de memoria de un elemento se usan la siguiente formula:
A[i,j] = base (A) + [((i - li1) R2 + (j + li2))*w]
donde:
i = Indice del renglón a calcular
j = Indice de la columna a calcular
li1 = Límite inferior de renglones
li2 = Límite inferior de columnas
w = Número de bytes tipo componen
Arreglos multidimensionales:
Este también es un tipo de dato estructurado, que está compuesto por n dimensiones. Para hacer referencia a cada componente del arreglo es necesario utilizar n índices, uno para cada dimensión
Para determinar el número de elementos en este tipo de arreglos se usan las siguientes fórmulas:
RANGO (Ri) = lsi - (lii + 1)
No. TOTAL DE ELEMENTOS = R1 * R2* R3 * ...* Rn
donde:
i = 1 ... n
n = No. total de dimensiones
Para determinar la dirección de memoria se usa la siguiente formula:
LOC A[i1,i2,i3,...,in] = base(A) + [(i1-li1)*R3*R4*Rn + (i2-li2)*R3*R2*... (in - lin)*Rn]*w
VECTOR EN JAVA
SUMA DE VECTORES
Generar Matriz
martes, 17 de agosto de 2010
Ejemplos
If-Then :
{
if (seMueve) {
velocidadActual--;
} else {
System.err.println("La bicicleta ya está detenida");
}
}
For:
for (inicialización; condición; incremento)
{ instrucción(es); };
While:
while (Condicion) {
instrucciones
}
Do While :
do {
instrucciones
} while (condiciones);
Switch :
{
int month = 8;
switch (month) {
case 1: System.out.println("Enero"); break;
case 2: System.out.println("Febrero"); break;
case 3: System.out.println("Marzo"); break;
case 4: System.out.println("Abril"); break;
case 5: System.out.println("Mayo"); break;
case 6: System.out.println("Junio"); break;
case 7: System.out.println("Julio"); break;
case 8: System.out.println("Agosto"); break;
case 9: System.out.println("Septiembre"); break;
case 10: System.out.println("Octubre"); break;
case 11: System.out.println("Noviembre"); break;
case 12: System.out.println("Diciembre"); break;
default: System.out.println("Mes no válido.");break;
}
}
}
{
if (seMueve) {
velocidadActual--;
} else {
System.err.println("La bicicleta ya está detenida");
}
}
For:
for (inicialización; condición; incremento)
{ instrucción(es); };
While:
while (Condicion) {
instrucciones
}
Do While :
do {
instrucciones
} while (condiciones);
Switch :
{
int month = 8;
switch (month) {
case 1: System.out.println("Enero"); break;
case 2: System.out.println("Febrero"); break;
case 3: System.out.println("Marzo"); break;
case 4: System.out.println("Abril"); break;
case 5: System.out.println("Mayo"); break;
case 6: System.out.println("Junio"); break;
case 7: System.out.println("Julio"); break;
case 8: System.out.println("Agosto"); break;
case 9: System.out.println("Septiembre"); break;
case 10: System.out.println("Octubre"); break;
case 11: System.out.println("Noviembre"); break;
case 12: System.out.println("Diciembre"); break;
default: System.out.println("Mes no válido.");break;
}
}
}
lunes, 9 de agosto de 2010
Estructuras Basicas
condicional :
if - then : nos permite examinar una condición y tomar una acción en caso de ser cierta u otra en caso de ser falsa.. Es decir, en ocasiones es posible que deseemos que el programa ejecute una instrucción o instrucciones, pero solo si se cumple determinada circunstancia, y, en caso contrario, o bien no hacer nada, o bien ejecutar otras instrucciones diferentes.
En definitiva, IF comparará valores, y ejecutará o no diferentes instrucciones, en función del resultado de la comparativa.
Interactivos :
For : Las tres partes del ciclo se encuentran separadas por ; (punto y coma)
•La primer parte del ciclo especifica valores previo a su inicio.
•La segunda parte indica la condición de terminación para el ciclo, la cual esta directamente relacionada con los valores iniciales.
•Finalmente, la última parte especifica como serán manipulados los valores iniciales en cada iteración del ciclo.
Cada parte del ciclo debe incluir al menos un elemento, a la cual es posible agregar otros elementos a partir de una , (coma).
While: es un ciclo mientras se cumpla la condicion. Es decir que todas las sentencias que encierra, se ejecutarán mientras la condición sea verdadera. Este ciclo puede o no ejecutarse, depende de los valores que sean evaluados en la condición. Por tanto la condición se evaluará antes de entrar en una nueva iteración.
Do While : El ciclo Do While evalúa la expresión simplemente una vez. Luego evalúa la condición y si ésta es verdadera, vuelve a evaluar la expresión. Este proceso continúa hasta que la condición sea falsa.
Bifuracion:
Switch: es una instrucción de decisión múltiple, donde el compilador prueba o busca el valor contenido en una variable contra una lista de constantes ints o chars, cuando el computador encuentra el valor de igualdad entre variable y constante, entonces ejecuta el grupo de instrucciones asociados a dicha constante, si no encuentra el valor de igualdad entre variable y constante, entonces ejecuta un grupo de instrucciones asociados a un default, aunque este ultimo es opcional.
if - then : nos permite examinar una condición y tomar una acción en caso de ser cierta u otra en caso de ser falsa.. Es decir, en ocasiones es posible que deseemos que el programa ejecute una instrucción o instrucciones, pero solo si se cumple determinada circunstancia, y, en caso contrario, o bien no hacer nada, o bien ejecutar otras instrucciones diferentes.
En definitiva, IF comparará valores, y ejecutará o no diferentes instrucciones, en función del resultado de la comparativa.
Interactivos :
For : Las tres partes del ciclo se encuentran separadas por ; (punto y coma)
•La primer parte del ciclo especifica valores previo a su inicio.
•La segunda parte indica la condición de terminación para el ciclo, la cual esta directamente relacionada con los valores iniciales.
•Finalmente, la última parte especifica como serán manipulados los valores iniciales en cada iteración del ciclo.
Cada parte del ciclo debe incluir al menos un elemento, a la cual es posible agregar otros elementos a partir de una , (coma).
While: es un ciclo mientras se cumpla la condicion. Es decir que todas las sentencias que encierra, se ejecutarán mientras la condición sea verdadera. Este ciclo puede o no ejecutarse, depende de los valores que sean evaluados en la condición. Por tanto la condición se evaluará antes de entrar en una nueva iteración.
Do While : El ciclo Do While evalúa la expresión simplemente una vez. Luego evalúa la condición y si ésta es verdadera, vuelve a evaluar la expresión. Este proceso continúa hasta que la condición sea falsa.
Bifuracion:
Switch: es una instrucción de decisión múltiple, donde el compilador prueba o busca el valor contenido en una variable contra una lista de constantes ints o chars, cuando el computador encuentra el valor de igualdad entre variable y constante, entonces ejecuta el grupo de instrucciones asociados a dicha constante, si no encuentra el valor de igualdad entre variable y constante, entonces ejecuta un grupo de instrucciones asociados a un default, aunque este ultimo es opcional.
Suscribirse a:
Entradas (Atom)