SoloCodigo

Programación General => Java => Mensaje iniciado por: thepunishercadiz en Lunes 20 de Octubre de 2008, 12:10

Título: Muchas dudas
Publicado por: thepunishercadiz en Lunes 20 de Octubre de 2008, 12:10

Buenos días a todos.

Tras dar muchas vueltas y estrujarme el coco, acudo aquí a ver si podéis echarme una mano porque no doy pie con bola.

Muchas gracias por adelantado.

El problema es el siguiente:

El algoritmo que desean crear recibe la secuencia de caracteres en un contenedor de tipo Cola. Una vez ejecutado retorna también una cola con el resultado obtenido.
El algoritmo de encriptación es un algoritmo recursivo que actúa de la siguiente manera:
La secuencia de caracteres que se desea encriptar se divide en dos partes. Cada una de las partes tendrá un número de elementos igual si la secuencia fuera de orden par. En caso contrario, la segunda parte tendrá un elemento más que la primera. Se dará la vuelta (invertir el orden de los caracteres) a cada una de las partes. Se repetirá el proceso de división e inversión para cada una de las partes obtenidas hasta que éste sean tanto pequeñas que la inversión no tenga sentido. Como resultado, el algoritmo devolverá la concatenación de las dos partes alteradas.

Y esto es lo que he hecho:

public class Ejercicio3 {
   
   public static ColaVectorImpl<String> cargacola (){
      
      ColaVectorImpl <String> res = new ColaVectorImpl <String> ();
      
      //meter caracteres en la cola
      res.encolar("H");
      res.encolar("o");
      res.encolar("l");
      res.encolar("a");
      res.encolar(" ");
      res.encolar("a");
      res.encolar("m");
      res.encolar("i");
      res.encolar("g");
      res.encolar("o");
      
      return res;
   }
   
   public static ColaVectorImpl<String> inviertecola (ColaVectorImpl <String> c) {
      
      ColaVectorImpl <String> invertida = new ColaVectorImpl <String>();
      PilaVectorImpl <String> temp = new PilaVectorImpl <String> ();
      int i = 0;
      
      if (c.estaVacio())
         return c;
      
      if (c.numElems() == 1)
         return c;
      
      else
         for (i = 0; i < c.numElems(); i ++)
            temp.apilar(c.desencolar());
      
      
      for (i = 0; i < temp.numElems(); i ++)
         invertida.encolar(temp.desapilar());
      
      
      return invertida;
         
   }
   
   public static void main (String [] args){
      
      ColaVectorImpl <String> c1;
      
      int i = 0;
      String tira;
      
      
      c1 = cargacola();
      
      tira = c1.toString();
      System.out.println(tira);

      ColaVectorImpl <String> aux1 = new ColaVectorImpl <String> ();
      ColaVectorImpl <String> aux2 = new ColaVectorImpl <String> ();
      ColaVectorImpl <String> aux3 = new ColaVectorImpl <String> ();
      ColaVectorImpl <String> aux4 = new ColaVectorImpl <String> ();
      ColaVectorImpl <String> fin = new ColaVectorImpl <String> ();
      
      if ((c1.numElems()% 2) == 0) {
         
         for (i = 0; i < c1.numElems()/2 ; i++){
            aux1.encolar(c1.desencolar());
         }
         for (i = (c1.numElems()/2); i < c1.numElems(); i++){
            aux2.encolar(c1.desencolar());
         }
         
      }
      
      else {
         
         for (i = 0; i < (c1.numElems()/2)-1 ; i++){
            aux1.encolar(c1.desencolar());
         }
         for (i = (c1.numElems()/2); i < c1.numElems(); i++){
            aux2.encolar(c1.desencolar());
         }
      }
      
      aux3 = inviertecola(aux1);
      aux4 = inviertecola(aux2);
      
      for (i=0; i < aux3.numElems(); i++)
         fin.encolar(aux3.desencolar());
      
      for (i=0; i < aux4.numElems(); i++)
         fin.encolar(aux4.desencolar());

      
      tira = aux1.toString();
      System.out.println(tira);
   }
}

Título: Re: Muchas dudas
Publicado por: m0skit0 en Lunes 20 de Octubre de 2008, 13:22

Es un algoritmo perfecto para hacerlo con recursividad. La condición de parada sería que la longitud de la cadena sea 1 (que es cuando la inversión no tiene sentido). Cualquier duda vemos un poco de código.

Título: Re: Muchas dudas
Publicado por: thepunishercadiz en Lunes 20 de Octubre de 2008, 22:45

Cita de: "m0skit0"

