[C++] Działania na zbiorach

[mario765i]

Witam!

Mam do napisania program takiej treści:

Wejście:
W pierwszej linii wejścia dana jest liczba \(\displaystyle{ n}\) (\(\displaystyle{ 1 \le n \le 10^6}\)) - rozmiar pierwszego zbioru. Następnie danych jest n różnych liczb całkowitych w porządku rosnącym (nie większych od \(\displaystyle{ 10^9}\)). W drugiej linii wejścia dana jest liczba \(\displaystyle{ m}\) (\(\displaystyle{ 1 \le m \le 10^6}\)) - rozmiar drugiego zbioru. Następnie danych jest m różnych liczb całkowitych w porządku rosnącym (nie większych od \(\displaystyle{ 10^9}\)).

Wyjście:
W pierwszej linii należy wypisać sumę zbiorów (w porządku rosnącym). W drugiej linii należy wypisać przekrój zbiorów (w porządku rosnącym). W trzeciej linii należy wypisać różnicę symetryczną zbiorów (w porządku rosnącym).

Przykład:

Kod: Zaznacz cały

Dla danych wejściowych:
10 2 3 5 6 7 9 10 12 14 16
10 3 4 6 7 9 11 12 14 15 16
poprawną odpowiedzią jest:
2 3 4 5 6 7 9 10 11 12 14 15 16
3 6 7 9 12 14 16
2 4 5 10 11 15

Oto napisany przeze mnie kod:

Kod: Zaznacz cały

#include<cstdio>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    int A[n];
    for (int i=0; i<n; i++) scanf("%d", &A[i]);

    int m;
    scanf("%d", &m);
    int B[m];
    for (int i=0; i<m; i++) scanf("%d", &B[i]);

    int C[n+m];
    for (int i=0; i<n; i++) C[i] = A[i];
    for (int i=0; i<m; i++) C[i+n] = B[i];

    sort(C, C+n+m);

    for (int i=0; i<n+m; i++)
       if ( C[i] != C[i+1] )
          printf("%d ", C[i]);

    printf("
");

    int k = 0;
    int D[k];
    for (int i=0; i<n; i++)
       for (int j=0; j<m; j++)
          if ( A[i] == B[j] )
          {
              D[k] = A[i];
              k = k+1;
          }

    for (int i=0; i<k; i++) printf("%d ", D[i]);

    printf("
");

    return 0;
}

Mój program wypisuje sumę zbiorów i przekrój zbiorów. Natomiast nie mam pojęcia, co należy dopisać, aby wypisywał również różnicę symetryczną zbiorów.
Programować zacząłem od niedawna, stąd moja prośba: Czy mógłby mi ktoś zmodyfikować ten program, aby spełniał wszystkie zalecenia podane w zadaniu?

[miki999]

Można skorzystać z definicji różnicy symetrycznej: \(\displaystyle{ A \dot{-} B = (A \cup B) \setminus (A \cap B)}\).
\(\displaystyle{ (A \cup B)}\)- masz, \(\displaystyle{ (A \cap B)}\)- również, zatem różnicą symetryczną będzie zbiór elementów należących do tablicy C i nienależących do tablicy D.

[t0m3k__]

Bierzesz każdą kolejną liczbę każdego zbioru i sprawdzasz czy jest w zbiorze drugim, jeśli nie ma to wypisujesz.

W przypadku Twojej interpretacji zadania można to rozwiązać w ten sposób:

Kod: Zaznacz cały

for (int i=0; i<n+m; i++)
  {
  if (C[i] == C[i+1])
     i++;
  else
  printf("%d ", C[i]);
  }

[mario765i]

Znam tę definicję różnicy symetrycznej, ale problem pozostaje. Mianowicie nadal należy obliczyć różnicę dwóch zbiorów \(\displaystyle{ ((A \cup B) \setminus (A \cap B))}\). A ja nie potrafię zaimplementować różnicy zbiorów. Pomoże mi ktoś?

-- 8 sty 2012, o 13:00 --

Bierzesz każdą kolejną liczbę każdego zbioru i sprawdzasz czy jest w zbiorze drugim, jeśli nie ma to wypisujesz.

W przypadku Twojej interpretacji zadania można to rozwiązać w ten sposób:
Kod:

Kod: Zaznacz cały

for (int i=0; i<n+m; i++)
  {
  if (C[i] == C[i+1])
     i++;
  else
  printf("%d ", C[i]);
  }

Owszem to działa, ale tylko wtedy, gdy zaimplementujemy ten kawałek kodu między implementacją sumy a przekrojem. A wynik różnicy symetrycznej ma być wyświetlony w trzeciej linii wyjścia (wymagania sprawdzarki).
Jeśli umieścimy ten kawałek kodu po implementacji przekroju, to otrzymamy błędny wynik. Wtedy różnica symetryczna to: 12 14 16 4 5 10 11 15.

[t0m3k__]

Dobrze działa, coś musiałeś namieszać przy tablicach, poprawiony program:

Kod: Zaznacz cały

#include<cstdio>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    int A[n];
    for (int i=0; i<n; i++) scanf("%d", &A[i]);

    int m;
    scanf("%d", &m);
    int B[m];
    for (int i=0; i<m; i++) scanf("%d", &B[i]);

    int C[n+m];
    for (int i=0; i<n; i++) C[i] = A[i];
    for (int i=0; i<m; i++) C[i+n] = B[i];

    sort(C, C+n+m);

    for (int i=0; i<n+m; i++)
       if ( C[i] != C[i+1] )
          printf("%d ", C[i]);

    printf("
");

	for (int i=0; i<n+m; i++)
	{
		if (C[i] == C[i+1])
		printf("%d ", C[i]);
	}
	
	printf("
");
	for (int i=0; i<n+m; i++)
	{
		if (C[i] == C[i+1])
		i++;
		else
		printf("%d ", C[i]);
	}
	printf("
");
	return 0;
}

[mario765i]

Rzeczywiście, masz rację, coś musiałem namieszać. Program działa poprawnie i szybko. Bardzo mi pomogłeś. Jeszcze raz wielkie dzięki.

[t0m3k__]

Parę lat w c++ nie pisałem ale wydaje mi się, że popełniłeś dość poważny błąd, mianowicie stworzyłeś tablicę bez zarezerwowanego miejsca

Kod: Zaznacz cały

    int k = 0;
    int D[k];

A później do niej zapisywałeś

Kod: Zaznacz cały

          if ( A[i] == B[j] )
          {
              D[k] = A[i];
              k = k+1;
          }

Stąd wystąpił błąd. Pilnuj tego, żeby tak nie robić, gdybyś operował na większych liczbach mógłbyś spowodować awarię systemu.

[Afish]

Chciałbym tylko zauważyć, że ten kod:

Kod: Zaznacz cały

 int n;
    scanf("%d", &n);
    int A[n];

jest niezgodny ze standardem języka.