Algoritmia - En principio deberia ser trivial, pero...

 
Vista:

En principio deberia ser trivial, pero...

Publicado por NoExit (4 intervenciones) el 06/02/2007 11:22:35
Hola a todos, tengo problemas al intentar solucionar un algoritmo que en
principio parace casi trivial. El enunciado es el sgte.:

Dado un vector v de n elementos (pongamos en este caso 10)

v(1) =1
v(2) =2
v(3) =2
v(4) =2
v(5) =1
v(6) =2
v(7) =2
v(8) =2
v(9) =1
v(10)=1

queremos contar todas las subsecuencias de números pares con el mismo
numero de elementos separadas por uno o varios impares. En este caso,
el resultado seria 2 secuencias de 3 pares seguidas, concretamente:

v(2)=2
v(3)=2
v(4)=2
esta es la primera subsecuencia de pares, de 3 eltos (hasta aqui, hasta el elto. 4)
v(5)=1
este es el impar que rompe la subsecuencia
v(6)=2
v(7)=2
v(8)=2
esta es la segunda subsecuencia de pares, de otros 3 eltos (hasta aqui, hasta el elto. 8)

Hacer notar que si v(9) hubiese sido igual a 2 (v(9)=2), entonces no habria subsecuencias
repetidas, porque la segunda subsecuencia de pares, de v(6) a v(9), consta de 4 eltos.,
mientras que la subsecuencia inmediatamente anterior, de v(2) a v(4) posee 3 eltos.

Bueno, a ver que hacemos con esto los "algorimistas". Os aseguro que no es tan facil como
parece... con las soluciones basadas en algoritmos conocidos de busquedas, recorridos, etc
no doy con la tecla, me falla si una subsecuencia llega hasta el ultimo elto., si coge el
primero... desesperante.

Mil gracias a todos.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:En principio deberia ser trivial, pero...

Publicado por NoExit (4 intervenciones) el 06/02/2007 11:33:03
Se me olvidada, el ultimo algo. que estoy probando, que por fin parece que funciona, es el sgte. (esta implementado en Visual Basic, pero es una sintaxis muy sencilla, muy parecida a la de cualquier lenguaje "teorico"):

Dim v(7) As Integer, n As Integer, i As Integer, j As Integer, igual As Boolean, c As Integer

v(1) = 2
v(2) = 2
v(3) = 2
v(4) = 1
v(5) = 2
v(6) = 2
v(7) = 2

i = 1
n = 7

While i <= n - 1
j = i + 1
igual = True
c = 0
While igual And j <= n
If v(i) = v(j) Then
c = c + 1
j = j + 1
Else
igual = False
End If
Wend
MsgBox c + 1
i = j
Wend
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:En principio deberia ser trivial, pero...

Publicado por NoExit (4 intervenciones) el 06/02/2007 11:36:03
Sangro un poco el codigo para que sea algo más legible:

Dim v(7) As Integer, n As Integer, i As Integer, j As Integer, igual As Boolean, c As Integer

v(1) = 2
v(2) = 2
v(3) = 2
v(4) = 1
v(5) = 2
v(6) = 2
v(7) = 2

i = 1
n = 7

While i <= n - 1
j = i + 1
igual = True
c = 0
While igual And j <= n
If v(i) = v(j) Then
c = c + 1
j = j + 1
Else
igual = False
End If
Wend
MsgBox c + 1
i = j
Wend
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar