SoloCodigo

CLR: .Net / Mono / Boo / Otros CLR => VB .NET => Mensaje iniciado por: krnl64 en Miércoles 21 de Noviembre de 2007, 18:19

Título: Problema Con Un Algoritmo
Publicado por: krnl64 en Miércoles 21 de Noviembre de 2007, 18:19
Hola a todos.
Verán estoy intentando hacer un code que me elimine los elementos repetidos de un vector. Pero resulta que el code que he escrito falla a veces.
Le he dado 1000 vueltas y no se porqué falla (en teoria es correcto lo que he escrito)

Podrían ayudarme a resolver el problema ?
Mi code es este:

Código: Text
  1.  
  2.  
  3. Dim v() As Integer
  4.         Dim i As Integer
  5.         Dim j As Integer
  6.         Dim z As Integer
  7.  
  8.         Dim limit As Integer
  9.         Randomize()
  10.  
  11.         Console.WriteLine(Chr(10) & "Introduzca el numero de elementos del vector")
  12.         limit = Console.ReadLine
  13.  
  14.         ReDim v(limit - 1)
  15.  
  16.         For i = 0 To v.Length - 1
  17.             v(i) = Int(Rnd() * 10) + 1 'Console.ReadLine
  18.         Next
  19.  
  20.  
  21.           Console.Write(Chr(10) & "El contenido del vector es: ")
  22.  
  23.         For i = 0 To v.Length - 1
  24.             Console.Write(" " & v(i))
  25.         Next
  26.  
  27.             For i = 0 To UBound(v)
  28.  
  29.  
  30.                     For j = i + 1 To UBound(v) - 1 '' me adelanto una pos
  31.  
  32.                         If v(j) = v(i) Then '' Si son iguales...
  33.  
  34.                             For z = j To UBound(v) - 1        '' me pongo en la pos del elemento a borrar
  35.                             If (z <> UBound(v)) Then v(z) = v(z + 1) '' adelanto los elementos 1 lugar
  36.                             Next
  37.  
  38.                             ReDim Preserve v(UBound(v) - 1)
  39.  
  40.                         End If
  41.  
  42.  
  43.                     Next
  44.  
  45.             Next
  46.  
  47.         Console.Write(Chr(10) & "El contenido del vector es: ")
  48.  
  49.         For i = 0 To UBound(v)
  50.             Console.Write(" " & v(i))
  51.         Next
  52.  
  53. Console.ReadKey()
  54.  
  55.  
  56.  

Gracias
Título: Re: Problema Con Un Algoritmo
Publicado por: fORU- en Martes 4 de Diciembre de 2007, 07:58
tengo una duda companero hizo algun algoritmo? antes de empezar a programar
Título: Re: Problema Con Un Algoritmo
Publicado por: Nebire en Domingo 9 de Diciembre de 2007, 02:51
Es bueno que documentes el texto, de otro modo me obligas a estudiar TODO el código en vez de sólo la parte donde se supone que tienes dudas. Esto hace a menudo que los que puedan ayudarte pasen de hacerlo, ya que les fuerzas a realizar mucho más trabajo del que en principio parece.

Por ejemplo tu planteas que te da error al borrar, pero deberías plantearlo de modo distinto.

Resumo tu código:

1 pides un valor para tomarlo como límite superior de una matriz
2 redimensionas la matriz y la llenas con valores aleatorios.
3 muestras el contenido que 'salió'.
4a inicia el recorrido de la matriz en un bucle
--- 5a inicias un bucle en un índice mayor que el anterior recorriendo la misma matriz
------ 6 si el valor en el índice del bucle 5 es igual que el valor en el índice en el bucle 4 luego ...
--------- 7a inicias un bucle de igual índice que 5 (para la misma matriz)
------------ 8 preguntas: si el índice no es el límite del bucle entonces el valor del índice del bucle 7 toma el valor del índice inmediatamente superior.
------------ 9 reduces la matriz en un índice preservando lo que contenga
--------- 7b cierras el bucle 7
------ 6b cierras el condicional de igualdad
--- 5b cierras el bucle 5
4b cierras el priemr bucle

10 muestras de nuevo el contenido actual de la matriz.

a ) Bien, para empezar tu código falla en varias partes, no queda claro lo que quieres hacer y lo haces lento.

b ) deduzco que tu intención inicial es la de crear una matriz aleatoria y luego eliminar los repetidos. Para observar si todo va bien, primero exhibes la lista y la comparas al final con otra exhibición.

c ) te daré un ejemplo de lo que debe ser un planteamiento antes de ponerte a escribir líneas de código sin ton ni son:
Se pueden usar varios planteamientos, te pongo uno que es muy efectivo y fácil de programar aunque puede que no interese lo que hace previamente, en ese caso luego te propongo otro método adicional...
0 Lo primero sería ordenar la lista de menor a mayor ( usa matriz.sort )
1 creo una matriz alterna de mismo tamaño 'matrizTmp' : puntero=0: i=0: k=1
2a hacer lo siguiente
3a --- mientras m(i) <> m(k) luego matrizTmp(puntero)=matrizAlea(i)
-------- i= k : k=k +1 : puntero=puntero +1
-------- si k > limite superior de m luego exit mientras 3
----- fin mientras 3
4a --- mientras m(i)=m(k) luego
-------- k=k +1
-------- si k > limite superior de m luego exit mientras 4
----- fin mientras 4
2b hasta que k = limite superior de m

