Wspólne Elementy Trzech Tablic

Zadanie

Dane są trzy posortowane tablice liczb całkowitych. Zadanie polega na znalezieniu wszystkich liczb, które występująca na każdej z trzech tablic. Innymi słowy należy znaleźć przecięcie trzech tablic. Zakładamy, że tablice nie mają powtarzających się elementów.

Przykładowo dla następujących tablic:

1. 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
2. 3 6 9 12 15 18 21 24 27 30
3. 4 8 12 16 20 24 28 32

Program powinien zwrócić, że powtarzającymi się elementami we wszystkich tablicach są elementy 12 oraz 24.

Rozwiązanie

Algorytm

W celu rozwiązania powyższego zadania w czasie liniowym należy zadeklarować trzy indeksy i₁, i₂ i i₃. Po jednym dla każdej tablicy. Następnie jeśli pod wskazanymi indeksami jest ta sama wartość to wszystkie indeksy należy zwiększyć. Jeśli jednak są różne wartości to: indeks i₁ zostaje zwiększony, gdy element i₁ pierwszej tablicy jest mniejszy od elementu na pozycji i₂ w drugiej tablicy. Analogicznie należy postąpić dla tablicy drugiej i trzeciej. Z kolei indeks trzeciej tablicy jest zwiększany, gdy nie są spełnione dwa wcześniejsze warunki. Algorytm kończy działanie, gdy k-ty indeks wykroczy poza granice k-tej tablicy.

Przykład

Dane są następujące tablice:

1. 1 3 5 7 9 12
2. 3 4 5 12
3. 3 6 9 12 15

Program wykona następujące operacje:

W podanych tablicach znalezione zostały tylko dwa powtarzające się elementy: 3 oraz 12.

Implementacja

Oto przykładowa implementacja funkcji znajdzWspolneElementy(). Funkcja nie zwraca żadnej wartości, ponieważ znalezione przecięcie tablic wypisuje bezpośrednio na konsole.

1. void znajdzWspolneElementy(int* tab1, int n1, int* tab2, int n2, int* tab3, int n3) {
2.   int i1 = 0, i2 = 0, i3 = 0;
3.   while (i1 < n1 && i2 < n2 && i3 < n3) {
4.     if (tab1[i1] == tab2[i2] && tab1[i1] == tab3[i3]) {
5.       cout << tab1[i1] << " ";
6.       i1++;
7.       i2++;
8.       i3++;
9.     } else {
10.       if (tab1[i1] < tab2[i2]) {
11.         i1++;
12.       } else if (tab2[i2] < tab3[i3]) {
13.         i2++;
14.       } else {
15.         i3++;
16.       }
17.     }
18.   }
19. }

(2.) Przygotuj indeksy, a następnie (3.) rozpocznij wyszukiwanie w pętli, aż w której z tablic zabraknie elementów. (4.) Jeśli zostanie znaleziony element we wszystkich tablicach to: (5.) wypisz go i (6. - 8.) zwiększ wszystkie indeksy. (9.) Jednak w przeciwnym przypadku (10. - 16.) zwiększ odpowiedni indeks.

Testowanie funkcji

Oto przykładowy kod, który wczyta od użytkownika wszystkie tablice, a następnie wywoła funkcję poszukującą przecięcia trzech tablic.

1. int* wczytajTablice(int i, int &n) {
2.   cout << "Podaj ile elementow ma tablice:\n n" << i << " = ";
3.   cin >> n;
4.   int* tab = new int[n];
5.   for (int i = 0; i < n; i++)
6.     cin >> tab[i];
7.   return tab;
8. }
10. int main () {
11.   int n1, n2, n3;
12.   int* tab1 = wczytajTablice(1, n1);
13.   int* tab2 = wczytajTablice(2, n2);
14.   int* tab3 = wczytajTablice(3, n3);
15.   znajdzWspolneElementy(tab1, n1, tab2, n2, tab3, n3);
16.   system("pause");
17.   return 0;
18. }

• Kod źródłowy Implementacja