Ayuda urgente please :D

[ricardosoto]

Hola compañeros chilecompartanos, soy nuevo por estos lados y en realidad no estoy muy seguro si este tema va aqui, asi que si no corresponde ruego me informen donde va.

 

ON TOPIC

 

resulta que con todo el agetreo de terminar el primer semestre en mi universidad, tengo como ultima instancia pasar el ramo haciendo una tarea, lamentablemente la tarea trata de materia que no habiamos alcanzado a pasar, y en realidad no entiendo aabsolutamente nada de lo que hay que hacer...

 

tengo 3 opciones que las colocare a continuacion:

 

Alternativa 1: Sea K el conjunto de los Ruts, es decir de los números del 1 al 30.000.000 (no considerar el dígito verificador). Sea A un arreglo de 300 elementos. Sea h la función hash h(x)=x mod 300. Es decir, se toma el resto de la división de x por 300. (a) Implementar esta función hash en lenguaje Java. (b) Realizar, 100 veces, el siguiente experimento: generar Ruts en forma aleatoria, insertándolos en el arreglo usando la función h, hasta que se produzca la primera colisión. © calcular el promedio de las iteraciones realizadas en el experimento anterior.

 

Alternativa 2: Implemente en lenguaje Java una skip list, y escriba una función que entregue los cinco elementos más chicos de la skip list.

 

Alternativa 3: Implemente en lenguaje Java un programa que reciba como input un grafo y diga si el grafo es conexo, es decir si es posible ir desde cualquier nodo a cualquier otro nodo pasando por aristas del grafo

 

espero me puedan ayudar con mi trabajo y me ayuden a pasar mi ramo.

 

Desde ya muchas gracias a todos los que comenten, y a la persona que me ayude le estare eternamente agradecido, porque realmente ya no tengo otro recurso aparte de este.

 

 

P.D.1. ambas opciones deben ser en java

P.D.2. trabajo actualmente con NET BEANS

 

Saludos compañeros y espero sus respuestas

Edited October 11, 2011 by ricardosoto

[wtfbenja]

encontre la skiplist

 

http://www.mathcs.duq.edu/drozdek/DSinJava/SkipList.java

 

teni que aprender a busar los elementos mas chicos, y lo mas dificil seria llevarlo a buscar en la lista.

 

weno creo que es cosa de googlear porque el grafo conexo me tinca que esta en todas partes.

[ricardosoto]

encontre la skiplist

 

http://www.mathcs.du...a/SkipList.java

 

teni que aprender a busar los elementos mas chicos, y lo mas dificil seria llevarlo a buscar en la lista.

 

weno creo que es cosa de googlear porque el grafo conexo me tinca que esta en todas partes.

 

 

revise el codigo, esta entendible, el problema como dices tu es buscar el elemento mas pequeño, no se como debo hacerlo, porque implementar una skip list no es tan dificil, la complejidad radica en llevarlo a la lista, ademas de buscar el elemento mas pequeño, que la debo hacer por recurividad y me confundo demasiado en eso :S

 

gracias por responder loquillo... sigo escuchando respuestas

[Th3_K4T]

encuentro que el 1 es el más fácil, osea, tienes que hacer una función de hash, que te guarda un máximo de 300 ruts, es tan simple como recibir el rut, hacer mod, ponerlo en una parte del arreglo, y si se producen colisiones mostrar por pantalla un mensaje y agregar el rut en una lista contigua o algo así, dependiendo del algoritmo de hashing que utilices. Luego el tema de los números aleatorios es terriblemente fácil, es un simple for que genera números aleatorios en un cierto rango, el rango se maneja con mod.

 

 

Yo me iría por el 1.