HAMIJO INFORMATICO

Chorradas, videojuegos, cómics, literatura, pollas, DOLAN y otros temas serios.

HAMIJO INFORMATICO

Notapor Winters Of Sion » 29 Oct 2015 18:01



Entono el mea culpa de lo (gooby) del hilo pero necesito la ayuda de alguien parlante en código binario. Tengo que hacer un trabajo y hay una parte que no consigo descifrar por mucho que me cueste admitir. Puedo resolver el problema en O(n^2) pero hay que hacerlo en O(n).

El problema es el siguiente:

Aceptando cualquier array de números como input y asumiendo que están ordenados. Construye un algoritmo que busque dos elementos en el array si existe la diferencia entre ellos de exactamente 20.

Imprime los número si existen.

Dificultades. Nada de librerías, todo a pelo y sobretodo O(n). Técnicamente lo tengo que hacer en Java, pero me vale Pseudocode, PHP, Javascript, C...etc.

Yo ahora mismo: (guardiola)

GRASIAS DE ANTEBRASO LICENSIADOS
Bokononist.
Avatar de Usuario
Winters Of Sion
El Nigga 2012
 
Mensajes: 1298
Registrado: 29 Jul 2008 20:54

Re: HAMIJO INFORMATICO

Notapor S-----G » 29 Oct 2015 22:07

¿Qué es eso de O(n^2)? Es como la complejidad/profundidad del algoritmo no? Si lo refrescas asi un poco seria mas facil ayudarte XD

Ignorando lo de O(n^2) el problema en si parece sencillo.
Avatar de Usuario
S-----G
Staff, Gañan 2012
 
Mensajes: 10487
Registrado: 11 Nov 2008 14:24

Re: HAMIJO INFORMATICO

Notapor Winters Of Sion » 30 Oct 2015 00:34

S-----G escribió:¿Qué es eso de O(n^2)? Es como la complejidad/profundidad del algoritmo no? Si lo refrescas asi un poco seria mas facil ayudarte XD

Ignorando lo de O(n^2) el problema en si parece sencillo.


Básicamente quiere decir usa sola una iteración (Solo un for loop o while loop). Es una medida de eficiencia. Todos los demás los he hecho pero este es el de nota. Tengo hasta el sábado. (snurkel)
Bokononist.
Avatar de Usuario
Winters Of Sion
El Nigga 2012
 
Mensajes: 1298
Registrado: 29 Jul 2008 20:54

Re: HAMIJO INFORMATICO

Notapor S-----G » 30 Oct 2015 09:42

WTFFF ¿por que sale mi respuesta como parte de tu mensaje? Creo que le di a editar tu mensaje en vez de a citar. Edito e ltuyo y lo pongo aqui.

Si pongo alguna subnormalidad o no funciona perdoname pero me he despertado hace 5 minutos xD....en un rato me releo lo que he puesto que me tengo que ir a trabajar .Sabes el tamaño del array o puedes consultarlo ¿no? Pues tomando como V[0] la posicion inicial y V[n] la final. No se como se llama la funcion java de valor absoluto, creo que Abs.

