{"id":"informatyka-2015-maj-matura-rozszerzona/zad/3.2","paper_id":"informatyka-2015-maj-matura-rozszerzona","number":"3.2","points":3,"ptype":"open","subject":"informatyka","category":"matura","year":2015,"month":"maj","level":"rozszerzona","text":"Zadanie 3.2. (0-3)\nUzupełnij poniższą rekurencyjną funkcję obliczania pary liczb (x, y) dla danych liczb a, b.\nSpecyfikacja:\nDane:\nliczby całkowite a > 0 i b ≥ 0\nWynik:\npara liczb całkowitych (\n)\n,x y , dla których\n( , ) =\n⋅\n+ ⋅\nNWD a b\na x\nb y\nRozszerzonyEuklides(a, b):\nKrok 1.\nJeśli b = 0, podaj jako wynik funkcji parę (1, 0) i zakończ jej wykonywanie.\nKrok 2.\nr ← a mod b\nKrok 3.\n(x, y) ← RozszerzonyEuklides( , )\nKrok 4.\nPodaj jako wynik parę ( , ).\nMiejsce na obliczenia.\nWypełnia\negzaminator\nNr zadania\n3.1.\n3.2.\nMaks. liczba pkt.\n2\n3\nUzyskana liczba pkt.\nMIN_1R\nBRUDNOPIS (nie podlega ocenie)","answer":null,"answer_text":"Zadanie 3.2. (0-3)\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji z wykorzystaniem\nkomputera, z zastosowaniem podejścia\nalgorytmicznego.\nZdający opracowuje i przeprowadza wszystkie etapy\nprowadzące do otrzymania poprawnego rozwiązania\nproblemu: od sformułowania specyfikacji problemu\npo testowa nie rozwiązania (5.7.).\nZdający stosuje rekurencję w prostych sytuacjach\nproblemowych (5.9.).\nPoprawna odpowiedź\nKrok 3: (b, r).\nKrok 4: ( y, x - (a div b) • y).\nSchemat punktowania\n3 p. - za prawidłowo wypełnione pola w krokach 3 i 4 algorytmu.\n2 p. - za prawidłowo wypełnione pola w kroku 4 algorytmu.\n1 p. - za prawidłowo wypełnione pola w kroku 3 algorytmu albo za odpowiedź (y', x' - (a div b) • y').\n0 p. - za odpowiedź niepełną lub błędną albo za brak odpowiedzi.\nCzęść II","solution":"## Poprawna odpowiedź\n\n**Krok 3:** `(x, y) ← RozszerzonyEuklides(b, r)`\n\n**Krok 4:** `Podaj jako wynik parę (y, x - (a div b)·y).`\n\n## Sposób 1 - wyprowadzenie ze wzoru w treści zadania\n\nW treści zadania mamy: dla x', y' takich, że NWD(b, r) = b·x' + r·y':\n- x = y'\n- y = x' - (a div b)·y'\n\n**Krok 3:** wywołujemy rekurencyjnie RozszerzonyEuklides z argumentami (b, r) - bo r = a mod b. To zwraca parę liczb takich, że b · (pierwsza) + r · (druga) = NWD(b, r) = NWD(a, b).\n\nWynik rekurencji w treści to (x', y'). W algorytmie używamy zmiennych (x, y), więc oznaczamy:\n- po wywołaniu RozszerzonyEuklides(b, r) zmienna `x` = x' (pierwsza zwrócona) oraz `y` = y' (druga zwrócona).\n\n**Krok 4:** zwracamy parę będącą NOWYM (x, y) dla wywołania (a, b):\n- nowe X = stare y' = `y`\n- nowe Y = stare x' - (a div b) · stare y' = `x - (a div b)·y`\n\nZatem zwracamy: **(y, x - (a div b)·y)**.\n\n## Sposób 2 - weryfikacja na konkretnym przykładzie (a=188, b=12)\n\nUżywając algorytmu:\nRozszerzonyEuklides(188, 12):\nr = 188 mod 12 = 8\n(x, y) ← RozszerzonyEuklides(12, 8)\n// zejście\nreturn (1, -1)\n// teraz x = 1, y = -1\nreturn (-1, 1 - 15*(-1)) = (-1, 16)\n\nSprawdzenie: 188·(-1) + 12·16 = -188 + 192 = 4 = NWD(188, 12). ✓\n\n**Pełny pseudokod (z wypełnionymi pustymi miejscami):**\nRozszerzonyEuklides(a, b):\nKrok 1. Jeśli b = 0, podaj jako wynik funkcji parę (1, 0) i zakończ.\nKrok 2. r ← a mod b\nKrok 3. (x, y) ← RozszerzonyEuklides(b, r)\nKrok 4. Podaj jako wynik parę (y, x - (a div b)·y).\n\n**Python:**\n```python\ndef rozszerzony_euklides(a, b):\nif b == 0:\nreturn (1, 0)\nr = a % b\nx, y = rozszerzony_euklides(b, r)\nreturn (y, x - (a // b) * y)\n\nprint(rozszerzony_euklides(188, 12)) # (-1, 16)\nprint(rozszerzony_euklides(231, 30)) # (3, -23)? sprawdzenie 3*231 + (-23)*30 = 693 - 690 = 3 = NWD\n\n## Reference informatyczny - równanie Bézouta i tożsamość\n\n> Reference - Bezout's Identity:\n> - Dla każdych całkowitych a, b istnieją całkowite x, y takie, że a·x + b·y = NWD(a, b).\n> - Algorytm rozszerzony Euklidesa znajduje JEDNĄ taką parę (x, y). Inne rozwiązania mają postać (x + k·b/d, y - k·a/d), gdzie d = NWD(a,b).\n> - Konstrukcja rekurencyjna: bazowy NWD(a, 0) = a = 1·a + 0·0 → (1, 0). Krok rekurencyjny opiera się na: jeśli NWD(b, r) = b·x' + r·y' to NWD(a,b) = a·y' + b·(x' - (a div b)·y').\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 3.2, max 3 pkt):\n> - **3 pkt** - poprawnie wypełnione kroki 3 ORAZ 4\n> - **2 pkt** - poprawnie wypełniony tylko krok 4\n> - **1 pkt** - poprawnie wypełniony tylko krok 3 ALBO odpowiedź (y', x' - (a div b)·y')\n> - **0 pkt** - niepełna lub błędna albo brak\n\n## Typowe pułapki\n\n- Krok 3: podanie `(b, a mod b)` zamiast `(b, r)` - formalnie OK, ale w kontekście kroku 2 `r = a mod b`, więc lepiej napisać `(b, r)`.\n- Krok 4: pomylenie kolejności (x, y) - pierwsze powinno być stare `y` (nie `x`!).\n- Krok 4: zapomnienie minus przy (a div b)·y.\n- Pomylenie a div b z a mod b - dwie różne wartości!\n- W niektórych źródłach: zwracanie pary (y', x' - (a div b)·y') - wtedy oznaczenia (x, y) ↔ (x', y'). Klucz CKE akceptuje obydwa zapisy.\n\n## Złożoność obliczeniowa\n\n- Czas: O(log min(a, b)) (jak klasyczny Euklides).\n- Pamięć: O(log min(a, b)) (stos rekurencji).","image":"img/informatyka-2015-maj-matura-rozszerzona/zad-3.2.webp","solution_image":null,"topics":null,"page_from":9,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2015 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 3.2. (0-3)
Uzupełnij poniższą rekurencyjną funkcję obliczania pary liczb (x, y) dla danych liczb a, b.
Specyfikacja:
Dane:
liczby całkowite a > 0 i b ≥ 0
Wynik:
para liczb całkowitych (
)
,x y , dla których
( , ) =
⋅

\n\n

NWD a b
a x
b y
RozszerzonyEuklides(a, b):
Krok 1.
Jeśli b = 0, podaj jako wynik funkcji parę (1, 0) i zakończ jej wykonywanie.
Krok 2.
r ← a mod b
Krok 3.
(x, y) ← RozszerzonyEuklides( , )
Krok 4.
Podaj jako wynik parę ( , ).
Miejsce na obliczenia.
Wypełnia
egzaminator
Nr zadania
3.1.
3.2.
Maks. liczba pkt.
2
3
Uzyskana liczba pkt.
MIN_1R
BRUDNOPIS (nie podlega ocenie)

","answer_text_html":"

Zadanie 3.2. (0-3)
III. Rozwiązywanie problemów
i podejmowanie decyzji z wykorzystaniem
komputera, z zastosowaniem podejścia
algorytmicznego.
Zdający opracowuje i przeprowadza wszystkie etapy
prowadzące do otrzymania poprawnego rozwiązania
problemu: od sformułowania specyfikacji problemu
po testowa nie rozwiązania (5.7.).
Zdający stosuje rekurencję w prostych sytuacjach
problemowych (5.9.).
Poprawna odpowiedź
Krok 3: (b, r).
Krok 4: ( y, x - (a div b) • y).
Schemat punktowania
3 p. - za prawidłowo wypełnione pola w krokach 3 i 4 algorytmu.
2 p. - za prawidłowo wypełnione pola w kroku 4 algorytmu.
1 p. - za prawidłowo wypełnione pola w kroku 3 algorytmu albo za odpowiedź (y', x' - (a div b) • y').
0 p. - za odpowiedź niepełną lub błędną albo za brak odpowiedzi.
Część II

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

Poprawna odpowiedź

\n

Krok 3: (x, y) ← RozszerzonyEuklides(b, r)

\n

Krok 4: Podaj jako wynik parę (y, x - (a div b)·y).

\n

Sposób 1 - wyprowadzenie ze wzoru w treści zadania

\n

W treści zadania mamy: dla x', y' takich, że NWD(b, r) = b·x' + r·y':

\n\n

Krok 3: wywołujemy rekurencyjnie RozszerzonyEuklides z argumentami (b, r) - bo r = a mod b. To zwraca parę liczb takich, że b · (pierwsza) + r · (druga) = NWD(b, r) = NWD(a, b).

\n

Wynik rekurencji w treści to (x', y'). W algorytmie używamy zmiennych (x, y), więc oznaczamy:

\n\n

Krok 4: zwracamy parę będącą NOWYM (x, y) dla wywołania (a, b):

\n\n

Zatem zwracamy: (y, x - (a div b)·y).

\n

Sposób 2 - weryfikacja na konkretnym przykładzie (a=188, b=12)

\n

Używając algorytmu:
RozszerzonyEuklides(188, 12):
r = 188 mod 12 = 8
(x, y) ← RozszerzonyEuklides(12, 8)
// zejście
return (1, -1)
// teraz x = 1, y = -1
return (-1, 1 - 15*(-1)) = (-1, 16)

\n

Sprawdzenie: 188·(-1) + 12·16 = -188 + 192 = 4 = NWD(188, 12). ✓

\n

Pełny pseudokod (z wypełnionymi pustymi miejscami):
RozszerzonyEuklides(a, b):
Krok 1. Jeśli b = 0, podaj jako wynik funkcji parę (1, 0) i zakończ.
Krok 2. r ← a mod b
Krok 3. (x, y) ← RozszerzonyEuklides(b, r)
Krok 4. Podaj jako wynik parę (y, x - (a div b)·y).

\n

Python:
```python
def rozszerzony_euklides(a, b):
if b == 0:
return (1, 0)
r = a % b
x, y = rozszerzony_euklides(b, r)
return (y, x - (a // b) * y)

\n

print(rozszerzony_euklides(188, 12)) # (-1, 16)
print(rozszerzony_euklides(231, 30)) # (3, -23)? sprawdzenie 3231 + (-23)30 = 693 - 690 = 3 = NWD

\n

Reference informatyczny - równanie Bézouta i tożsamość

\n
Reference - Bezout's Identity:
- Dla każdych całkowitych a, b istnieją całkowite x, y takie, że a·x + b·y = NWD(a, b).
- Algorytm rozszerzony Euklidesa znajduje JEDNĄ taką parę (x, y). Inne rozwiązania mają postać (x + k·b/d, y - k·a/d), gdzie d = NWD(a,b).
- Konstrukcja rekurencyjna: bazowy NWD(a, 0) = a = 1·a + 0·0 → (1, 0). Krok rekurencyjny opiera się na: jeśli NWD(b, r) = b·x' + r·y' to NWD(a,b) = a·y' + b·(x' - (a div b)·y').
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 3.2, max 3 pkt):
- 3 pkt - poprawnie wypełnione kroki 3 ORAZ 4
- 2 pkt - poprawnie wypełniony tylko krok 4
- 1 pkt - poprawnie wypełniony tylko krok 3 ALBO odpowiedź (y', x' - (a div b)·y')
- 0 pkt - niepełna lub błędna albo brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}