 Autor
|
Tema: Comparacion de arrays y eliminacion de elementos iguales (Leído 6,220 veces)
|
PeinSoR
 Desconectado
Mensajes: 2
Aún estoy en fase beta
|
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...  #include<stdio.h> #define TC 5 int main(){ int a[5],b[5],c[5],d[5],i,j,k,x=0; //Elementos de los conjuntos for(i=0;i<TC;i++){ printf("\nIngrese el elemento %d: ",i +1); } for(i=0;i<TC;i++){ printf("\nIngrese el elemento %d: ",i +1); } //impresion de los elementos de los conjuntos printf("Sus conjuntos son: \n"); for(i=0;i<TC;i++){ for(i=0;i<TC;i++){ //Resta de conjuntos (eliminar aquellos elementos que sean iguales) for(i=0;i<TC;i++){ for(j=0;j<TC;j++){ if(a[i]!=b[j]){ c[k]=a[i]; k++; } } } //Resultado de la resta de conjuntos printf("La diferencia es: {"); for(i=0;i<k;i++){ return 0; }
|
|
|
|
|
En línea
|
-PSR
|
|
|
Falo Zipo Pixote
Desconectado
Mensajes: 143
|
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[k]=a[i]; cuando k>= 5, cuando intente asignar un valor a c[5], etc... que no existen. Ojo con estas cosas que C no avisa.
|
|
|
|
« Última modificación: 2 Junio 2022, 07:48 am por Falo Zipo Pixote »
|
En línea
|
|
|
|
dijsktra
Desconectado
Mensajes: 110
Mr Edsger Dijsktra (Tribute to)
|
Hay una pequeña confusion en lo que planteas. - si hablas de eliminar elementos iguales (como en la prosa), la operacion es A union B \ (A intersec. B) . Es decir A={1,2,3,4,5} B={2,4,6,8,10} C={1,3,5,8,10}, lo que dice Falo.
- si hablas de resta o diferencias de conjuntos (como en el programa), la operación es A\B, quitando del primero los del segundo. Es decir A={1,2,3,4,5} B={2,4,6,8,10} C={1,3,5}NO ES CONMUTATIVA (Esto es importante). a
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. k=0; for(i=0;i<TC;i++){ for(j=0;j<TC && a[i]!=b[j];j++); // cuerpo vacio a proposito if (j==TC) { c[k]=a[i]; k++; } }
Y la salida es A={ 1 2 3 4 5 }
B={ 2 4 6 8 10 }
La diferencia es: { 1 3 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. k=0; for(i=0;i<TC;i++){ for(j=0;j<TC && a[i]!=b[j];j++); // cuerpo vacio a porposito if (j==TC) { c[k]=a[i]; k++; } } for(i=0;i<TC;i++){ for(j=0;j<TC && b[i]!=a[j];j++); // cuerpo vacio a proposito. if (j==TC) { c[k]=b[i]; k++; } }
Y la salida es . A={ 1 2 3 4 5 }
B={ 2 4 6 8 10 }
La diferencia es: { 1 3 5 6 8 10 } |
|
|
|
« Última modificación: 2 Junio 2022, 10:18 am por dijsktra »
|
En línea
|
Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
|
|
|
|
Serapis
|
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... entero j, k, n
arrays C[],Salida[]
Si no se conoce el mayor de ambos arrays, buscarlo.
reservar memoria para el array C[0 a mayor]
bucle para k desde 0 a A.size -1
C[A[k]] +=1
siguiente
bucle para k desde 0 a B.size -1
C[B[k]] +=1
siguiente
n = (A.size + B.size)
k=0
j=0
reservar memoria para Salida[0 a n -1]
hacer mientras (k < mayor)
j = 1
bucle para j desde 0 a C[k]-1
Salida[j-1] = C[k]
j +=1
si (j > n) devolver Salida
siguiente
k += j
repetir
devolver Salida[]
El algoritmo es muy simple a pesar de la verbosidad mostrada... Comparar con las (escasas) modificaciones del algoritmo para cumplir el propósito requerido: entero j, k, n
arrays C[], Salida[]
Si no se conoce el mayor de ambos arrays, buscarlo.
reservar memoria para el array C[0 a mayor]
bucle para k desde 0 a A.size -1
si C[A[k]]== 0
n +=1
C[A[k]] =1
fin si
siguiente
bucle para k desde 0 a B.size -1
si C[B[k]]== 0
n +=1
C[B[k]] =1
fin si
siguiente
k=0
j=0
reservar memoria para Salida[0 a n -1]
hacer mientras (k < n)
si (C[k] > 0) // si (C[k] == 1)
Salida[j] = C[k]
j +=1
fin si
k +=1
repetir
devolver Salida[]
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. |
|
|
|
|
En línea
|
|
|
|
dijsktra
Desconectado
Mensajes: 110
Mr Edsger Dijsktra (Tribute to)
|
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 - Tiempo: O(max(A)+N+M)
- Memoria: O(max(A)+N+M)
La mía, (si implementese la uni'on de conjuntos, con memoria dinamica... etc) - Tiempo: O(N*M)
- Memoria: O(N+M)
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. |
|
|
|
|
En línea
|
Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
|
|
|
|
Serapis
|
en resumen, es una solución de compromiso, dependiendo de...
Bueno, no estoy muy seguro de lo que digo. CAUTION.
Pues sí, es bastante certero tu análisis. Añadiría tan solo un pequeño detalle pasado por alto... 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).
|
|
|
|
|
En línea
|
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
|
Problema eliminacion elementos
Programación Visual Basic
|
h0oke
|
1
|
1,401
|
31 Mayo 2009, 17:16 pm
por h0oke
|
|
|
|
Consulta SQL;Listar elementos que estan presentes en TODOS los elementos de otra
Desarrollo Web
|
astinx
|
2
|
4,847
|
2 Noviembre 2011, 23:06 pm
por astinx
|
|
|
|
problemas con comparación de arrays + presentación
Programación C/C++
|
doctore17
|
7
|
2,711
|
5 Diciembre 2014, 11:12 am
por Orubatosu
|
|
|
|
ayuda con la eliminacion de elementos repetidos en un vector en c++
Programación C/C++
|
abejaatareada
|
4
|
4,567
|
11 Mayo 2016, 13:39 pm
por kgarcia994
|
|
|
|
¿Existe algún algoritmo para escribir las pemutaciones de n elementos sin almacenar las de n-1 elementos?
Programación General
|
fzp
|
3
|
4,658
|
24 Octubre 2021, 23:06 pm
por fzp
|
 |