Spoiler: mostrar
int i=0;
while (i+1!=null) do{
if ( Abs(V[i] - V[i+1] == 0) {
print(V[i];
print V[i+1];
}
else {
i++;
}
}


Mi algoritmo es profundamente subnormal y no hace lo que pedias, habia supuesto que solo habia que comprar numeros contiguos XDDD Ya me extrañaba que solo pudieras hacer esto. Pues mira lo mismo luego me entretengo en intentarlo (doge)
Avatar de Usuario
S-----G
Staff, Gañan 2012
 
Mensajes: 10487
Registrado: 11 Nov 2008 14:24

Re: HAMIJO INFORMATICO

Notapor AsbestosDeath » 30 Oct 2015 12:53

Si x es tu vector de números

Spoiler: mostrar
Código: Seleccionar todo
for ii = 1:length(x)-1
   x_r(ii)  = (x(ii) - x(ii+1)) == 20
end

for ii = 1:length(x_r)
   if x_r(ii) == 1;
      display (x(ii)); display(x(ii+1))
   end
end


Está en código Matlab pero se entiende bien, creo.
Es O(n) porque los dos bucles FOR no están anidados. En el primero construyes un vector nuevo en el que cada posición indica el resultado de la operación lógica de que dos elementos consecutivos de x se diferencian en 20.
En el segundo FOR recorres este vector y para cada 1 que encuentres (indicando un valor verdadero de lo anterior) pues imprimes el valor correspondiente en el vector x y su consecutivo.

Creo que está bien eso, vaya (guardiola)
psichoboy escribió:No pasa nada, Asbestos sigue siendo BOBO.
Avatar de Usuario
AsbestosDeath
Dronecracia Real
Dronecracia Real
 
Mensajes: 7486
Registrado: 12 Ago 2010 22:36
Ubicación: Your mom.

Re: HAMIJO INFORMATICO

Notapor S-----G » 30 Oct 2015 13:05

AsbestosDeath escribió:Si x es tu vector de números

Spoiler: mostrar
Código: Seleccionar todo
for ii = 1:length(x)-1
   x_r(ii)  = (x(ii) - x(ii+1)) == 20
end

for ii = 1:length(x_r)
   if x_r(ii) == 1;
      display (x(ii)); display(x(ii+1))
   end
end


Está en código Matlab pero se entiende bien, creo.
Es O(n) porque los dos bucles FOR no están anidados. En el primero construyes un vector nuevo en el que cada posición indica el resultado de la operación lógica de que dos elementos consecutivos de x se diferencian en 20.
En el segundo FOR recorres este vector y para cada 1 que encuentres (indicando un valor verdadero de lo anterior) pues imprimes el valor correspondiente en el vector x y su consecutivo.

Creo que está bien eso, vaya (guardiola)


Has hecho lo mismo que yo XD Solo comparas elementos contiguos. ¿Y si el elemento 3 y 8 se diferencian en 20?
Avatar de Usuario
S-----G
Staff, Gañan 2012
 
Mensajes: 10487
Registrado: 11 Nov 2008 14:24

Re: HAMIJO INFORMATICO

Notapor AsbestosDeath » 30 Oct 2015 13:08

No tenian que ser contiguos? xDDDDD

ED: ah pues no. PO PO POOOO
No se, si se me ocurre algo ya lo podre por aqui, si no esperemos a que venga el tarado a poner orden (gooby)
psichoboy escribió:No pasa nada, Asbestos sigue siendo BOBO.
Avatar de Usuario
AsbestosDeath
Dronecracia Real
Dronecracia Real
 
Mensajes: 7486
Registrado: 12 Ago 2010 22:36
Ubicación: Your mom.

Re: HAMIJO INFORMATICO

Notapor S-----G » 30 Oct 2015 13:17

Creo que simplemente hay qe jugar con el hecho de que te aseguran que estan ordenados, eso te permite resolverlo con un solo while pero hay que llevar el control de 2 punteros en vez de solo 1.
Avatar de Usuario
S-----G
Staff, Gañan 2012
 
Mensajes: 10487
Registrado: 11 Nov 2008 14:24

Re: HAMIJO INFORMATICO

Notapor S-----G » 30 Oct 2015 13:31

Un boceto no muy eficiente pero que quizas te ayude, no tengo ahora tiempo de explicarlo mucho xDD Llamo V al vector de tamaño n. He usado una funcion auxiliar diferencia para calcular si la diferencia es 20, se que no puedes usarlas pero es que ahora mismo no se como expresar matematicamente que la diferencia entre 2 enteros es de 20.

Código: Seleccionar todo
i=0;
j=1;
while ((i!=n) & (j!=n)){    //osea mientras ningun puntero haya llegado al final del array
 if ( diferencia( V[i], V [j]) == 20  ){  //encuentras 2 con diferencia 20
        print (V[i]);
        print (V[j]);
        j=j+1;   // aqui avanzas solo uno de los punteros para seguir comparandolo con el que apunta i, porque puede           haber valores iguales consecutivos
  }
 else if ((diferencia( V[i], V [j]) != 20 && (j!=n-1)){    // no son iguales los 2 que apuntas y aun no has llegado al final del vector, pues avanzas uno de ellos para mirar el siguiente
   j = j +1;
 }
 else {        //has llegado al final del vector con j, pues avanzas i y se repite el mismo proceso.
   i=i+1;
   j=j+1;
 }


}
Avatar de Usuario
S-----G
Staff, Gañan 2012
 
Mensajes: 10487
Registrado: 11 Nov 2008 14:24

Re: HAMIJO INFORMATICO

Notapor Winters Of Sion » 30 Oct 2015 15:17

Muchísimas gracias a los dos.

AsbestosDeath escribió:Está en código Matlab pero se entiende bien, creo.
Es O(n) porque los dos bucles FOR no están anidados.


Efectivamente LICENCIADO seria O(n). Lo explique mal antes. El Matlab se entiende pero que cosa más raruna.

Pero como te ha dicho S-G el problema es que no solo son contiguos los números.

S-----G escribió:Creo que simplemente hay qe jugar con el hecho de que te aseguran que estan ordenados, eso te permite resolverlo con un solo while pero hay que llevar el control de 2 punteros en vez de solo 1.


Ahi esta la clave el hecho que están ordenados. Pero tu código pinta interesante, a ver si lo implemento en Java ahora en un rato.

Igualmente no os voy a dejar con la duda y voy a postear la solución cuando este la semana que viene.

(snurkel)
Bokononist.
Avatar de Usuario
Winters Of Sion
El Nigga 2012
 
Mensajes: 1298
Registrado: 29 Jul 2008 20:54

Siguiente

Volver a Off Topic

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 12 invitados

cron
Top