Título: Comparacion de arrays y eliminacion de elementos iguales Publicado por: PeinSoR en 2 Junio 2022, 04:23 am Hola a todos! Quiero hacer un programa que compare dos arreglos y elimine aquellos elementos que sean iguales. Pero solo me imprime los elementos del primer arreglo 5 veces, ¿podrían ayudarme a decirme si mi lógica está bien? espero puedan ayudarme a solucionar mis dudas... :huh:
Código
Título: Re: Comparacion de arrays y eliminacion de elementos iguales Publicado por: Falo Zipo Pixote en 2 Junio 2022, 07:46 am Dando un vistazo por encima encuentro dos cosas:
1ª) En línea 4 declaras d[5] que luego no usas. 2ª) En línea 4 declaras c[5] que no tiene por qué ser del mismo orden que a[] y b[]. De hecho puede ser hasta el doble de grande. Ejemplo: si a[] = {0, 1, 2, 3, 4} y b[] = {5, 6, 7, 8, 9} ==> c[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Con lo que no puede imprimir a partir de c[5], c[6],... porque no existen. Además, el programa internamente tiene necesariamente que funcionar mal -aunque quizá no veas muestra relevante de ello por pantalla- en Código: c[k]=a[i]; Título: Re: Comparacion de arrays y eliminacion de elementos iguales Publicado por: dijsktra en 2 Junio 2022, 10:16 am Hay una pequeña confusion en lo que planteas.
Empiezo por la segunda - que creo que es la que quires realmente hacer. el mayor fallo es que no inicializas k y el bucle no es correcto. mira este. Código Y la salida es Código: A={ 1 2 3 4 5 } En el caso de la primera, es cierto que C puede llegar a ser la suma de A y B (si no tienen elementos en comun). Pon, por ejemplo, c[5+5] . El bucle se repite para ambos lados. Código
Y la salida es . Código: A={ 1 2 3 4 5 } Título: Re: Comparacion de arrays y eliminacion de elementos iguales Publicado por: Serapis en 8 Junio 2022, 13:20 pm Cabe aún una interpretación más... por eso es tan importante ser certero en la especificación de lo que se solicita...
Y es que se eliminen las copias, es decir que haya 1 única copia por cada elemento presente (en ambos arrays). Dados los arrays de ejemplo que presenta dijsktra: A={1,2,3,4,5} B={2,4,6,8,10} el resultado debería arrojar: C={1,2,3,4,5,6,8,10} Como se ve, los elementos eliminados son 2 y 4, que aparecen en ambos arrays, de los cuales por tanto se deja una sola copia: Comúnmente suele requerirse o necesitarse más a menudo esta 'interpretación' al hablar de 'retirar elementos iguales' (en realidad: eliminar copias de elementos iguales)... El procedimiento más simple, es insertar ordenadamente el array más corto en el más largo.... estando así los elementos ordenados, las múltiples copias d e cada elemento aparecen contiguas, luego bastan 2 bucles uno que recorre cada elemento único, y otro interno que busca para cada elemento siguiente al único si se repite a continuación, ...saltar... el bucle externo va así pasando cada elemento único a la salida. El método exacto puede varias según se quiera evitar el empleo de arrays auxiliares. Un algoritmo que hace esto muy eficiente (dadas ciertas restricciones*), es una versión del algoritmo 'counting-sort'. En general dicho algoritmo funciona con un solo array de entrada, pero puede rediseñarse para usar 2 o más arrays, en el pseudocódigo usamos con dos: Este es el pseudocódigo (una implementación) para counting sort... Código: entero j, k, n Comparar con las (escasas) modificaciones del algoritmo para cumplir el propósito requerido: Código: entero j, k, n Como se puede observar, se utilizan dos arrays adicionales, uno cuenta sobre su propio índice la cantidad de veces que aparece ese índice, es requisito para counting Sort, para la versión precisa, basta igualarlo a 1 o incluso usar un buleano. Se utiliza en la segunda parte dle algoritmo para recrear la salida. El segundo array es el que se devuelve. * El número mayor no debe ser muy grande (so pena de un gasto excesivamente grande de memoria adicional y quizás ralentización (si hay gran cantidad de ausencias), se aplica sólo a números enteros (preferentemente positivos, ...con negativos hay que rehacer el algoritmo para considerarlos). Es útil conocer de antemano el valor mayor... si no, supone un costo extra su búsqueda y es necesario para determina rel array auxiliar, para comprender la implicación de este array es preciso ejecutarlo con un pequeño array (por ejemplo 20) pero cuyo valor mayor fuere alto (por ejemplo 1 millón) respecto dle tamaño del array... en el caso del eejemplo propuesto, siendo 10 un valor (más alto del array) muy pequeño, no tiene repercusión a considerar. Título: Re: Comparacion de arrays y eliminacion de elementos iguales Publicado por: dijsktra en 9 Junio 2022, 10:52 am Lo que Serapis propone es emular la unión de conjuntos con vectores, dado que en su representación más básica en C, los conjuntos consisten en vectores con elementos no repetidos.
Un algoritmo que hace esto muy eficiente (dadas ciertas restricciones*), es una versión del algoritmo 'counting-sort'. ... Dicho brevemente, sea max(A) el maximo numero de A, N el tamaño de A y M el tamaño de B . Entonces la solucion de Serapis
en resumen, es una solución de compromiso, dependiendo del valor relativo del máximo y las longitudes de A y B se puede bajar en tiempo de N*M a lineal en N+M+max(A)... a base de invertir en memoria, que nunca baja,por supuesto... Bueno, no estoy muy seguro de lo que digo. CAUTION. Título: Re: Comparacion de arrays y eliminacion de elementos iguales Publicado por: Serapis en 13 Junio 2022, 15:31 pm en resumen, es una solución de compromiso, dependiendo de... Pues sí, es bastante certero tu análisis. Añadiría tan solo un pequeño detalle pasado por alto...Bueno, no estoy muy seguro de lo que digo. CAUTION. Si los arrays de entrada no están ordenados, cualquier otro método, exige sumar al tiempo total el de ordenar dichos arrays... en el método que yo propuse, este tiempo está incluido (siempre) en el proceso, lo que implica que el 'compromiso' debe valorarse adecuadamente (es decir hay más terreno a ese lado que considerar). |