Página 1 de 2 12 ÚltimoÚltimo
Resultados 1 al 20 de 25

Tema: Recursividad con vectores en Java

  1. #1 Recursividad con vectores en Java 
    Iniciado
    Fecha de ingreso
    Apr 2009
    Mensajes
    13
    Descargas
    1
    Uploads
    0
    Hola a todos,

    Estoy haciendo un programa en Java que me permita saber si un vector esta contenido en otro o viceversa, es decir si el primer vector esta contenido en el segundo. Para esto no hace falta que sean de la misma longitud. La unica restriccion en este programa es que el metodo que decide la solucion tiene que ser un metodo recursivo. Se me ha ocurrido ir llamando siempre al metodo con una casilla del vector menos, y en el momento que una de las casillas ya no pertenezca, salir del metodo, puesto que ya el vector no esta contenido. Cuando he querido implementarlo, tengo la duda de como hacerlo, para los dos vectores, es decir si son de la misma longitud, deberia de comprobarlo para los dos.¿Alguna idea?Una seria llamar dos veces a la funcion invirtiendo el orden de los vectores, pero no me convence mucho, pues la veo un poco "chapuza".

    Gracias de antemano a todos.
    ---------------
    Hispasat88
    Citar  
     

  2. #2  
    Moderador Global Avatar de hystd
    Fecha de ingreso
    Jul 2005
    Ubicación
    1, 11, 21, 1211...
    Mensajes
    1.596
    Descargas
    58
    Uploads
    0
    Un pequeño inciso... Si el vector contiene elementos que son de tipo básico (enteros, reales, coma flotante, caracteres, etc...), puedes convertir dicho vector a un String y usar el método int indexOf(String str) de la clase String, el cual devuelve el índice de la primera ocurrencia de la subcadena str en la cadena que invoca al método. Y del mismo modo el método int indexOf(String str, int fromIndex) que hace lo mismo, pero contando a partir del valor marcado por el argumento "fromIndex".

    Ahora bien, si los elementos del vector no tienen definido un método "toString" que los defina, o bien simplemente quieres implementar un algoritmo, o bien existe cualquier otra razón que impida usar el método indexOf comentado, entonces vamos a pensar cómo diseñar el algoritmo...

    Ok, Antes de nada... ¿Hay alguna condición que diga que los vectores están ordenados? (Suponemos que esta pregunta se puede realizar porque los elementos del vector poseen un criterio de comparación, o bien si son objetos, implementan la interfaz Comparable)

    Si es así, puedes realizar búsquedas binarias, es decir, dividir el vector en dos mitades, comparar el primer elemento de cada mitad con el primer elemento del vector, ves si es mayor, menor o igual y quedarte siempre con la mitad en la que es posible que esté contenido el subvector. En la siguiente iteración se hace una llamada recursiva, pero habiendo reducido el tamaño del vector a la mitad. Esto reduce bastante el coste en el peor de los casos a una cota superior O(log n).

    Piensa que para hacer recursividad hay que llegar a un caso base, de lo contrario, tendrías un bucle infinito que acabaría por desbordar la pila en donde se van almacenando las direcciones de retorno (RETN) de las llamadas a funciones (CALL).

    Si por contra los elementos del vector no tienen por qué estar ordenados, o simplemente se trata de elementos u objetos que no poseen un criterio de ordenación, entonces la cosa es un poco más delicada... (Supongo que la idea que voy a decir ahora es lo que de verdad te puede servir...)

    Tomas la longitud de ambos, si son iguales, quiere decir que los vectores han de ser idénticos (da igual decir que el vector A está contenido en B, que decir el vector B está contenido en A). Para ello básta con comparar el primer elemento de A con el primero de B, y si son distintos, el algoritmo finaliza, ya que es imposible que A esté contenido en B.

    Si los vectores son de distinto tamaño, lo que hacemos es dividir el vector más grande (por ejemplo, vector A) en tantas partes como sea de grande el vector más pequeño (por ejemplo, vector B). Ahora tenemos el vector A, dividio en X subvectores, cada uno, de longitud igual a la del vector B. (Nota que X = longitud(A) / longitud (B)). El resto de la división (longitud(A) mod longitud(B)), se descarta porque es más pequeño que el vector B, por tanto nunca podrá estar contenido B en este resto.

    Por cada subvector, comparas el primer elemento del vector A con el primero de B (nota como estamos en el caso 1: "los vectores tienen el mismo tamaño"). De forma que si dichos elementos son distintos, fin.

    Este algoritmo posee un coste O(n/m). Donde "n" es la longitud del vector más grande, y "m" la del más pequeño. Observa que si m=1, es decir, buscar un sólo elemento, el coste es lineal O(n), ya que habría que comparar todos los elementos del vector.


    Espero que te haya servido, o por lo menos haberte dado una idea de optimización bastante buena, o cercana a la óptima. Te dejo que implementes el código, y si hay problemas pues aquí andamos.

    Un saludo.
    El optimista tiene ideas, el pesimista... excusas

    Citar  
     

  3. #3  
    Moderador HH
    Fecha de ingreso
    Sep 2003
    Mensajes
    1.384
    Descargas
    21
    Uploads
    5
    Si el problema es saber si un vector esta dentro de otro o no, me parece que el algoritmo que contas hystd, falla.
    No hay (que yo sepa) algoritmos de reconocimiento de cadenas de orden (n/m) siendo n la longitud del vector en el que se busca otro de longitud m.

    Supon los siguientes vectores A = [1,2,3,1,2,3] B = [2,3,1]
    Segun leo, estas diciendo de dividir A en 2 y comparar los primeros elementos de ambas partes con el priemer elemento de B.
    1!=2 asi que segun tu algoritmo B no esta en A, pero es obvio que si esta.

    Mas alla de esto me parece que la idea de lo que pide Hispasat88 es simplemente hacer recursion sobre los vectores, sin ocuparse demasiado de ordenes de complejidad.

    Para implementar algoritmos recursivos, vienen muy los lenguajes funcionales, asi que dejo un algoritmo de reconocimiento de cadenas en haskell y solo resta pasarlo a java:

    Código:
    contiene :: Eq a => [a] -> [a] -> Bool
    contiene xs ys = con ([],xs) ys False
    
    con :: Eq a => ([a],[a]) -> [a] -> Bool -> Bool
    con (ys,x:xs) [] flag	= False
    con (ys,[]) (x:xs) flag	= True
    con (xs,[]) [] flag	= True
    con (xs,y:ys) (z:zs) flag	| y==z 			= con (xs++[y],ys) zs False
    			| y/=z && not flag	= con ([],xs++(y:ys)) (z:zs) True
    			| y/=z && flag		= con ([],xs++(y:ys)) zs False
    - Me desagrada
    - ¿Por qué?
    - No estoy a su altura.
    ¿Ha respondido así alguna vez un hombre?

    Friedrich Nietzsche



    Citar  
     

  4. #4  
    Moderador Global Avatar de hystd
    Fecha de ingreso
    Jul 2005
    Ubicación
    1, 11, 21, 1211...
    Mensajes
    1.596
    Descargas
    58
    Uploads
    0
    Cierto, me he esquivocado... Es lo que pasa cuando no coges papel y lapiz...

    Al dividir el vector grande en tantas partes como sea el vector pequeño, se están dejando subvectores sin comprobar... Ya me parecía a mi un poco extraña la complejidad, pero tampoco me paré a estudiarlo detenidamente.

    Bueno, ahora me tengo que ir, luego, cuando vuelva, me pondré y daré la solución buena, usando un algoritmo recursivo en java.

    Un saludo, y espero que me perdoneis por el lapsus.
    El optimista tiene ideas, el pesimista... excusas

    Citar  
     

  5. #5  
    Moderador Global
    Fecha de ingreso
    Aug 2005
    Mensajes
    6.279
    Descargas
    7
    Uploads
    0
    Yo haría una búsqueda binaria del primer elemento del vector que se desea buscar. De encontrarlo, comprobaría el resto de elementos secuencialmente. De no coincidir todos los elementos continuaría con la búsqueda binaria hasta encontrarlo o agotar el vector "continente".

    Salu2

    . . . . . . . . . . . . . . . . . . . .
    [[ NORMAS DEL FORO ]]
    . . . . . . . . . . . . . . . . . . . .
    __________
    Citar  
     

  6. #6  
    Moderador HH
    Fecha de ingreso
    Sep 2003
    Mensajes
    1.384
    Descargas
    21
    Uploads
    5
    Para poder hacer una busqueda binaria se necesita que el vector este ordenado (de alguna forma).


    Salduos
    - Me desagrada
    - ¿Por qué?
    - No estoy a su altura.
    ¿Ha respondido así alguna vez un hombre?

    Friedrich Nietzsche



    Citar  
     

  7. #7  
    Moderador Global Avatar de hystd
    Fecha de ingreso
    Jul 2005
    Ubicación
    1, 11, 21, 1211...
    Mensajes
    1.596
    Descargas
    58
    Uploads
    0
    Cierto, como ya dije antes:

    Antes de nada... ¿Hay alguna condición que diga que los vectores están ordenados? (Suponemos que esta pregunta se puede realizar porque los elementos del vector poseen un criterio de comparación, o bien si son objetos, implementan la interfaz Comparable)

    Si es así, puedes realizar búsquedas binarias, es decir, dividir el vector en dos mitades, comparar el primer elemento de cada mitad con el primer elemento del vector, ves si es mayor, menor o igual y quedarte siempre con la mitad en la que es posible que esté contenido el subvector. En la siguiente iteración se hace una llamada recursiva, pero habiendo reducido el tamaño del vector a la mitad. Esto reduce bastante el coste en el peor de los casos a una cota superior O(log n).
    Por eso fue lo primero que pregunté. De todas maneras sigo insistiendo en lo que comenté antes... si es por aprender, por necesidad, o porque si, entonces vale, pero de lo contrario, existe el método indexOf de la clase String, ya implementado.

    Por cierto me pondré con el tema en breve... cuando acabe os adjunto el código en java.

    Un saludo.
    El optimista tiene ideas, el pesimista... excusas

    Citar  
     

  8. #8  
    Iniciado
    Fecha de ingreso
    Apr 2009
    Mensajes
    13
    Descargas
    1
    Uploads
    0
    Los vectores son de enteros, pero no se permite el uso de la clase String como comentas, mi idea es primero ordenarlos los dos en el metodo main con algun algoritmo de ordenacion, da igual su complejidad, pues son para ejercicios muy basicos, luego si el primer vector tiene la misma longitud que el segundo, llamo a la funcion compruebaVectores con estos parametros:vectorA=vector mas grand;vectorB=vector mas pequeño; indice=0.

    En la funcion voy comprobando que el indice-elemento de vectorB, vectorB[indice], esta en vectorA con una busqueda binaria, si esta, vuelvo a llamar con estos parametros:
    -vectorA= vector mas grande
    -vectorB=vector mas pequeño
    -indice=indice+1(He aqui la cuestion)

    entonces el metodo comprobara pero ahora el siguiente elemento del vectorB, si estan todos acabara imprimendo k si esta contenido y si falla en alguno, imprimira que no.

    Si se da el caso de que los dos son iguales, pues comprobaria hasta acabar los dos.

    El problema es que no puedo utilizar el metodos "extraños" pues baja "sustancialmente" la nota.

    Cuando tenga el codigo terminado, lo subire en este mismo hilo.
    ---------------
    Hispasat88
    Citar  
     

  9. #9  
    Moderador Global Avatar de hystd
    Fecha de ingreso
    Jul 2005
    Ubicación
    1, 11, 21, 1211...
    Mensajes
    1.596
    Descargas
    58
    Uploads
    0
    Si no es una especificacion del problema que los vectores estén ordenados, entonces no entiendo bien, cual es el objetivo de ordenarlos, ya que si lo haces, pierdes toda la estructura del vector. En ningún momento se ha almacenado la posición en la que se encontraba el elemento antes de la ordenación, con lo cual, si no te dicen que los vectores están ordenados, el tema de buscar binariamente no es viable.

    Bueno, como dices que no importa los órdenes de complejidad temporal, pues el algoritmo es mucho más simple. Como dije, lo tendría "en breve", pero por falta de tiempo no he podido tenerlo antes...


    private static int posicion=-1;
    private static boolean encontrado=false;

    public static boolean comprueba(int v1[], int v2[], int pri){
    boolean fin=false;

    for (int i=0; i<v2.length && !fin; i++){
    if (v2[i]!=v1[pri+i]){
    fin=true;
    }
    }
    return !fin;
    }

    public static int busca(int v1[], int v2[], int indice){

    if(indice<(v1.length-v2.length)&&(!encontrado)){
    if (comprueba(v1, v2, indice)){
    posicion=indice;
    encontrado=true;
    }
    busca(v1, v2, indice+1);
    }
    return res;
    }
    }
    El método (o mejor dicho función) "busca", recibe los dos vectores, y un índice a partir del cual se va a realizar la búsqueda del vector v2 en el vector v1, y devuelve la posición de la primera ocurrencia del vector v2 en v1. Si no se encuentra, devuelve -1. También se podría haber codificado de forma tradicional siguiendo el esquema:

    si esCasoBase:
    resuelveCasoBase
    |en_otro_caso:
    llamadarecursiva
    operacion_tras_llamada_recursiva
    fin

    Por supuesto se puede adaptar de múltiples formas para que encuentre por ejemplo, todas las ocurrencias de v2 en v1, o la última ocurrencia de v2 en v1, etc...

    Un saludo.
    Última edición por hystd; 18-04-2009 a las 17:04
    El optimista tiene ideas, el pesimista... excusas

    Citar  
     

  10. #10  
    Moderador HH
    Fecha de ingreso
    Sep 2003
    Mensajes
    1.384
    Descargas
    21
    Uploads
    5
    Hispasat88, ahora que decis que primero ordenas los vectores, se me ocurre que el problema es si los elementos del vector A estan (todos) en el vector B, es decir es la relacion de contencion pero considerando a los vectores como conjuntos (donde no importa el orden de los elementos). Por favor aclara esto.

    Si esto es asi, el algoritmo que describis funciona (hay que ver como lo implementas).

    Hystd, a tu codigo lo cambiaria un poquito:
    Código:
    private static int posicion=-1;
    private static boolean encontrado=false;
    
    public static boolean comprueba(int v1[], int v2[], int pri){
    
    boolean fin=false; for (int i=0; i<v2.length && !fin; i++){
    if (v2[i]!=v1[pri+i]){
    fin=false;
    }else{fin=true}
    } return !fin;
    } public static int busca(int v1[], int v2[], int indice){
    if(indice<(v1.length-v2.length)&&(!encontrado)){
    if (comprueba(v1, v2, indice)){
    posicion=indice; encontrado=true;
    } busca(v1, v2, indice+1);
    } return posicion;
    } }
    De todas maneras, me parece que estos algoritmos si bien usan la tecnica de recursion, me parece que el problema (cualquiera de los dos posibles, ya sea que se condieren los vectores como n-uplas ordenadas o como simples conjuntos) deja entrever una esencia recursiva mas importante.


    Despues paso el codigo que puse en haskell a c o alguna especie de pseudocodigo.


    Saludos
    - Me desagrada
    - ¿Por qué?
    - No estoy a su altura.
    ¿Ha respondido así alguna vez un hombre?

    Friedrich Nietzsche



    Citar  
     

  11. #11  
    Moderador Global Avatar de hystd
    Fecha de ingreso
    Jul 2005
    Ubicación
    1, 11, 21, 1211...
    Mensajes
    1.596
    Descargas
    58
    Uploads
    0
    Marchi, creo que esa modificación no es correcta, ya que si el primer elemento no coincide, no es necesario seguir comparando, puesto que el resultado es falso, sin embargo si el último elemento resulta que si coincide, entonces fin=true; y a pesar de no coincidir, la función dice que si que son iguales... Esa modificación hubiera estado bien si la comparación hubiera sido (==) y no (!=, distinto de). En la siguiente llamada recursiva se comprobarán los siguientes elementos desplazados una posición a la derecha.

    Pero bueno, más que una cuestión de lógica con variables booleanas, la idea era darle al compañero una solución recursiva en java.

    En cuanto a la segunda modificación es verdad, es "posicion"... es lo que tiene la costumbre de usar la palabra "res" como variable para almacenar el resultado .

    Un saludo.
    Última edición por hystd; 18-04-2009 a las 19:09
    El optimista tiene ideas, el pesimista... excusas

    Citar  
     

  12. #12  
    Moderador HH
    Fecha de ingreso
    Sep 2003
    Mensajes
    1.384
    Descargas
    21
    Uploads
    5
    Si tenes razon, no se por que tuve todo el tiempo la sensacion de que en lugar de != habia un ==, por eso es que creia que estaba mal

    Lo que si, en la funcion busca terminas devolviendo res, se te debe haber pasado.

    Saludos
    - Me desagrada
    - ¿Por qué?
    - No estoy a su altura.
    ¿Ha respondido así alguna vez un hombre?

    Friedrich Nietzsche



    Citar  
     

  13. #13  
    Iniciado
    Fecha de ingreso
    Apr 2009
    Mensajes
    13
    Descargas
    1
    Uploads
    0
    No es necesario que los vectores esten ordenados, yo los ordeno, para realizar la busqueda binaria del elemento indice, pero no es necesario, tiene razon hystd, con la busqueda binaria pero no solo del primer elemento sino de cualquiera, si algun elemento falla, el vector ya no esta contenido en el vector superior. Con lo cual, solo aria falta un metodo que realizase la busqueda binaria del elemento vectorB[indice] y si esta llamar al mismo metodo con vectorB[indice+1] y si no esta, volver del metodo imprimiendo no esta contenido.

    Agradezco mucho vuestra ayuda y ya creo k tengo el problema bastante claro, solo me falta un poquillo de tiempo para implementarlo, pero muchas gracias.
    ---------------
    Hispasat88
    Citar  
     

  14. #14  
    Moderador Global Avatar de hystd
    Fecha de ingreso
    Jul 2005
    Ubicación
    1, 11, 21, 1211...
    Mensajes
    1.596
    Descargas
    58
    Uploads
    0
    Vaya mientras escribia, os habeis adelantado xD. Bueno, no pasa nada.

    Ahora entiendo más o menos tu idea de ordenar y hacer búsqueda binaria de cada uno de los elementos por separado... ordenas el vector grande, y buscas un elemento del pequeño en el grande siguiendo una búsqueda binaria no? y así sucesivamente con el resto de elementos del vector pequeño no?

    Bueno si es así, y suponiendo que el resultado fuera que "todos los elementos del vector pequeño están en el vector grande", sería una condición necesaria, pero no es suficiente... no te garantiza que esos elementos estén dispuestos de la misma manera que están en el vector pequeño.

    Por ejemplo...

    Vector grande: 3 5 2 1 4 6 (ordenado: 1 2 3 4 5 6)
    Vector pequeño: 1 2 6

    1 2 y 6 están contenidos en Vector grande. Pero sin embargo el resultado de la búsqueda es falso, puesto que el subvector: (1, 2, 6) no existe en Vector grande.

    Un saludo.
    El optimista tiene ideas, el pesimista... excusas

    Citar  
     

  15. #15  
    Moderador HH
    Fecha de ingreso
    Sep 2003
    Mensajes
    1.384
    Descargas
    21
    Uploads
    5
    Por eso es que digo que depende como sea el problema, quizas al decir que el vector A este en el B quiere decir que cada elemento del vector A este en el vector B. Lo cual serian hacer tamaño(A) busquedas binarias sobre B.

    El problema no esta bien aclarado de principio y por eso que estamos con tantas vueltas.


    Saludos
    - Me desagrada
    - ¿Por qué?
    - No estoy a su altura.
    ¿Ha respondido así alguna vez un hombre?

    Friedrich Nietzsche



    Citar  
     

  16. #16  
    Iniciado
    Fecha de ingreso
    Apr 2009
    Mensajes
    13
    Descargas
    1
    Uploads
    0
    Esque no es necesario que esten en el orden exacto, solo que esten todos los elementos. Esa es la idea que yo tenia, la de ordenarlos y la de ir buscando el elemento del vector pequeño en el vector grande.pero solo lo ordeno por no utilizar un metodo que busque sin el prerequisito de estar ordenado.

    en tu ejemplo, el vector pequeño si estaria contenido en el vector grande y si que devolveria true el metodo compruebaVectores.

    Siento si he escrito en algun sitio que debian estar en el mismo orden.

    un saludo
    ---------------
    Hispasat88
    Citar  
     

  17. #17  
    Moderador HH
    Fecha de ingreso
    Sep 2003
    Mensajes
    1.384
    Descargas
    21
    Uploads
    5
    No es que lo hallas escrito en algun lado, solo que hablar de contencion entre vectores lo hace de cierta forma implicito.


    Saludos
    - Me desagrada
    - ¿Por qué?
    - No estoy a su altura.
    ¿Ha respondido así alguna vez un hombre?

    Friedrich Nietzsche



    Citar  
     

  18. #18  
    Moderador Global Avatar de hystd
    Fecha de ingreso
    Jul 2005
    Ubicación
    1, 11, 21, 1211...
    Mensajes
    1.596
    Descargas
    58
    Uploads
    0
    Esque no es necesario que esten en el orden exacto
    ¬¬

    solo que esten todos los elementos
    Bueno, pues entonces tu solución radica como ya hemos comentado en ordenar el vector grande y hacer tantas busquedas binarias como elementos tenga el vector A.

    Un saludo.
    El optimista tiene ideas, el pesimista... excusas

    Citar  
     

  19. #19  
    Iniciado
    Fecha de ingreso
    Apr 2009
    Mensajes
    13
    Descargas
    1
    Uploads
    0
    Bueno despues de mas tiempo del esperado, ya tengo el primer codigo(ire modificandolo para que entren nuevos casos) del ejercicio que me ocupa. Muchas gracias por haberme ayudado, me han servido de mucho vuestros consejos. Da gusto como aconsejais a la gente, en otros foros la cosa hubiese sido bastante diferente. Este codigo no tiene en cuenta que los dos vectores sean iguales, pero para el ejercicio que pedian no ha de darse ese caso
    Código:
    public class VectoresContenidos {
    	
    	/**
    	 * Metodo para ordenar los vectores del ejercicio
    	 * @param v vector a ordenar
    	 */
    	public static void ordenacionBurbuja(int[]v){
    		int i=0;
    		int j=0;
    		int aux=0;
    		for(i=0;i<v.length;i++){
    			  for(j=0;j<v.length-1;j++){
    				  if(v[j]>v[j+1]){
    					  aux=v[j];
    					  v[j]=v[j+1];
    					  v[j+1]=aux;
    				  }
    			  }
    		 }
    	}
    
    	/**
    	 * Metodo recursivo para ver si un vector esta contenido en el otro
    	 * @param vec1 vector del que se comprobara si esta contenido
    	 * @param vec2 vector del que se comprobara si esta contenido
    	 */
    	public static boolean compruebaVectores(int[] vecMayor, int[] vecMenor, int indice){
    		if(indice>=vecMenor.length){
    			return true;
    			
    		}
    		for(int i=0;i<=vecMayor.length;i++){
    			if(busquedaBinariaNoRecursiva(vecMayor,vecMenor[indice])){
    				if(!compruebaVectores(vecMayor,vecMenor,indice+1)){
    					return false;
    				}else{
    					return true;
    				}
    				
    			}else{
    				return false;
    			}
    		}
    		return false;
    	}
    	
    	/**
    	 * Metodo no recursivo que busca si un elemento esta dentro de un vector		
    	 * @param vector vector donde se busca el elemento 
    	 * @param elemento elemento que queremos buscar dentro del vector
    	 */
    	public static boolean busquedaBinariaNoRecursiva(int[]vector,int elemento){
    		int inicio=0;
    		int fin=vector.length;
    		int posicion;
    		while(inicio<=fin){
    			posicion=(inicio+fin) / 2;
    			if(vector[posicion]==elemento){
    				return true;
    			}else{
    				if(vector[posicion]<elemento){
    					inicio=posicion+1;
    				}else{
    					fin=posicion-1;
    				}
    			}
    		}
    		return false;
    	}
    	
    	/**
    	 * Metodo Principal
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		
    		int[] vector1={1,2,3,4,6};
    		int[] vector2={1,2,3,4,6,7};
    		if(vector1.length>vector2.length){
    			ordenacionBurbuja(vector1);
    			if(compruebaVectores(vector1,vector2,0)){
    				System.out.println("El vector2 esta contenido en el vector1");
    			}else{
    				System.out.println("El vector2 no esta contenido en el vector1");
    			}
    		}
     		if(vector1.length<vector2.length){
    			ordenacionBurbuja(vector2);
    			if(compruebaVectores(vector2,vector1,0)){
    				System.out.println("El vector1 esta contenido en el vector2");
    			}else{
    				System.out.println("El vector1 no esta contenido en el vector2");
    			}
    		}
    		
    	}
    		
    }
    De nuevo muchas gracias. Se que es algo chapuzero, pero estoy empezando,
    ---------------
    Hispasat88
    Citar  
     

  20. #20  
    Moderador HH
    Fecha de ingreso
    Sep 2003
    Mensajes
    1.384
    Descargas
    21
    Uploads
    5
    Hola Hispasat88, el codigo creo que funciona, no lo mire mucho, pero al menos bubble sort y la busqueda binaria tienen "la apariencia" correcta.

    Siguiendo tu idea podrias cambiar bubble sort por quick sort o merge sort, que son bastante mas eficientes.


    Por otro lado, me parece que escribir tanto codigo para solucionar ese problema, no esta muy bien (ya se que estas empezando, asi que no lo tomes mal, sino como consejo). Ademas, terminas combirtiendo el problema en otro usando cosas no hechas de forma recursiva, como la ordenacion y la busqueda (que pueden hacerse recursivas de forma relativamente facil).

    Cuando uno esta empezando con la programacion (no creas que yo entiendo mucho de esto), suele complicarse las cosas mas de lo necesario.


    Asi que te incluyo una opcion, que sin ser muy eficiente, resuelve el problema pedido en forma enteramente recursiva y de forma mas simple.


    Código:
    public static boolean contiene(int v1[],int v2[],int i1,int i2)	// v1 contenido en v2?
    {
    	if(i2>=v2.length) return false;
    		
    	if(v1[i1]==v2[i2]) 
    		if(i1==v1.length-1) return true;
    		else return contiene(v1,v2,i1+1,0);
    	else return contiene(v1,v2,i1,i2+1);
    }

    Una cosa que seria interesante, relativa a la implementacion, es el tema de los argumentos de la funcion, lo mejor seria declarar los arreglos en forma global para no pasarlos como argumento a la funcion.


    No se si este bien para java, lo hice en c y lo pase segun el codigo que habias escrito. (no conosco java)

    Espero que te sirva.


    Saludos
    - Me desagrada
    - ¿Por qué?
    - No estoy a su altura.
    ¿Ha respondido así alguna vez un hombre?

    Friedrich Nietzsche



    Citar  
     

Temas similares

  1. Vectores de ataque del HTML 5
    Por LUK en el foro PROGRAMACION WEB
    Respuestas: 0
    Último mensaje: 11-07-2011, 15:05
  2. recursividad
    Por krizalid en el foro GENERAL
    Respuestas: 4
    Último mensaje: 29-06-2011, 04:45
  3. Suma de Dos Vectores
    Por yamteo en el foro PROGRAMACION DESKTOP
    Respuestas: 2
    Último mensaje: 29-05-2010, 10:10
  4. IDE Java 3D
    Por eduk15 en el foro GENERAL
    Respuestas: 1
    Último mensaje: 10-06-2009, 14:34
  5. duda recursividad pascal
    Por kamsky en el foro GENERAL
    Respuestas: 4
    Último mensaje: 10-04-2006, 15:19

Marcadores

Marcadores

Permisos de publicación

  • No puedes crear nuevos temas
  • No puedes responder temas
  • No puedes subir archivos adjuntos
  • No puedes editar tus mensajes
  •