Przekładając tę definicję na prostszy język: aby tablice A i B były k-podobne, należy sprawdzić, czy:
- pierwsze k liczb tablicy A odpowiada ostatnim k liczbom tablicy B,
- ostatnie n-k liczb tablicy A odpowiada pierwszym n-k liczbom tablicy B.
Zadanie 1.1
W tym zadaniu mamy do czynienia z dwiema tablicami - A i B, o długości n.
przykład 2.
Znamy do niego odpowiedź, ale przerobię go dla przykładu.
Mamy dane:
n = 5, A = [4, 7, 1, 4, 5], B = [1, 4, 5, 4, 7], k = 2
Aby sprawdzić czy te tablice są k-podobne znając liczbę k, w przypadku gdy k = 2
, należy w pierwszym kroku sprawdzić, czy dwie pierwsze liczby tablicy A odpowiadają dwóm ostatnim liczbom tablicy B.
A = [4, 7, 1, 4, 5]
B = [1, 4, 5, 4, 7]
Zgadza się. Następnie należy sprawdzić, czy pozostałe liczby również sobie odpowiadają (jest ich n-k).
A = [4, 7, 1, 4, 5]
B = [1, 4, 5, 4, 7]
Zgadza się. Zatem podane tablice są k-podobne i odpowiedź to PRAWDA.
przykład 5.
W tym przykładzie musimy sprawdzić, czy tablice są k-podobne.
Mamy dane:
n = 5, A = [1, 2, 3, 4, 5], B = [3, 4, 5, 1, 2], k = 2, k-podobne = ?
Sprawdzamy czy pierwsze dwie liczby tablicy A odpowiadają dwóm ostatnim tablicy B.
A = [1, 2, 3, 4, 5]
B = [3, 4, 5, 1, 2]
Zgadza się. Teraz sprawdźmy czy pozostałe liczby również sobie odpowiadają:
A = [1, 2, 3, 4, 5]
B = [3, 4, 5, 1, 2]
Zgadza się, zatem odpowiedź to PRAWDA.
przykład 6.
W tym przykładzie musimy sprawdzić, dla jakiego k tablice będą k-podobne.
Mamy dane:
n = 9, A = [1, 1, 1, 1, 3, 1, 1, 1, 1], B = [3, 1, 1, 1, 1, 1, 1, 1, 1], k = ?, k-podobne = PRAWDA
Sprawdzając kolejne możliwości znajdujemy właściwą odpowiedź:
A = [1, 1, 1, 1, 3, 1, 1, 1, 1]
B = [3, 1, 1, 1, 1, 1, 1, 1, 1]
Znaleźliśmy podział, który dzieli te dwie tablice na dwie odpowiadające sobie części. Podział w tablicy A następuje za 4. elementem, zatem k = 4.
przykład 7.
W tym przykładzie znów musimy sprawdzić, czy tablice są k-podobne.
Mamy dane:
n = 6, A = [4, 2, 4, 4, 2, 6], B = [4, 4, 2, 6, 4, 2], k = 1, k-podobne = ?
Sprawdzamy czy pierwsza liczba tablicy A (tylko jedna, bo k = 1) odpowiada ostatniej liczbie tablicy B.
A = [4, 2, 4, 4, 2, 6]
B = [4, 4, 2, 6, 4, 2]
Nie zgadza się, 2 ≠ 4. Tablice nie są k-podobne, FAŁSZ.
Zadanie 1.2
Rozwiązanie w Pythonie:
def czy_k_podobne(n, A, B, k):
for i in range(k):
if A[i] != B[n-k+i]:
return False
for i in range(n-k):
if A[k+i] != B[i]:
return False
return True
Możemy korzystać jedynie z podstawowych operacji, zatem użycie Pythonowych slice'ów odpada. Możemy jednak używać pętli oraz ifów (obie to instrukcje sterujące).
W algorytmie najpierw sprawdzamy czy pierwsze k liczb tablicy A odpowiada ostatnim k liczbom tablicy B, a następnie sprawdzamy, czy ostatnie n-k liczb tablicy A odpowiada pierwszym n-k liczbom tablicy B.
Rozwiązanie w Pythonie, korzystające z funkcji zdefiniowanej w poprzednim podpunkcie.
def czy_podobne(n, A, B):
for k in range(n):
if czy_k_podobne(n, A, B, k):
return True
return False
W prostej pętli for sprawdzamy, czy istnieje takie k, dla którego tablice A i B są k-podobne.