Es un algoritmo perfecto para hacerlo con recursividad. La condición de parada sería que la longitud de la cadena sea 1 (que es cuando la inversión no tiene sentido). Cualquier duda vemos un poco de código.

Muchas gracias por tu respuesta moskito podríamos ver un poco de código? Estoy desesperao!!

Título: Re: Muchas dudas
Publicado por: m0skit0 en Martes 21 de Octubre de 2008, 10:18

La clase ColaVectorImpl , ¿tiene más métodos aparte de encolar(), desencolar(), numElems() y estaVacio()? ¿Hay atributos accesibles (públicos)?

Título: Re: Muchas dudas
Publicado por: thepunishercadiz en Martes 21 de Octubre de 2008, 18:43

Cita de: "m0skit0"

La clase ColaVectorImpl , ¿tiene más métodos aparte de encolar(), desencolar(), numElems() y estaVacio()? ¿Hay atributos accesibles (públicos)?

pues aparte tiene el constructor predeterminado y el sobrecargado con un número máximo de eltos. para el vector, un estaLLeno, primero() que devuelve sin extraer la cabeza de la cola y un iterador para ir recorriendo la estructura.

Gracias de nuevo!!

Título: Re: Muchas dudas
Publicado por: m0skit0 en Miércoles 22 de Octubre de 2008, 12:18

Supongo que encolar() mete un elemento al final de la cola y desencolar() saca uno del comienzo. Para devolver una parte de la cola (siendo indice el indicador de hasta qué posición de la cola (ésta incluída) vamos a devolver) invertida hacemos (con recursividad):

Código: Java

1. public static ColaVectorImpl<String> AntesDe_Invertida (ColaVectorImpl <String> c, int indice)
2. {
3.     String strtemp;
4.    
5.     if (c.estaVacio() || indice <= 0)
6.         return new ColaVectorImpl <String>();
7.     else
8.     {
9.         strtemp = c.desencolar();
10.         return AntesDe_Invertida(c, indice-1).encolar(strtemp);
11.     }
12. }
13.  

Ahora para hacer lo mismo pero con la parte de la cola posterior a indice (esta posición sin incluir), podemos hacer:

Código: Java

1. public static ColaVectorImpl<String> DespuesDe (ColaVectorImpl <String> c, int indice)
2. {   
3.     if (c.estaVacio() || indice <= 0)
4.         return c;
5.     else
6.     {
7.         c.desencolar();
8.         return DespuesDe(c, indice-1);
9.     }
10. }
11.  

Dado que este método no devuelve la cola ya invertida, necesitamos una función de inversión (de nuevo, con recursividad):

Código: Java

1. public static ColaVectorImpl<String> InvertirCola (ColaVectorImpl <String> c)
2. {
3.     String strtemp;
4.    
5.     if (c.numElems()<= 1)
6.         return c;
7.     else
8.     {
9.         strtemp = c.desencolar();
10.         return InvertirCola(c).encolar(strtemp);
11.     }
12. }
13.  

