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. def znajdzWspolneElementy(tab1, tab2, tab3):
2.   i1, i2, i3 = 0, 0, 0
3.   while (i1 < len(tab1) and i2 < len(tab2) and i3 < len(tab3)):
4.     if(tab1[i1] == tab2[i2] and tab1[i1] == tab3[i3]):
5.       print(str(tab1[i1]))
6.       i1 = i1 + 1
7.       i2 = i2 + 1
8.       i3 = i3 + 1
9.     else:
10.       if(tab1[i1] < tab2[i2]):
11.         i1 = i1 + 1
12.       elif(tab2[i2] < tab3[i3]):
13.         i2 = i2 + 1
14.       else:
15.         i3 = i3 + 1

(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. - 15.) 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. print("Podaj tablicę 1:")
2. tab1 = [int(x) for x in input().split()]
3. print("Podaj tablicę 2:")
4. tab2 = [int(x) for x in input().split()]
5. print("Podaj tablicę 3:")
6. tab3 = [int(x) for x in input().split()]
7. znajdzWspolneElementy(tab1, tab2, tab3)

• Kod źródłowy Implementacja