{"id":"informatyka-2016-maj-matura-rozszerzona/zad/6.3","paper_id":"informatyka-2016-maj-matura-rozszerzona","number":"6.3","points":5,"ptype":"open","subject":"informatyka","category":"matura","year":2016,"month":"maj","level":"rozszerzona","text":"Kontekst - patrz zadanie 6.1.\n\nW pliku dane_6_3.txt zapisano 3 000 par słów. Drugie słowo w każdej parze jest szyfrogramem pierwszego z nieznanym kluczem. Niektóre szyfrogramy są błędne (niektóre litery zakodowano z różnymi przesunięciami). Słowo ma zawsze tę samą długość co odpowiadający mu szyfrogram.\n\nFragment:\nZAWISLAK EFBNXQFP\nKRASZEWSKI XENFMRJFXV\n\nUwaga: Pierwsze słowo w pliku wynikowym to SMIGIELSKI.\n\nNapisz program, który wyszuka i wypisze te słowa z pliku dane_6_3.txt, które błędnie zaszyfrowano. Wynik zapisz w pliku wyniki_6_3.txt: każde słowo w osobnym wierszu, w porządku odpowiadającym kolejności tych słów z pliku z danymi.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n**Pierwsze słowa w pliku wynikowym:**\n\nSMIGIELSKI\nJANEK\nJANUSZEWSKI\nWOLAK\nGAJEK\nMROCZKOWSKI\nSZCZESNIAK\nCIESLINSKI\n(i więcej, w kolejności występowania)\n\n## Sposób 1 - wykrywanie błędu szyfrowania\n\n**Idea:** prawidłowy szyfr Cezara to **stałe przesunięcie** dla całego słowa. Dla każdej pary (jawne, szyfr) liczymy przesunięcie każdej litery `delta_i = (szyfr[i] - jawne[i]) mod 26`. Jeśli **wszystkie delta_i są równe** → szyfrowanie prawidłowe. Jeśli różnią się → BŁĘDNE.\n\n**Weryfikacja KRASZEWSKI → XENFMRJFXV:**\n- K(10) → X(23): delta = (23-10) mod 26 = 13\n- R(17) → E(4): delta = (4-17) mod 26 = -13 mod 26 = 13 ✓\n- A(0) → N(13): delta = 13 ✓\n- S(18) → F(5): delta = (5-18) mod 26 = -13 mod 26 = 13 ✓\n- Z(25) → M(12): delta = (12-25) mod 26 = -13 mod 26 = 13 ✓\n- E(4) → R(17): delta = 13 ✓\n- W(22) → J(9): delta = (9-22) mod 26 = -13 mod 26 = 13 ✓\n- S(18) → F(5): 13 ✓\n- K(10) → X(23): 13 ✓\n- I(8) → V(21): delta = 13 ✓\n\nWszystkie delta = 13 → szyfr **prawidłowy**, NIE dodajemy KRASZEWSKI do wyniku.\n\n## Sposób 2 - implementacja Python\n\n```python\ndef przesuniecie(jawny, szyfr):\n\"\"\"Zwraca delta = (szyfr - jawne) mod 26 dla pierwszej litery.\"\"\"\nreturn (ord(szyfr) - ord(jawny)) % 26\n\ndef czy_blednie_zaszyfrowane(jawne, szyfr):\nif len(jawne) != len(szyfr):\nreturn True # różna długość = błąd\ndelty = [(ord(s) - ord(j)) % 26 for j, s in zip(jawne, szyfr)]\nreturn len(set(delty)) > 1 # więcej niż jedno przesunięcie\n\nwynik = []\nwith open('dane_6_3.txt', encoding='utf-8') as fin:\nfor linia in fin:\ncz = linia.strip().split()\nif len(cz) != 2:\ncontinue\njawne, szyfr = cz\nif czy_blednie_zaszyfrowane(jawne, szyfr):\nwynik.append(jawne)\n\nwith open('wyniki_6_3.txt', 'w', encoding='utf-8') as fout:\nfor s in wynik:\nfout.write(s + '\\n')\n\nprint(\"Pierwsze 10:\")\nfor s in wynik[:10]:\nprint(s)\n\n**Spodziewany początek wyniku:**\nSMIGIELSKI\nJANEK\nJANUSZEWSKI\nWOLAK\nGAJEK\nMROCZKOWSKI\nSZCZESNIAK\nCIESLINSKI\n\n## Sposób 3 - C++\n\n```cpp\n#include \n#include \n#include \n#include \nusing namespace std;\n\nbool blednyszyfr(const string& jawny, const string& szyfr) {\nif (jawny.size() != szyfr.size()) return true;\nset delty;\nfor (size_t i = 0; i < jawny.size(); i++) {\nint d = ((szyfr[i] - jawny[i]) % 26 + 26) % 26;\ndelty.insert(d);\n}\nreturn delty.size() > 1;\n}\n\nint main() {\nifstream fin(\"dane_6_3.txt\");\nofstream fout(\"wyniki_6_3.txt\");\nstring jawny, szyfr;\nwhile (fin >> jawny >> szyfr) {\nif (blednyszyfr(jawny, szyfr)) fout << jawny << \"\\n\";\n}\nreturn 0;\n}\n\n## Sposób 4 - Pascal\n\n```pascal\nprogram Cezar63;\nvar fin, fout: TextFile; jawny, szyfr: String;\ni, d, d0: Integer; blad: Boolean;\nbegin\nAssignFile(fin, 'dane_6_3.txt'); Reset(fin);\nAssignFile(fout, 'wyniki_6_3.txt'); Rewrite(fout);\nwhile not Eof(fin) do begin\nReadln(fin, jawny, ' ', szyfr); // lub Read + Read\nblad := False;\nif Length(jawny) <> Length(szyfr) then blad := True\nelse begin\nd0 := ((Ord(szyfr[1]) - Ord(jawny[1])) mod 26 + 26) mod 26;\nfor i := 2 to Length(jawny) do begin\nd := ((Ord(szyfr[i]) - Ord(jawny[i])) mod 26 + 26) mod 26;\nif d <> d0 then begin blad := True; Break; end;\nend;\nend;\nif blad then Writeln(fout, jawny);\nend;\nCloseFile(fin); CloseFile(fout);\nend.\n\n## Reference informatyczny - kryptoanaliza szyfru Cezara\n\n> Reference - Wykrywanie błędu szyfru Cezara:\n> - **Cecha charakterystyczna**: prawidłowy szyfr Cezara ma **stałe przesunięcie** dla całego słowa.\n> - Algorytm wykrywania: oblicz przesunięcie dla każdej pozycji; jeśli przynajmniej dwa różne → BŁĘDNE.\n> - **Złożoność**: O(L) na słowo, gdzie L = długość słowa.\n>\n> Reference - Modulo z ujemnymi:\n> - `(szyfr - jawne) mod 26` może dać wartość ujemną w C++/Pascal.\n> - Zabezpieczenie: `((x % 26) + 26) % 26`.\n> - W Pythonie `(szyfr - jawne) % 26` zwraca zawsze 0 25 - bez problemu.\n>\n> Reference - Set zamiast porównania:\n> - Jeśli wszystkie elementy listy są takie same, `set(lista)` ma rozmiar 1.\n> - Bardzo elegancka kontrola jednorodności.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 6.3, max 5 pkt):\n> - **5 pkt** - poprawny plik wynikowy\n> - **3 pkt** - program odwrotny (przepisuje POPRAWNIE szyfrowane)\n> - **2 pkt** - wynik bez uwzględnienia zawijania (modulo 26)\n> - **0 pkt** - błędna albo brak\n>\n> **Uwaga: NIE PRZYZNAJE SIĘ 4 ani 1 PUNKTU.**\n\n## Typowe pułapki\n\n- **Odwrotny program** - wypisuje TYLKO poprawnie zaszyfrowane zamiast BŁĘDNE - strata 2 pkt.\n- **Modulo ujemne nieprawidłowe** - `(B - Z)` w C++ daje -24 (zamiast 2). Konieczne `((x % 26) + 26) % 26`.\n- **Brak modulo 26** - przesunięcia mogą wyjść spoza zakresu 0-25, ale wciąż być stałe; bez modulo program zwraca BŁĘDNE dla wszystkich.\n- **Porównanie pierwszej z drugą tylko** - błąd: trzeba sprawdzić, czy WSZYSTKIE delta są równe.\n- **Pominięcie pierwszego przesunięcia** - niektóre implementacje porównują delta[i] z delta[i-1]; trzeba pamiętać, żeby zacząć od i=1 lub i=2 (Pascal).\n- **Pomylenie kolejności** - w pliku jest \"JAWNE SZYFR\", nie odwrotnie.\n\n## Złożoność obliczeniowa\n\n- 3000 słów × max 30 znaków: O(N·L) = **O(90 000) operacji**.\n- Set/porównanie delta: O(L) na słowo.","image":null,"solution_image":null,"topics":null,"page_from":null,"source":"maturazai","answer_source":null,"answer_text_source":null,"solution_source":"maturazai","text_source":"maturazai","source_label":"Informatyka · Matura · maj 2016 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Kontekst - patrz zadanie 6.1.

\n

W pliku dane_6_3.txt zapisano 3 000 par słów. Drugie słowo w każdej parze jest szyfrogramem pierwszego z nieznanym kluczem. Niektóre szyfrogramy są błędne (niektóre litery zakodowano z różnymi przesunięciami). Słowo ma zawsze tę samą długość co odpowiadający mu szyfrogram.

\n

Fragment:
ZAWISLAK EFBNXQFP
KRASZEWSKI XENFMRJFXV

\n

Uwaga: Pierwsze słowo w pliku wynikowym to SMIGIELSKI.

\n

Napisz program, który wyszuka i wypisze te słowa z pliku dane_6_3.txt, które błędnie zaszyfrowano. Wynik zapisz w pliku wyniki_6_3.txt: każde słowo w osobnym wierszu, w porządku odpowiadającym kolejności tych słów z pliku z danymi.

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

Pierwsze słowa w pliku wynikowym:

\n

SMIGIELSKI
JANEK
JANUSZEWSKI
WOLAK
GAJEK
MROCZKOWSKI
SZCZESNIAK
CIESLINSKI
(i więcej, w kolejności występowania)

\n

Sposób 1 - wykrywanie błędu szyfrowania

\n

Idea: prawidłowy szyfr Cezara to stałe przesunięcie dla całego słowa. Dla każdej pary (jawne, szyfr) liczymy przesunięcie każdej litery delta_i = (szyfr[i] - jawne[i]) mod 26. Jeśli wszystkie delta_i są równe → szyfrowanie prawidłowe. Jeśli różnią się → BŁĘDNE.

\n

Weryfikacja KRASZEWSKI → XENFMRJFXV:

\n
  • K(10) → X(23): delta = (23-10) mod 26 = 13
  • R(17) → E(4): delta = (4-17) mod 26 = -13 mod 26 = 13 ✓
  • A(0) → N(13): delta = 13 ✓
  • S(18) → F(5): delta = (5-18) mod 26 = -13 mod 26 = 13 ✓
  • Z(25) → M(12): delta = (12-25) mod 26 = -13 mod 26 = 13 ✓
  • E(4) → R(17): delta = 13 ✓
  • W(22) → J(9): delta = (9-22) mod 26 = -13 mod 26 = 13 ✓
  • S(18) → F(5): 13 ✓
  • K(10) → X(23): 13 ✓
  • I(8) → V(21): delta = 13 ✓
\n

Wszystkie delta = 13 → szyfr prawidłowy, NIE dodajemy KRASZEWSKI do wyniku.

\n

Sposób 2 - implementacja Python

\n

```python
def przesuniecie(jawny, szyfr):
"""Zwraca delta = (szyfr - jawne) mod 26 dla pierwszej litery."""
return (ord(szyfr) - ord(jawny)) % 26

\n

def czy_blednie_zaszyfrowane(jawne, szyfr):
if len(jawne) != len(szyfr):
return True # różna długość = błąd
delty = [(ord(s) - ord(j)) % 26 for j, s in zip(jawne, szyfr)]
return len(set(delty)) > 1 # więcej niż jedno przesunięcie

\n

wynik = []
with open('dane_6_3.txt', encoding='utf-8') as fin:
for linia in fin:
cz = linia.strip().split()
if len(cz) != 2:
continue
jawne, szyfr = cz
if czy_blednie_zaszyfrowane(jawne, szyfr):
wynik.append(jawne)

\n

with open('wyniki_6_3.txt', 'w', encoding='utf-8') as fout:
for s in wynik:
fout.write(s + '\\n')

\n

print("Pierwsze 10:")
for s in wynik[:10]:
print(s)

\n

Spodziewany początek wyniku:
SMIGIELSKI
JANEK
JANUSZEWSKI
WOLAK
GAJEK
MROCZKOWSKI
SZCZESNIAK
CIESLINSKI

\n

Sposób 3 - C++

\n

```cpp
#include <iostream>
#include <fstream>
#include <string>
#include <set>
using namespace std;

\n

bool blednyszyfr(const string& jawny, const string& szyfr) {
if (jawny.size() != szyfr.size()) return true;
set<int> delty;
for (size_t i = 0; i < jawny.size(); i++) {
int d = ((szyfr[i] - jawny[i]) % 26 + 26) % 26;
delty.insert(d);
}
return delty.size() > 1;
}

\n

int main() {
ifstream fin("dane_6_3.txt");
ofstream fout("wyniki_6_3.txt");
string jawny, szyfr;
while (fin >> jawny >> szyfr) {
if (blednyszyfr(jawny, szyfr)) fout << jawny << "\\n";
}
return 0;
}

\n

Sposób 4 - Pascal

\n

```pascal
program Cezar63;
var fin, fout: TextFile; jawny, szyfr: String;
i, d, d0: Integer; blad: Boolean;
begin
AssignFile(fin, 'dane_6_3.txt'); Reset(fin);
AssignFile(fout, 'wyniki_6_3.txt'); Rewrite(fout);
while not Eof(fin) do begin
Readln(fin, jawny, ' ', szyfr); // lub Read + Read
blad := False;
if Length(jawny) <> Length(szyfr) then blad := True
else begin
d0 := ((Ord(szyfr[1]) - Ord(jawny[1])) mod 26 + 26) mod 26;
for i := 2 to Length(jawny) do begin
d := ((Ord(szyfr[i]) - Ord(jawny[i])) mod 26 + 26) mod 26;
if d <> d0 then begin blad := True; Break; end;
end;
end;
if blad then Writeln(fout, jawny);
end;
CloseFile(fin); CloseFile(fout);
end.

\n

Reference informatyczny - kryptoanaliza szyfru Cezara

\n
Reference - Wykrywanie błędu szyfru Cezara:
- Cecha charakterystyczna: prawidłowy szyfr Cezara ma stałe przesunięcie dla całego słowa.
- Algorytm wykrywania: oblicz przesunięcie dla każdej pozycji; jeśli przynajmniej dwa różne → BŁĘDNE.
- Złożoność: O(L) na słowo, gdzie L = długość słowa.

Reference - Modulo z ujemnymi:
- (szyfr - jawne) mod 26 może dać wartość ujemną w C++/Pascal.
- Zabezpieczenie: ((x % 26) + 26) % 26.
- W Pythonie (szyfr - jawne) % 26 zwraca zawsze 0 25 - bez problemu.

Reference - Set zamiast porównania:
- Jeśli wszystkie elementy listy są takie same, set(lista) ma rozmiar 1.
- Bardzo elegancka kontrola jednorodności.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 6.3, max 5 pkt):
- 5 pkt - poprawny plik wynikowy
- 3 pkt - program odwrotny (przepisuje POPRAWNIE szyfrowane)
- 2 pkt - wynik bez uwzględnienia zawijania (modulo 26)
- 0 pkt - błędna albo brak

Uwaga: NIE PRZYZNAJE SIĘ 4 ani 1 PUNKTU.
\n

Typowe pułapki

\n
  • Odwrotny program - wypisuje TYLKO poprawnie zaszyfrowane zamiast BŁĘDNE - strata 2 pkt.
  • Modulo ujemne nieprawidłowe - (B - Z) w C++ daje -24 (zamiast 2). Konieczne ((x % 26) + 26) % 26.
  • Brak modulo 26 - przesunięcia mogą wyjść spoza zakresu 0-25, ale wciąż być stałe; bez modulo program zwraca BŁĘDNE dla wszystkich.
  • Porównanie pierwszej z drugą tylko - błąd: trzeba sprawdzić, czy WSZYSTKIE delta są równe.
  • Pominięcie pierwszego przesunięcia - niektóre implementacje porównują delta[i] z delta[i-1]; trzeba pamiętać, żeby zacząć od i=1 lub i=2 (Pascal).
  • Pomylenie kolejności - w pliku jest "JAWNE SZYFR", nie odwrotnie.
\n

Złożoność obliczeniowa

\n
  • 3000 słów × max 30 znaków: O(N·L) = O(90 000) operacji.
  • Set/porównanie delta: O(L) na słowo.
"}]}