FUNCIONES DE DISPERSION

Ejemplo de lista de adyacencia

ESTRUCTURA DE DATOS EN LA REPRESENTACION DE GRAFOS

Estructuras de datos en la representación de grafos [editar]
Artículo principal: Grafo (estructura de datos)
Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
Estructura de lista [editar]
lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.
lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.
En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si V=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.

GRAFOS

Implementación en Java
/**
* Calcular el camino mínimo en un grafo
*/
public static CaminoConPesos caminoMinimoAciclico
(Grafo g, int origen, int destino)
throws NoExiste, IdIncorrecto, HayCiclos
{
int anterior[]= new int[g.numVertices()];
double[] peso= new double[g.numVertices()];
// dar valor infinito a todas las casillas de peso
for (int i=0; i procesar =
new LinkedList();
int procesados=0;
// insertar en la cola vértices de grado cero
for (int v=0; v> ady=g.listaAristas(v);
for (Arista a: ady) {
int dest=a.destino();
grado[dest]--;
if (grado[dest]==0) {
procesar.addLast(new Integer(dest));
}
if (!Double.isInfinite(peso[v])) {
double p=a.contenido().doubleValue();
if (peso[dest]>peso[v]+p) {
anterior[dest]=v;
peso[dest]=peso[v]+p;
}
}
}
}
if (procesados!=g.numVertices()) {
throw new HayCiclos();
}
if (Double.isInfinite(peso[destino])) {
throw new NoExiste();
} else {
return caminoDe
(origen,destino,anterior,peso[destino],g);
}
}

IMPLEMENTACION CON MATRICES

METODO DE BUSQUEDA HASHING

HEAPSORT

ORDENAMIENTO POR SHELL SHORT

ORDENACION POR INSERCION BINARIA

QUICKSORT

ORDENAMIENTO DE LISTA EN ALGORITMO

// Se ingresa una lista de nombres (la lista termina
// cuando se ingresa un nombre en blanco) no permitiendo
// ingresar repetidos y luego se ordena y muestra

Proceso OrdenaLista

Dimension lista[200];

Escribir "Ingrese los nombres (enter en blanco para terminar):";

// leer la lista
cant<-0;
//AQUI GUARDA EL NOMBRE
Leer nombre;
Mientras nombre<>"" Hacer
cant<-cant+1;
lista[cant]<-nombre;
Repetir // leer un nombre y ver que no este ya en la lista
Leer nombre;
se_repite<-Falso;
Para i<-1 Hasta cant Hacer
Si nombre=lista[i] Entonces
se_repite<-Verdadero;
FinSi
FinPara
Hasta Que NO se_repite
FinMientras

// ordenar la lista
Para i<-1 Hasta cant-1 Hacer
// busca el menor entre i y cant
pos_menor<-i;
Para j<-i+1 Hasta cant Hacer
Si lista[j] pos_menor<-j;
FinSi
FinPara
// intercambia el que estaba en i con el menor que encontro
aux<-lista[i];
lista[i]<-lista[pos_menor];
lista[pos_menor]<-aux;
FinPara

// mostrar como queda la lista
Escribir "La lista ordenada es:";
Para i<-1 Hasta cant Hacer
Escribir " ",lista[i];
FinPara

FinProceso

ESTRUCTURA DE DATOS

ESTRUCTURA DE UN ARBOL

COLA DE PRIORIDAD EN JAVA

/**
* Clase enumerada que representa la
* urgencia de un cliente
*/
public enum Urgencia
{
baja, media, alta
}
import java.util.*;
/public class ColaEsperaConUrgencia
{
/**
* Clase interna para almacenar los datos
* de un cliente con urgencia
*/
private static class DatosCliente
implements Comparable
{
Cliente c;
Urgencia urg;
/**
* Constructor de DatosCliente
*/
DatosCliente (Cliente c, Urgencia urg) {
this.c=c;
this.urg=urg;
}
/*
* Comparación de clientes por su urgencia
*/
public int compareTo(DatosCliente otro) {
return this.urg.compareTo(otro.urg);
}
// cola del servicio
private Queue colaEspera;
/**
* Constructor de ColaEspera
*/
public ColaEsperaConUrgencia()
{
colaEspera=new
PriorityQueue();
}
/**
* Nuevo cliente; se mete en la cola de espera
*/
public void nuevoCliente
(Cliente c, Urgencia urg)
{
DatosCliente datos=new DatosCliente(c,urg);
colaEspera.add(datos);
}
/**
* Atender cliente: se saca de la cola de
* espera; retorna el cliente atendido
*/
public Cliente atenderCliente()
throws NoSuchElementException
{
DatosCliente datos=colaEspera.remove();
return datos.c;
}
/**
* Mostrar el estado de la cola de espera
*/
public void muestraEstado() {
System.out.println();
System.out.println("--Estado de la cola--");
System.out.println("No atendidos "+
colaEspera.size());
if (colaEspera.size()>0) {
for (DatosCliente datos:colaEspera) {
System.out.println(datos.c+" urgencia:
"+datos.urg);
}
}
}
/**
* Num clientes en espera
*/
public int numClientesEnEspera() {
return colaEspera.size();
}
}

COLA DE ESPERA EN JAVA

import java.util.*;
public class ColaEspera {
/** Clase interna para almacenar todos los datos de un cliente*/
private static class DatosCliente {
Cliente c;
long entrada, salida; // milisegundos
/** Constructor; pone la hora de entrada*/
DatosCliente (Cliente c) {
this.c=c;
entrada=Reloj.ahora();
}
void atiende() {
salida=Reloj.ahora();
}
}
// colas del servicio
private Queue colaEspera;
private Queue colaAtendidos;
/**Constructor de ColaEspera */
public ColaEspera() {
colaEspera=new LinkedList();
colaAtendidos=new
LinkedList();
}
/**
* Nuevo cliente; se mete en la cola de espera
*/
public void nuevoCliente(Cliente c)
{
DatosCliente datos=new DatosCliente(c);
colaEspera.add(datos);
}
/**
* Atender cliente: se saca de la cola de
* espera y se mete en la de atendidos;
* retorna el cliente atendido
*/
public Cliente atenderCliente()
throws NoSuchElementException
{
DatosCliente datos=colaEspera.remove();
datos.atiende();
colaAtendidos.add(datos);
return datos.c;
}
public double tiempoEsperaNoAtendidos()
{
long tiempo=0;
int num=0;
long ahora=Reloj.ahora();
for (DatosCliente datos: colaEspera) {
tiempo=tiempo + ahora-datos.entrada;
num++;
}
if (num==0) {
return 0.0;
} else {
return (((double) tiempo)/num)/1000.0;
}
}
public double tiempoEsperaNoAtendidos()
{
long tiempo=0;
int num=0;
long ahora=Reloj.ahora();
for (DatosCliente datos: colaEspera) {
tiempo=tiempo + ahora-datos.entrada;
num++;
}
if (num==0) {
return 0.0;
} else {
return (((double) tiempo)/num)/1000.0;
}
}

EJEMPLO DE COLAS EN JAVA

import java.io.*;

//Declaramos la clase calculatorTest
public class ejecutar_cola{


//Declaramos el metodo principal
public static void main (String args[])throws IOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int Espacios = 0;
char Resp, op;
String aux;

//--- Imprimir Menu ---- \\

System.out.println("\n :: XROM RELOADED :: 19/07/07 \n");

System.out.print("\t Cuantos espacios quiere en la Cola (entre 3 y 30 recomendable)? :");
Espacios = Integer.parseInt(entrada.readLine());

Cola Ejecutar = new Cola(Espacios);

//--- Imprimir Menu ---- \\

System.out.println("\n\n\t ------------ //-------- Menu Cola Simple --------\\\\------------ \n ");

do {

System.out.println("\n\n1.- Imprimir Cola"); // Mostrar
System.out.println("2.- Agregar Elemento a la Cola"); // Push
System.out.println("3.- Quitar Elemento de la Cola"); // Pop


System.out.print("\n\n Elija una Opcion : ");

aux = entrada.readLine();
op = aux.charAt(0);



//---- Elegir opcion ---\\


switch (op) {

case '1':

Ejecutar.Imprimir();

break;

case '2':


Ejecutar.Push();


break;

case '3':

Ejecutar.Pop();

break;


default:

System.out.println("opcion fuera de rango !!");



} // Fin del switch


System.out.print("Desea hacer otra operacion ?? S / N ");
aux = entrada.readLine();
Resp = aux.charAt(0);


} while (Resp == 'S' Resp == 's');


} // Fin del metodo main

} // Fin de la calse
Cola.java(Clase y Metodos de la Cola)

ARBOL BINARIO DE BUSQUEDA EN JAVA

public class CArbolBinarioDeBusqueda extends CArbolBinB
{
public int comparar(Object obj1, Object obj2)
{
String str1=new String(((CDatos)obj1).obtenerNombre());
String str2=new String(((CDatos)obj2).obtenerNombre());
return str1.compareTo(str2);
}

public void procesar(Object obj)
{
String nombre=new String(((CDatos)obj).obtenerNombre());
Double nota=((CDatos)obj).obtenerNota();
System.out.println(nombre+" "+nota);
}

public void visitarInorden()
{
inorden(null, true);
}

public void visitarPosorden()
{
posorden(null, true);
}

public void visitarPreorden()
{
preorden(null, true);
}
}

PROGRAMA DE ARBOLES CON JPANEL EN JAVA

import java.util.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import javax.swing.tree.*;
public class Arboles extends JPanel{
//elementos para crear el entorno grafico
private static JSplitPane oJSP1, oJSP2;
private static JTree arbol1,arbol2;

static int i=0;
DefaultMutableTreeNode raiz,raiz2,rama,seleccion;
DefaultTreeModel modelo,modelo2;
/////////////////////////////////////////
/** Creates a new instance of arboles */
public Arboles() {

//creamos el entorno grafico
oJSP1 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
oJSP2 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
raiz = new DefaultMutableTreeNode( "raiz" );
arbol1 = new JTree(raiz);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo =(DefaultTreeModel)arbol1.getModel();
modelo.addTreeModelListener(new MiTreeModelListener());
arbol1.addTreeSelectionListener(new MiTreeSelectionListener());
arbol1.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP2.setRightComponent(new JScrollPane( arbol1));
oJSP2.setLeftComponent(new JScrollPane());
oJSP1.setRightComponent(oJSP2);
raiz2 = new DefaultMutableTreeNode( "raiz2" );
arbol2 = new JTree(raiz2);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo2 =(DefaultTreeModel)arbol2.getModel();
modelo2.addTreeModelListener(new MiTreeModelListener());
arbol2.addTreeSelectionListener(new MiTreeSelectionListener());
arbol2.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP1.setLeftComponent(new JScrollPane(arbol2));
Dimension minimumSize = new Dimension(100, 540);
oJSP1.setDividerLocation(150);
oJSP1.setDividerSize(10);
oJSP1.setPreferredSize(new Dimension(500, 450));
this.add(oJSP1);
//creamos las tablas para almacenar las acciones
//
}
//anhade una nueva rama al nodo seleccionado
void nueva_rama(){

Estructura est;
String datos[][] = {
{ "Colores","Rojo","Verde","Azul" },
{ "Sabores","Salado","Dulce","Amargo" },
{ "Longitud","Corta","Media","Larga" },
{ "Intensidad","Alta","Media","Baja" },
{ "Temperatura","Alta","Media","Baja" },
{ "Volumen","Alto","Medio","Bajo" },
};

if( i == datos.length ) i = 0;
rama = new Rama( datos[i++] ).node();
// Control de la útlima selección realizada
if (MiTreeSelectionListener.oEstructura.getTree() == null) return;
seleccion = (DefaultMutableTreeNode)MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
if( seleccion == null ) {
System.out.println("AKI LA CAGO!!!!!!!!!!");
seleccion = raiz;
}
// El modelo creará el evento adecuado, y en respuesta
// a él, el árbol se actualizará automáticamente
MiTreeSelectionListener.oEstructura.getModelo().insertNodeInto( rama,seleccion,0 );

}
//elimina la rama seleccionada
void elimina_rama(){
Estructura est;
//buscamos la rama seleccionada

rama = (DefaultMutableTreeNode) MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
//comprobamos q la rama no sea nula
if (rama == null) return;
//comprobamos q no sea la rama raiz y la borramos
if ((rama !=raiz)&&(rama !=raiz2)) MiTreeSelectionListener.oEstructura.getModelo().removeNodeFromParent(rama);

}

}

ARBOL GENERICO

public class Arboles {

public Arboles() {
System.out.println("Un árbol genérico");
}

public Arboles(String tipo) {
System.out.println("Un árbol tipo " + tipo);
}

public Arboles(int altura) {
System.out.println("Un árbol de " + altura + " metros");
}

public Arboles(int altura,String tipo) {
System.out.println("Un " + tipo + " de " + altura + " metros");
}

public static void main(String args[]) {
Arboles arbol1 = new Arboles(4);
Arboles arbol2 = new Arboles("Roble");
Arboles arbol3 = new Arboles();
Arboles arbol4 = new Arboles(5,"Pino");
}
}

mapa conceptual estructuras

ALGORITMOS ARBOLES

Inor(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz
Top →
Pila[Top] → Nulo
Si Raiz = Nulo
Imprmir “Arbol Vacio…” y Salir
Etiqueta:
Mientras Temp ≠ Nulo
Top → Top + 1
Pila[Top] → Temp
Temp → Izq[Temp]
Fin del ciclo
Temp → Pila[Top]
Top → Top - 1
Mientras Temp ≠ Nulo
Imprimir Arbol[Temp]
Si Der[Temp] ≠ Nulo
Temp → Der[Temp]
Ir a Etiqueta
Temp → Pila[Top]
Top → Top - 1
Fin del ciclo

Salir
----------------------------------------------

PostOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz
Top →
Pila[Top] → Nulo
Si Raiz = Nulo
Imprimir “Arbol Vacio…” y Salir
Etiqueta:
Mientras Temp ≠ Nulo
Top → Top + 1
Pila[Top] → Temp
Si Der[Temp] ≠ Nulo
Top → Top + 1
Pila[Top] → - (Der[Temp])
Temp → Izq[Temp]
Temp → Pila[Top]
Top → Top - 1
Fin del ciclo
Mientras Temp ≥ 0
Imprimir Arbol[Temp]
Si Arbol[Temp] = Info[Raiz]
Temp → Pila[Top]
Top → Top - 1
Fin del ciclo
Si Temp < 0 Temp = -(Temp)
Ir a Etiqueta

Salir

----------------------------------------------
PreOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz
Top →
Pila[Top] → Nulo
Si Raiz = Nulo
Imprimir “Árbol Vació…” y Salir
Repetir mientras Temp ≠ Nulo
Imprimir Arbol[Temp]
Si Der[Temp] ≠ Nulo
Top → Top + 1
Pila[Top] → Der[Temp]
Si Izq[Temp] ≠ Nulo
Temp → Izq[Temp]
Si no:
Temp → Pila[Top];
Top → Top - 1
Fin del ciclo

Salir
----------------------------------------------

Busqueda(Arbol, Der, Izq, Pila, Raiz, Elem)

Si Raiz = Nulo
Imprimir “Arbol Vacio”
Pos → Nulo
Pad → Nulo
Regresar Pos y Pad
Salir
Si Elem = Arbol[Raiz]
Imprimir “Elemento Encontrado”
Pos → Raiz
Pad → Nulo
Regresar Pos y Pad
Salir
Si Elem < Arbol[Raiz]
Temp → Izq[Raiz]
Temp2 → Raiz
Si no:
Temp → Der[Raiz]
Temp2 → Raiz
Mientras Temp ≠ Nulo
Si Elem = Arbol[Temp]
Imprimir “Elemento Encontrado…”
Pos → Temp
Pad → Temp2
Regresar Pos y Pad
Salir
Si Elem < Arbol[Temp]
Temp2 → Temp
Temp → Izq[Temp]
Si no:
Temp2 → Temp
Temp → Der[Temp]
Fin del ciclo
Imprimir “Elemento no Encontrado…”
Pos → Nulo
Pad → Temp2
Regresar Pos y Pad

Salir

RECORRIDOS DE UN ARBOL

Al visitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol.

Los ordenamientos más importantes son llamados: preorden, post-orden y en-orden y se definen recursivamente como sigue:

Si un árbol T es nulo, entonces, la lista vacía es el listado preorden, post-orden y en-orden del árbol T.

Si T consiste de un sólo nodo n, entonces, n es el listado preorden, post-orden y en-orden del árbol T.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• visitar el nodo raíz

• recorrer el subárbol izquierdo

• recorrer el subárbol derecho

Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PRE-ORDEN:

• Visitar el raíz

• Recorrer el subárbol izquierdo en pre-orden

• Recorrer el subárbol derecho en pre-orden

Recorrido EN-ORDEN

• Recorrer el subárbol izquierdo en en-orden • Visitar el raíz • Recorrer el subárbol derecho en en-orden

Recorrido en POST-ORDEN

• Recorrer el subárbol izquierdo en post-orden

• Recorrer el subárbol derecho en post-orden

• Visitar el raíz

ARBOLES BINARIOS

COMO UTILIZAR ARBOLES

Podemos utilizar árboles con la clase JTree, se puede mostrar un árbol de datos. JTree realmente no contiene datos, simplemente es un vista de ellos. Aquí tienes una imagen de un árbol.

Como muestra la figura anterior, JTree muestra los datos verticalmente. Cada fila contiene exactamente un ítem de datos (llamado un nodo). Cada árbol tiene un nodo raíz. Los nodos que no pueden tener hijos se llaman nodos leaf (hoja). En la figura anterior, el aspecto-y-comportamiento marca los nodos hojas con una Flecha.

Los nodos que no sean hojas pueden tener cualquier número de hijos, o incluso no tenerlos. En la figura anterior, el aspecto-y-comportamiento marca los nodos que no son hojas con un carpeta. Normalmente el usuario puede expandir y contraer los nodos que no son hojas -- haciendo que sus hijos sean visibles o invisibles -- pulsando sobre él.

TORRES DE HANOI EN JAVA

import java.util.Stack;

class Hanoy {
// Las 3 pilas de discos
private Stack columnas[];

// Constructor, toma el nº de fichas total
public Hanoy(int fichas) {
columnas = new Stack[3];
// Inicializamos las columnas vacias
columnas[0] = new Stack();
columnas[1] = new Stack();
columnas[2] = new Stack();
// Colocamos en la primera las fichas, de mayor a menor
for (int i=fichas;i>0;i--) columnas[0].push(i);
}

// Muestra el estado actual
public void Mostrar() {
for (int i=0;i<3;i++) {
System.out.print("Col. "+i+": ");
for(int n : columnas[i]) System.out.print("["+n+"]");
System.out.println("");
}
}

// Mueve de la columna origen a la columna destino 1 disco
public void Mover(int origen, int destino) {
// Mostramos en pantalla lo que hacemos
Mostrar();
System.out.println("Movemos desde ("+origen+") hasta ("+destino+")");
System.out.println("");
// Y luego, lo hacemos, claro
columnas[destino].push(columnas[origen].pop());
}

// Mueve de la columna origen a la columna destino varios discos
public void MoverN(int origen, int destino, int cuantas) {
// Si solo es uno, se mueve sin más
if (cuantas <= 1) Mover(origen,destino);
else {
// Si son varios, entonces:
// - Primero movemos N-1 a la columna ni origen ni destino
MoverN(origen,3 - (origen+destino),cuantas-1);
// - Movemos la N, es decir, la grande
Mover(origen,destino);
// - Movemos las N-1 del primer paso, a la col. destino
MoverN(3 - (origen+destino),destino,cuantas-1);
}
}

// Programa principal
public static void main(String args[]) {
// Creamos una partida de 5 discos
Hanoy h = new Hanoy(5);
// Y la resolvemos (movemos de col.0 a col.2 los 5 discos
h.MoverN(0,2,5);
// Mostramos resultado, resuelto
h.Mostrar();
}
}

DEFINICIONES DE LISTAS

LinkedList

Es una lista enlazada de Recipientes (nodos) donde cada uno contiene elementos (objetos, otras listas, etc) y uno o dos punteros hacia posiciones de memoria que apuntan al anterior o siguiente nodo.
Útil cuando se quiere insertar o eliminar elementos al principio o al final de la lista. No permite acceder a un elemento en concreto de la lista directamente sin recorrer antes los anteriores.

ArrayList

Es una estructura de datos de tipo Array dinámica. A diferencia de los arrays clásicos (arrays estáticos), un ArrayList permite aumentar el tamaño del vector indefinidamente (hasta lo que la memoria permita) y agregar o quitar elementos.
A diferencia de la LinkedList, la ArrayList permite acceder a cualquier elemento de la lista directamente mediante su índice, lo que la hace especialmente adecuada para búsquedas rápidas.

HashSet

Un HashSet es una estructura de datos que contiene un conjunto de objetos. Permite buscar un objeto dentro del conjunto de forma rápida y fácil. Internamente gestiona un array y guarda los objetos utilizando un índice calculado con un código hash del objeto.
- Los elementos de un HashSet no están ordenados- Para añadir un elemento al HashSet se utiliza el método add(Object obj).- Para borrar un elemento se utiliza remove(Object obj).- Para borrar todos los elementos se utiliza clear().- El tamaño del HashSet se puede obtener con la función size()

HashMap

Un HashMap permite guardar elementos, donde cada elemento es un par clave/valor. A diferencia de un array simple donde se guarda el valor en un índice en concreto, un HashMap determina el índice él mismo basándose en el valor hash (hashcode) generado a partir de la clave.

TreeSet

Un TreeSet mantiene los objetos ordenados en lo que se conoce como un red-black tree, es decir, en un árbol binario balanceado (cada padre tiene como máximo 2 hijos, y cuando se inserta una entrada se autobalancea de forma que quede un árbol binario simétrico).
Un TreeSet permite hacer búsquedas rápidas. No tanto como un HashMap, pero el TreeSet tiene la ventaja de estar ordenado por clave.

USO DE LISTAS

import java.awt.*;
import java.awt.event.*;
public class listas extends Frame
{
List lista=new List(0,true);
Label text=new Label("Maravillas que se pueden visitar en la localidad elegida");

public listas()
{

*/ esta es la super clase y lo q esta haciendo es agregar cada uno de los barrios a una lista

super("Elegir itinerario");
lista.add("Bienvenido");
lista.add("Foiano de Val Fortore");
lista.add("Baselice");
lista.add("San Bartolomeo en Galdo");
lista.add("San Marco de los Cavoti");
lista.add("Montefalcone en Val Fortore");
lista.add("Pesco Sannita");
lista.add("Colle Sannita");
lista.add("Castelvetere en Val Fortore");
lista.add("Castelfranco en Miscano");
lista.add("Ginestra de los Schiavoni");
lista.add("San Giorgio la Molara");
lista.add("Molinara");
lista.add("Pietrelcina");
lista.add("Fragneto Monforte");
lista.add("Circello");
lista.add("Campolattaro");

/*aquí esta creando el layout de la lista por decirlo de alguna manera la imagen

add(lista,BorderLayout.CENTER);
add(text,BorderLayout.SOUTH);

*/aquí crea una nueva ventana de listas

addWindowListener(new listeWindowListener());
lista.addItemListener(new escuchaLista());

*/ este es tamaños de la ventana q creamos arriba

setSize(350,100);
setResizable(false);

show();
}

*/ constructor

public static void main(String [] arg)
{
new listas();
}

*/ auqi se implementa la clase window

class listeWindowListener implements WindowListener
{

*/ las siguientes son funciones de la clase window estamos implementando entonces tenemos q crear una función q habrá la ventana y otra q la cierre

public void windowActivated(WindowEvent e)
{}
public void windowClosed(WindowEvent e)
{}
public void windowClosing(WindowEvent e)
{
String[] s=lista.getSelectedItems();
int i=0;
System.out.println("Itinerario seleccionado");

*/ aquí estamos validando si la opción escogida estaba en el itinerario

try

{
while (true){System.out.println(s[i++]);
}
}
catch (ArrayIndexOutOfBoundsException er)
{
System.out.println("Qué lo pases bien...");
}
System.exit(0);
}

*/ las siguientes funciones también son parte de la implementación de la clase window

public void windowDeactivated(WindowEvent e)
{}
public void windowDeiconified(WindowEvent e)
{}
public void windowIconified(WindowEvent e)
{}
public void windowOpened(WindowEvent e)
{}
}

*/ aquí tenemos otra clase q nos esta mostrando los ítems seleccionados

class escuchaLista implements ItemListener
{

*/ esta función se genera un evento elevento es el ítem seleccionado

public void itemStateChanged(ItemEvent e)
{
int índice=((Integer) e.getItem()).intValue();

*/ esta es una consecución de if anidados q están validando elitem q se escogió y según el ítem escogido mostrara un texto diferente

if (índice==0) text.setText("Rocca de los Rettori, arco de Trajano, anfiteatro Romano, ciudad espectáculo");
if (índice==1) text.setText("localidad San Giovanni, Campanario, via Roma, lago, fiesta S.Giovanni, fiesta del emigrante");
if (índice==2) text.setText("óasis ds San Leonardo");
if (indice==3) text.setText("casco histórico");if (índice==4) text.setText("casco histórico");
if (índice==5) text.setText("casco histórico");if (índice==6) text.setText("casco histórico");
if (índice==7) text.setText("casco histórico"); if (índice==8) text.setText("casco histórico");
if (índice==9) text.setText("Bosque"); if (índice==10) text.setText("casco histórico");
if (índice==11) text.setText("Lago de San Giorgio"); if (índice==12) text.setText("casco histórico"); if (índice==13) text.setText("Piana Romana, casco histórico, casas de Padre Pío");
if (índice==14) text.setText("Encuentro internacional de globos, Palacio Ducal");
if (índice==15) text.setText("casco histórico"); if (índice==16) text.setText("Dique de Campolattaro");
}
}
}

RESOLUCION DE LAS TORRES DE HANOI

El problema de las Torres de Hanói es curiosísimo porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos.

Existen otras versiones del problema con un número diferente de varillas. Aunque se conocen algoritmos eficientes que resuelven el problema con 3 varillas de manera óptima, no se han encontrado aún sus contrapartidas para cualquier número (N igual o superior a 3) de ellas.

Otra manera de resolverlo es basándose en el disco más pequeño, en este caso el de hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar. El disco número dos por regla, se debe mover a la varilla número tres. Luego el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuación se mueve el disco que sigue de la varilla uno, en este caso el disco número tres, y se coloca en la varilla dos. Finalmente el disco número uno regresa de la varilla tres a la uno (sin pasar por la dos) y así sucesivamente. Es decir, el truco está en el disco más pequeño

LEYENDA SOBRE LAS TORRES DE HANOI

En un templo de Benarés, se encontraba una cúpula que señalaba el centro del mundo. Allí estaba una bandeja sobre la cual existían tres agujas de diamante. En una mañana lluviosa, un rey mandó a poner 64 discos de oro, siendo ordenados por tamaño: el mayor en la base de la bandeja y el menor arriba de todos los discos.

Después de la colocación, los sacerdotes del templo intentaron mover los discos entre las agujas, según las leyes que se les habían entregado: "El sacerdote de turno no debe mover más de un disco a la vez, y no puede situar un disco de mayor diámetro encima de otro de menor diámetro".

Hoy no existe tal templo, pero el juego aún perduró en el tiempo...

Otra leyenda cuenta que Dios al crear el mundo, colocó tres varillas de diamante con 64 discos en la primera. También creó un monasterio con monjes, los cuales tienen la tarea de resolver esta Torre de Hanói divina. El día que estos monjes consigan terminar el juego, el mundo acabará.

No obstante, esta leyenda resultó ser un invento publicitario del creador del juego, el matemático Éduard Lucas. En aquella época, era muy común encontrar matemáticos ganándose la vida de forma itinerante con juegos de su invención, de la misma forma que los juglares hacían con su música. No obstante, la falacia resultó ser tan efectista y tan bonita, que ha perdurado hasta nuestros días. Además, invita a realizarse la pregunta: "si la leyenda fuera cierta, ¿cuándo será el fin del mundo?".

El mínimo número de movimientos que se necesita para resolver este problema es de 2⁶⁴-1. Si los monjes hicieran un movimiento por segundo, los 64 discos estarían en la tercera varilla en algo menos de 585 mil millones de años. Como comparación para ver la magnitud de esta cifra, la Tierra tiene como 5 mil millones de años, y el Universo entre 15 y 20 mil millones de años de antigüedad, sólo una pequeña fracción de esa cifra.

¿QUE SON LAS TORRESDE HANOI?

Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.

Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento.

El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.

Las reglas son:

• Sólo se puede mover un disco cada vez.
• Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
• Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

ALGORITMO TORRES DE HANOI

hanoi ( N, origen, destino, auxiliar )
{
si N0
entonces
hanoi(N - 1, origen, auxiliar, destino)
pasar disco N de origen a destino
hanoi(N - 1, auxiliar, destino, origen)
fin-si
}
sea máximo el número de discos total
sea destino el sitio final de máximo
sea disco = máximo

repita

mientras disco > 0 haga

si disco ya está en destino,
o bien, mover disco a destino tiene éxito entonces

si disco = máximo entonces
decremente máximo en 1

si máximo = 0 entonces
termine // solución lista
fin-si

sea destino el sitio final de máximo

fin-si

si_no

sea destino el sitio distinto de destino y del
sitio en donde está disco

fin-si

decremente disco en 1

fin-mientras

sean p y q los sitios distintos de destino
sea disco el menor de los discos de los topes de p y q
sea destino el sitio entre p y q con el mayor tope

fin-repita

}

ALGORITMO FACTORIAL DE UN NUMERO

Inicio

var: fact,resp;

principal

Escribir("Digite el número al que desea sacarle el factorial");
Leer(fact);resp=1si(fact=0);
escribir("fact=1");
sino
{
while(fact> o =1)resp=resp*factfact=fact - 1;
}
escribir("la respuesta del factorial es="+resp)

terminar

EL FACTORIAL DE UN NUMERO

import javax.swing.JOptionPane;
class factorial2
{
public static void main(String Args[])
{
/* estas lineas de codigo son la declaracion de las variables
int factorial[] = new int[999999];
int resto=0;
String strnumero;
int intnumero;
int a=1, d=0, f=0;
factorial[0] = 1;
/* aqui le pedimos al usuario el numero que desea el factorial

strnumero = JOptionPane.showInputDialog( "Ingrese el numero" );

/*aqui lo guardamos
intnumero = Integer.parseInt( strnumero );
for(;a<=intnumero;a++) { if(a%500 == 0) System.out.println(a); /*esto es para que el usuario sepa por que nmero va.*/ for(d=0;d<=f;d++) { /*voy recorriendo los indices del array hasta llegar al indice maximo hasta el momento*/ factorial[d] = factorial[d] * a + resto; resto = factorial[d] / 10; /*el factorial se divide entre 10 para que la variable int me elimine el ultimo numero*/ factorial[d] = factorial[d] - (resto*10); /*con esto obtengo el ultimo numero que es el que se quedara en el array*/ } d--; for(;f>=d;)
{
if(resto==0)
{
break;
}
f++;

/*aqui es cuando aumento el indice del array a medida que lo voy necesitando*/

factorial[f] = factorial[f] * a + resto;
resto = factorial[f] / 10;
factorial[f] = factorial[f] - (resto*10);
}
}
System.out.print("El factorial de: "+intnumero+" es: ");
for(d=f+1;f>=0;f--)
{
System.out.print(factorial[f]);
}
System.out.println("\nEste numero tiene: "+d+" cifras");
}
}