elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recopilación Tutoriales y Manuales Hacking, Seguridad, Privacidad, Hardware, etc


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Comparacion de arrays y eliminacion de elementos iguales
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Comparacion de arrays y eliminacion de elementos iguales  (Leído 6,739 veces)
PeinSoR

Desconectado Desconectado

Mensajes: 2


Aún estoy en fase beta


Ver Perfil
Comparacion de arrays y eliminacion de elementos iguales
« 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
  1. #include<stdio.h>
  2. #define TC 5
  3. int main(){
  4. int a[5],b[5],c[5],d[5],i,j,k,x=0;
  5. //Elementos de los conjuntos
  6. printf("\nconjunto A:");
  7. for(i=0;i<TC;i++){
  8. printf("\nIngrese el elemento %d: ",i+1);
  9. scanf("%d",&a[i]);
  10. }
  11. printf("\nconjunto B:");
  12. for(i=0;i<TC;i++){
  13. printf("\nIngrese el elemento %d: ",i+1);
  14. scanf("%d",&b[i]);
  15. }
  16. //impresion de los elementos de los conjuntos
  17. printf("Sus conjuntos son: \n");
  18. printf("A={ ");
  19. for(i=0;i<TC;i++){
  20. printf("\t%d",a[i]);
  21. }printf("\t}\n");
  22. printf("B={ ");
  23. for(i=0;i<TC;i++){
  24. printf("\t%d",b[i]);
  25. }printf("\t}\n");
  26. //Resta de conjuntos (eliminar aquellos elementos que sean iguales)
  27. for(i=0;i<TC;i++){
  28. for(j=0;j<TC;j++){
  29. if(a[i]!=b[j]){
  30. c[k]=a[i];
  31. k++;
  32. }
  33.  }
  34. }
  35. //Resultado de la resta de conjuntos
  36. printf("La diferencia es: {");
  37. for(i=0;i<k;i++){
  38. printf(" %d ",c[i]);
  39. }printf("}");
  40. return 0;
  41. }


En línea

-PSR
Falo Zipo Pixote

Desconectado Desconectado

Mensajes: 143


Ver Perfil
Re: Comparacion de arrays y eliminacion de elementos iguales
« Respuesta #1 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];
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 Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Comparacion de arrays y eliminacion de elementos iguales
« Respuesta #2 en: 2 Junio 2022, 10:16 am »

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.


Código
  1.   k=0;
  2.   for(i=0;i<TC;i++){
  3.   for(j=0;j<TC && a[i]!=b[j];j++); // cuerpo vacio a proposito
  4.   if (j==TC) {
  5.         c[k]=a[i];
  6.         k++;
  7.         }
  8.    }
  9.  
Y la salida es

Código:
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.


Código
  1.  
  2.        k=0;
  3. for(i=0;i<TC;i++){
  4.   for(j=0;j<TC && a[i]!=b[j];j++); // cuerpo vacio a porposito
  5.           if (j==TC) {
  6.              c[k]=a[i];
  7.              k++;
  8.           }
  9.       }
  10.  
  11. for(i=0;i<TC;i++){
  12.   for(j=0;j<TC && b[i]!=a[j];j++); // cuerpo vacio a proposito.
  13.           if (j==TC) {
  14.             c[k]=b[i];
  15.             k++;
  16.         }
  17.    }

Y la salida es .

Código:
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
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: Comparacion de arrays y eliminacion de elementos iguales
« Respuesta #3 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
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:
Código:
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 Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Comparacion de arrays y eliminacion de elementos iguales
« Respuesta #4 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
  • 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
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: Comparacion de arrays y eliminacion de elementos iguales
« Respuesta #5 en: 13 Junio 2022, 15:31 pm »

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

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines