Zadanie 3. Pary słów
W pliku tekstowym pary.txt znajduje się 500 par słów złożonych z liter alfabetu
angielskiego a, b, …, z. Każda para słów jest zapisana w osobnym wierszu. Słowa w wierszu
są oddzielone pojedynczym odstępem, a długość każdego z nich nie przekracza 50 znaków.
Pierwszych pięć wierszy pliku pary.txt zawiera następujące pary słów:
bcba babb
abaa ccc
bcb abbba
bca cdd
aadc ddcdccaba
Napisz program (lub kilka programów), który(-e) znajdzie(-ą) i da(dzą) odpowiedzi do
podanych zadań. Odpowiedzi do poszczególnych zadań zapisz w pliku wyniki3.txt.
Każdą odpowiedź poprzedź numerem oznaczającym zadanie.
Do dyspozycji masz plik pary_przyklad.txt, który zawiera 500 par słów. Odpowiedzi
dla tego pliku podano w treściach zadań. Możesz sprawdzać na nim działanie swojego
programu.
Uwaga: Pamiętaj, że Twój program musi ostatecznie działać na pliku pary.txt.
A(3, 4), A(6, 2), A(12, 1)
","solutions":[{"source":"maturaonline","label":"matura-online.pl","kind":"text","html":"Odpowiedź: 3.1. gpeeazeugmvsbzwsrxfplqdbakoxxe lhpbmoirdm — wartość 2206 3.2. aacbcccaacacbcabac cccccaaaacaccbabcba — suma 18 3.3. Siedem par: `` bbbbaabbababbaaaa baaaaabaaabbbabab 5 aababbbababbbbbbaab bbbbaabbababababa 7 aaaababaaaabbbb aabbbbbabbbaaaa 6 bbbbabaaabbbabb aaababaabbbbbbba 5 ccccabacbba acbbabcbcbcbaa 5 caabbccabccc cabccccabbaac 6 abaacabcccccabbbc abbbcbbbbbcabaca 5 ``
Treść zadania (CKE)
\n3.1 — suma kodów ASCII
\n```python
najw = 0
para = None
for wiersz in open('pary.txt'):
s1, s2 = wiersz.split()
r = abs(sum(map(ord, s1)) - sum(map(ord, s2)))
if r > najw:
najw, para = r, (s1, s2)
print(*para, najw)
```
3.2 — wspólne wystąpienia liter
\nDla każdej litery bierzemy minimum z liczby wystąpień w obu słowach:
\n```python
from collections import Counter
najw = 0
para = None
for wiersz in open('pary.txt'):
s1, s2 = wiersz.split()
c1, c2 = Counter(s1), Counter(s2)
suma = sum(min(c1[x], c2[x]) for x in set(c1) & set(c2))
if suma > najw:
najw, para = suma, (s1, s2)
print(*para, najw)
```
Bez Counter wystarczy tablica 26 liczników na słowo — zgodnie z duchem zadania.
\n3.3 — prefiksosufiks w obu kierunkach
\n```python
def najdluzszy(s1, s2):
best = 0
for k in range(1, min(len(s1), len(s2)) + 1):
if s1[:k] == s2[-k:]: # początek s1 = koniec s2
best = max(best, k)
if s2[:k] == s1[-k:]: # początek s2 = koniec s1
best = max(best, k)
return best
for wiersz in open('pary.txt'):
s1, s2 = wiersz.split()
d = najdluzszy(s1, s2)
if d >= 5:
print(s1, s2, d)
```
Złożoność O(n·L²) przy 500 parach i słowach do 50 znaków jest w zupełności wystarczająca — nie trzeba tu KMP ani haszowania.
\nPunktacja CKE
\nTypowy błąd: 3.2 — najczęstszy błąd to zliczanie sumy zamiast minimum. Definicja mówi min(d(x,s1), d(x,s2)), czyli ile razy litera występuje w obu słowach jednocześnie. Dla adabbcdde i aadabbbccdc litera b występuje 2 i 3 razy → wkład 2, nie 5. 3.3 — prefiksosufiks działa w dwie strony. To nie jest tylko „początek s1 = koniec s2". Trzeba sprawdzić oba kierunki i wziąć dłuższy z nich. W przykładzie z arkusza abbaabaa / baabaabba najdłuższy (baabaa, długość 6) pochodzi z kierunku „początek s2 = koniec s1" — kto sprawdza tylko jeden kierunek, znajdzie abba o długości 4 i odrzuci parę. Uwaga na warunek „co najmniej 5". Para z prefiksosufiksem długości dokładnie 5 spełnia warunek. Bez pliku źródłowego nie da się odtworzyć wyników. Plik pary.txt uczeń dostaje na egzaminie; powyższe odpowiedzi pochodzą z oficjalnych zasad oceniania CKE. Sens tego zadania to ćwiczenie algorytmu, nie zapamiętanie liczb.