Zadanie 1. Podobne tablice Niech n będzie dodatnią liczbą całkowitą, a A[1..n] i B[1..n] będą n-elementowymi tablicami liczb całkowitych. Dla nieujemnej liczby całkowitej k, gdzie k < n, powiemy, że tablice A i B są k-podobne, gdy A[1..k] = B[n-k+1..n] oraz A[k+1..n] = B[1..n-k]. Liczbę k nazywamy świadectem podobieństwa. Uwaga: dla k = 0 przyjmujemy, że prawdziwe jest A[1..0]=B[n+1..n].
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

Zadanie 1.1. Uzupełnij tabelę - wpisz w pustych kratkach odpowiednie wartości. W wierszu piątym i siódmym wpisz słowo PRAWDA, jeśli tablice A i B są k-podobne przy podanym k, albo FAŁSZ w przeciwnym wypadku. W wierszu szóstym wpisz takie k, dla którego tablice A i B są k-podobne.
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

Zadanie 1.2. Zapisz w wybranej przez siebie notacji (w postaci pseudokodu, listy kroków lub w wybranym języku programowania) funkcję czy_k_podobne(n, A, B, k), gdzie A i B są n-elementowymi tablicami liczb całkowitych. Wynikiem funkcji jest PRAWDA, jesli tablice A i B są k-podobne dla zadanego parametru k, natomiast FAŁSZ - w przeciwnym przypadku. Uwaga: w zapisie możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), odwoływanie się do pojedynczych elementów tablicy, porównywanie liczb, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje zawierające wyżej wymienione operacje. Specyfikacja: n - dodatnia liczba całkowita, A[1..n],B[1..n] - n-elementowe tablice liczb całkowitych, k - nieujemna liczba całkowita mniejsza niż n. Wynik: PRAWDA jeśli tablice A i B są k-podobne dla podanego parametru k, FAŁSZ w przeciwnym przypadku.

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.

Zapisz w wybranej przez siebie notacji funkcję czy_podobne(n, A, B), która dla danych tablic A i B daje odpowiedź PRAWDA, jeśli istnieje takie k, dla którego tablice A i B są k-podobne, natomiast FAŁSZ - w przeciwnym przypadku. Uwaga: w zapisie możesz skorzystać jedynie z operacji wymienionych w zadaniu 1.2. oraz funkcji czy_k_podobne(n, A, B, k) opisanej w zadaniu 1.2. Specyfikacja: Dane: n - dodatnia liczba całkowita, A[1..n], B[1..n] - n-elementowe tablice liczb całkowitych. Wynik: PRAWDA, jeśli istnieje takie k(0<=k<n), dla którego tablice A i B są k-podobne, FAŁSZ w przeciwnym przypadku.
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.