Dado que mi nivel de Java es bastante precario (por no decir inexistente :( ), disculpa mis errores de sintaxis. Aparte, no estoy seguro de si estos métodos modifican las colas pasadas como parámetro (creo que sí, prueba a ver).

Disculpa también :argh:  que no pueda probar el código, es que no tengo instalado Java SDK en el trabajo  :bad: .

Título: Re: Muchas dudas
Publicado por: thepunishercadiz en Jueves 23 de Octubre de 2008, 08:06

Tio muchas gracias!

Ayer no pude conectarme y acabo de ver tu mensaje. Lo probaré esta tarde a ver qué pasa.

De nuevo muchísimas gracias!!!

Título: Re: Muchas dudas
Publicado por: jotron en Lunes 3 de Noviembre de 2008, 18:54

Hola moskito tengo un problema parecido o casi igual lo unico que en vez de cadenas es con números
en el método main es cuando me hago un lío
la primera vez que llamamos a las funciones recursivas lo hace bien porque lo guardo en dos colas cola1 con la primera parte y cola2 con la segunda parte e invierto, ahora bien, la segunda vez me salen 4 colas la tercera 8 colas y la cuarta 16 colas, esto es un chapú no??? como podría implementar el main para hacer las llamadas a las funciones recursivas y que me lo vaya haciendo la inversión????
gracias de antetodo

Título: Re: Muchas dudas
Publicado por: jotron en Lunes 3 de Noviembre de 2008, 19:49

Cita de: "jotron"

Hola moskito tengo un problema parecido o casi igual lo unico que en vez de cadenas es con números
en el método main es cuando me hago un lío
la primera vez que llamamos a las funciones recursivas lo hace bien porque lo guardo en dos colas cola1 con la primera parte y cola2 con la segunda parte e invierto, ahora bien, la segunda vez me salen 4 colas la tercera 8 colas y la cuarta 16 colas, esto es un chapú no??? como podría implementar el main para hacer las llamadas a las funciones recursivas y que me lo vaya haciendo la inversión????
gracias de antetodo

Título: Re: Muchas dudas
Publicado por: m0skit0 en Martes 4 de Noviembre de 2008, 09:34

Cita de: "jotron"

esto es un chapú no???

Cita de: "jotron"

lo guardo en dos colas cola1 con la primera parte y cola2 con la segunda parte e invierto, ahora bien, la segunda vez me salen 4 colas la tercera 8 colas y la cuarta 16 colas

No te comprendo...  :wacko:

Título: Re: Muchas dudas
Publicado por: jotron en Jueves 6 de Noviembre de 2008, 14:11

Hola moskito,
Te explico tenemos los metodos recursivos AntesDe_Invertida, DespuesDe, InvertirCola que tu mismo explicaste.
pues yo en el metodo main hago esto
cad=AntesDe_Invertida(InvertirCola(cadena,cadena.numElems()/2));
cad1=DespuesDe(InvertirCola(cadena,cadena.numElems()/2));

entonces dado la cadena 12345678
esto me guarda en cad 4321 8765
Hasta aquí bien pero ahora no veo como seguir iterando para que me vuelva a dividir 4321.... y 5678 ... hasta que no tenga sentido su inversión, ya que el siguiente paso tendría que tener 4 cadenas 34   12     78    56 y así sucesivamente hasta que ya la inversión no tenga sentido.
y aqui me atasco la primera vez bien pero la segunda tengo 2 colas que dividir e invertir la tercera 4 colas y así hasta que pierda el sentido la inversión.
Me entiendes??
Gracias antetodo

Título: Re: Muchas dudas
Publicado por: m0skit0 en Jueves 6 de Noviembre de 2008, 14:39

Si quieres tener cada cadena por separado, vas a a necesitar tantas cadenas como elementos tenga la original, puesto que la inversión no tienen sentido sólo en el caso de 1 o menos elementos. De todas formas, no le veo la utilidad de llegar hasta el final, puesto que cada cadena contendrá un solo elemento. Podrías parar cuando las cadenas tengan 2 elementos, por tanto necesitarías tantas cadenas como la mitad de elementos que contenga la original.

Título: Re: Muchas dudas
Publicado por: jotron en Jueves 6 de Noviembre de 2008, 18:05

Gracias por tu contestación
Efectivamente tengo que parar cuando solo queden 2 que es cuando a partir de esta ya no tiene sentido.
Pero como creo las cadenas sin saber cuantas voy a tener???
porque la entrada puede ser los números que quieran 12345678910111213141516171819202122232425262728
para esta entrada tendré un número de colas para almacenar y posteriormente dividir e invertir para otra entrada mas corta otro número de colas.........
podías ponerme un ejemplo de como crear la colas? en funcion de los elementos de entrada.?
Gracias,

Título: Re: Muchas dudas
Publicado por: m0skit0 en Viernes 7 de Noviembre de 2008, 06:56

Cita de: "jotron"

Pero como creo las cadenas sin saber cuantas voy a tener???

:wacko: ¿Seguro que has leído la respuesta anterior?

Título: Re: Muchas dudas
Publicado por: kala en Domingo 9 de Noviembre de 2008, 07:22

Alguien podria poner el código entero del ejercicio que pedía thepunishercadiz, es que no acabo de ver como realizas la recursividad...

muchas gracias

Título: Re: Muchas dudas
Publicado por: m0skit0 en Domingo 9 de Noviembre de 2008, 12:47

viewtopic.php?f=32&t=37154#p135376 (http://foros.solocodigo.com/viewtopic.php?f=32&t=37154#p135376" onclick="window.open(this.href);return false;)

Título: Re: Muchas dudas
Publicado por: kala en Domingo 9 de Noviembre de 2008, 15:30

Gracias por responder moskito, yo lo que me refiero es si podrias dar el código del main principal o del metodo donde haces referencia a estos otros.
Mi duda esta en el momento de ir dividiendo entre dos las colas, no acabo de entender como lo haces.

Muchas gracias.

Título: Re: Muchas dudas
Publicado por: m0skit0 en Domingo 9 de Noviembre de 2008, 20:56

Yo no tengo el main(), tengo lo que se ha publicado en este post. No necesitas el main() para entender la recursividad. Si quieres, abre otro hilo especificando qué es exactmente lo que no entiendes y ya te lo explico. Un saludo