5 redim preserve matrizTmp(0 to puntero)          
6 compara ambas matrices exhibiendo m() y matrizTmp()

Como puedes ver al estar ordenado un elemento sólo debes compararlo con el siguiente mientras sea distinto (y no se alcance el final) se añade, si es igual se compara con el siguiente hasta que sea distinto o se alcance el final. Por tanto la matriz sólo se recorre una vez. Cierto que penaliza un poco el ordenar la lista. pero fíjate que tu recorres la matriz 3 veces de forma anidada por tanto para eliminar elementos repetidos de una matriz de 1000 elementos recorrerías 1000 millones de elementos, es decir 1000 al cubo es decir eterno... el método propuesto para 1000 elementos sólo recorre 999 elementos.

Usar un método similar al tuyo optimizándolo en el mejor de los casos produce un tiempo de cálculo de m elementos al cuadrado, es decir para 1000 elementos sería recorrer 1000 x 1000 ya que exige 2 bucles anidados. Esto a fin de cuentas supone el equivalente al tiempo de cálculo para un algoritmo de burbuja. Se puede optimizar bastante más pero al final será a lo sumo equivalente a la velocidad de cálculo que ordenando primero la matriz. Por tanto es lógico no añadir más código ni comerte la cabeza teneiendo en cuenta que el método sort ya provee toda esa lógica.

Este método puede no interesar si se da el caso de que NO deseamos modificar el orden de los elementos en la matriz. Entonces podemos hacer una de 2 cosas, o bien añadir unos pasos para tomar sólo: los elementos de la matriz m() (en el orden de esta matriz) que aparecen en la matrizTmp() (porque aún tenemos las 2 matrices) o directamente usar otro método distinto sin tener la lista ordenada.

En cualquier caso en tu código se registran varios fallos:
1 El primer bucle de los 3 anidados no debe ser completo si no desde 0 hasta el penúltimo elemento de la matriz que no se repite, como a priori no sabemos cual es se olvida el for y se usa un bucle Do --- loop (en su forma until o while)
2 el segundo bucle de los 3 anidados sólo es correcto en el principio, el final si debe ser el final de la matriz, sólo la primera vez, por tanto o usamos un puntero para el final que debe actualizarse o usamos nuevamente un bucle Do ... loop
3 el tercer bucle inicia correctamente (con el puntero actual del 2ª) pero como está mal el final de segundo, el tercero debe tener otro final que el que tiene actualmente. concretamente el mismo -1 que tenga el 2ª bucle, pero fíjate que si actualizáramos el puntero después del bucle debería ser una unidad menos, en cambio si lo actualizamos antes del bucle el puntero ya está fijado a un valor menos que en el 2º bucle.
4 el condicional dentro del segundo bucle que compara los elementos es correcto, pretendes entonces acercar el resto hasta el final una posición abajo; 2 cosas: a ) el condicional dentro del 3 bucle sobra, simplemente se hace la asignación. b ) se debe usar un puntero que antes del primer bucle debe valer lo mismo ubound (m)...éste puntero debe usarse como final para el segundo y tercer bucle, El puntero debe reducirse en uno cada vez que la condición del segundo bucle se da.
5 el redim preserve es una pérdida de tiempo si se hace demasiado contínuo, es muy útil pero debe limitarse lo más posible (para eso usamos el puntero).

Entonces usando tu mismo código quedaría algo como:

Código: Text
  1.  
  2. p= ubound(v)       ' pes un puntero para los bucles 2ª y 3ª
  3. i=0
  4. do until i=p      ' si hemos hallado 5 repes sobre 30 elementos, no deberemos ir más allá del elemento 25... se entioende ???
  5.       For j = i + 1 To p        ' se usa p, porque irá reduciéndose a medida que se hallen repes.
  6.             If v(j) = v(i) Then '' ok...
  7.                   p=p -1      ' si se halló un repe se reduce el puntero.
  8.                   For z = j To p           ' no debe compararse con los que ya sabemos repestidos, por eso usamos p
  9.                         v(z) = v(z + 1) '' ok...
  10.                   Next z                  
  11.             End If
  12.       Next j
  13.      i=i +1     ' aumentamos el contador del primer bucle.
  14. loop
  15.  
  16. ReDim Preserve v(0 to p)
  17.  
  18. ' no uses este algoritmo para matrices grandes será eterno... para -de 200-300 elementos todavía es lento pero sopotable... Te aconsejo que implementes el que te describo al principio.
  19.  
  20.  
  21.  

Por último,  si el bucle primero se recorre en sentido inverso se propiciará mover menos elementos que si los 2 lo recorren en el mismo sentido. (hará que sea más rápido). Al hacer esto se deben cambiar algunos punteros del interior de los otros bucles. Esto te lo dejo como ejercicio para ti...