{"id":"informatyka-2015-maj-matura-rozszerzona/zad/3.1","paper_id":"informatyka-2015-maj-matura-rozszerzona","number":"3.1","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2015,"month":"maj","level":"rozszerzona","text":"Zadanie 3.1. (0-2)\nUzupełnij poniższą tabelę ilustrującą wykonanie funkcji RozszerzonyEuklides(a, b) dla\ndanych a = 188, b = 12.\ni - nr wywołania\nWartość a w i-tym\nwywołaniu\nWartość b w i-tym\nwywołaniu\nWynik x\nWynik y\n1\n188\n12\n2\n3\n4\n0\n1\n0\nMiejsce na obliczenia.\nMIN_1R","answer":null,"answer_text":"Zadanie 3.1. (0-2)\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji z wykorzystaniem\nkomputera, z zastosowaniem podejścia\nalgorytmicznego.\nZdający stosuje podejście algorytmiczne\ndo rozwiązywania problemu (5.2.).\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.).\nPoprawna odpowiedź\nNumer\nwywołania\nWartość a\nWartość b\nWynik x\nWynik y\n1\n188\n12\n-1\n16\n2\n12\n8\n1\n-1\n3\n8\n4\n0\n1\n4\n4\n0\n1\n0\nSchemat punktowania\n2 p. - za prawidłowe uzupełnienie kolumn z wartościami a i b oraz za prawidłowe uzupełnienie kolumn\nWynik x i Wynik y.\n1 p. - za prawidłowe uzupełnienie kolumn z wartościami a i b albo za prawidłowe uzupełnienie kolumn\nWynik x i Wynik y.\n0 p. - za odpowiedź niepełną lub błędną albo brak odpowiedzi.","solution":"## Poprawna odpowiedź\n\n| i | a | b | x | y |\n| 1 | 188 | 12 | **-1** | **16** |\n| 2 | **12** | **8** | **1** | **-1** |\n| 3 | **8** | **4** | **0** | **1** |\n| 4 | **4** | **0** | **1** | **0** |\n\nNWD(188, 12) = 4 = (-1)·188 + 16·12.\n\n## Sposób 1 - rozwijanie rekurencji od dołu (pre-order) i z powrotem\n\n**Krok 1: zejście rekurencji (oblicz a, b dla każdego wywołania)**\n\ni=1: a=188, b=12, r = 188 mod 12 = 8 (bo 188 = 15·12 + 8). Wywołaj RozszerzonyEuklides(12, 8).\ni=2: a=12, b=8, r = 12 mod 8 = 4. Wywołaj RozszerzonyEuklides(8, 4).\ni=3: a=8, b=4, r = 8 mod 4 = 0. Wywołaj RozszerzonyEuklides(4, 0).\ni=4: a=4, b=0 - przypadek bazowy, zwracamy (x, y) = (1, 0).\n\n**Krok 2: powrót z rekurencji (oblicz x, y)**\n\ni=4: (x, y) = (1, 0). NWD(4, 0) = 4 = 1·4 + 0·0. ✓\n\ni=3: a=8, b=4, dzielnik (a div b) = 8 div 4 = 2. Z rekurencji (x', y') = (1, 0).\n- x = y' = **0**\n- y = x' - (a div b)·y' = 1 - 2·0 = **1**\n- Sprawdzenie: NWD(8, 4) = 4 = 0·8 + 1·4 ✓\n\ni=2: a=12, b=8, (a div b) = 12 div 8 = 1. (x', y') = (0, 1).\n- x = y' = **1**\n- y = x' - 1·y' = 0 - 1·1 = **-1**\n- Sprawdzenie: NWD(12, 8) = 4 = 1·12 + (-1)·8 = 12 - 8 = 4 ✓\n\ni=1: a=188, b=12, (a div b) = 188 div 12 = 15. (x', y') = (1, -1).\n- x = y' = **-1**\n- y = x' - 15·y' = 1 - 15·(-1) = 1 + 15 = **16**\n- Sprawdzenie: NWD(188, 12) = 4 = (-1)·188 + 16·12 = -188 + 192 = **4** ✓\n\n## Sposób 2 - implementacja Python rekurencyjna\n\n```python\ndef rozszerzony_euklides(a, b):\nif b == 0:\nreturn (1, 0)\nr = a % b\nx_prim, y_prim = rozszerzony_euklides(b, r)\nx = y_prim\ny = x_prim - (a // b) * y_prim\nreturn (x, y)\n\nx, y = rozszerzony_euklides(188, 12)\nprint(f'x = {x}, y = {y}') # x = -1, y = 16\nprint(f'sprawdzenie: {x}*188 + {y}*12 = {x*188 + y*12}') # 4\n\nIteracje (trace):\nWywołanie(188, 12): r = 8\nWywołanie(12, 8): r = 4\nWywołanie(8, 4): r = 0\nWywołanie(4, 0): return (1, 0)\nPowrót do (8,4): x = 0, y = 1 - 2*0 = 1 → return (0, 1)\nPowrót do (12,8): x = 1, y = 0 - 1*1 = -1 → return (1, -1)\nPowrót do (188,12): x = -1, y = 1 - 15*(-1) = 16 → return (-1, 16)\n\n## Reference informatyczny - Rozszerzony algorytm Euklidesa\n\n> Reference - Extended Euclidean Algorithm:\n> - Klasyczny Euklides: NWD(a, b) = NWD(b, a mod b), bazowy NWD(a, 0) = a.\n> - **Rozszerzony Euklides** dodaje obliczenie x, y takich że a·x + b·y = NWD(a, b) (tożsamość Bézouta).\n> - Algorytm rekurencyjny: pre-order zejście, post-order powrót z formułami:\n> - x = y'\n> - y = x' - (a div b)·y'\n> - Zastosowania: odwracanie modularne (RSA, kryptografia), rozwiązywanie równań Diofantosa.\n> - Złożoność: O(log min(a, b)) - tyle samo co klasyczny Euklides.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 3.1, max 2 pkt):\n> - **2 pkt** - poprawne uzupełnienie kolumn a i b ORAZ kolumn x i y\n> - **1 pkt** - poprawne tylko a i b ALBO tylko x i y\n> - **0 pkt** - niepełna lub błędna albo brak\n\n## Typowe pułapki\n\n- Pomylenie a div b (dzielenie całkowite) z a / b (zmiennoprzecinkowe). 188 div 12 = 15, nie 15.666.\n- Niepoprawne stosowanie formuły y = x' - (a div b)·y' - łatwo zapomnieć minus.\n- Pomylenie x i x' (apostrof oznacza wartość z rekurencji niżej, bez apostrofu - z aktualnego poziomu).\n- Brak sprawdzenia: a·x + b·y musi się równać NWD.\n- Pomyłka w `a mod b` dla 188, 12 - to 8 (188 = 15·12 + 8).\n\n## Złożoność obliczeniowa\n\n- Liczba wywołań rekurencyjnych: O(log min(a, b)) (twierdzenie Lamé).\n- Pamięć: O(log min(a, b)) (stos rekurencji).\n- Czas: **O(log min(a, b))**.","image":"img/informatyka-2015-maj-matura-rozszerzona/zad-3.1.webp","solution_image":null,"topics":null,"page_from":8,"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.1. (0-2)
Uzupełnij poniższą tabelę ilustrującą wykonanie funkcji RozszerzonyEuklides(a, b) dla
danych a = 188, b = 12.
i - nr wywołania
Wartość a w i-tym
wywołaniu
Wartość b w i-tym
wywołaniu
Wynik x
Wynik y
1
188
12
2
3
4
0
1
0
Miejsce na obliczenia.
MIN_1R

","answer_text_html":"

Zadanie 3.1. (0-2)
III. Rozwiązywanie problemów
i podejmowanie decyzji z wykorzystaniem
komputera, z zastosowaniem podejścia
algorytmicznego.
Zdający stosuje podejście algorytmiczne
do rozwiązywania problemu (5.2.).
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.).
Poprawna odpowiedź
Numer
wywołania
Wartość a
Wartość b
Wynik x
Wynik y
1
188
12
-1
16
2
12
8
1
-1
3
8
4
0
1
4
4
0
1
0
Schemat punktowania
2 p. - za prawidłowe uzupełnienie kolumn z wartościami a i b oraz za prawidłowe uzupełnienie kolumn
Wynik x i Wynik y.
1 p. - za prawidłowe uzupełnienie kolumn z wartościami a i b albo za prawidłowe uzupełnienie kolumn
Wynik x i Wynik y.
0 p. - za odpowiedź niepełną lub błędną albo brak odpowiedzi.

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

Poprawna odpowiedź

\n

| i | a | b | x | y |
| 1 | 188 | 12 | -1 | 16 |
| 2 | 12 | 8 | 1 | -1 |
| 3 | 8 | 4 | 0 | 1 |
| 4 | 4 | 0 | 1 | 0 |

\n

NWD(188, 12) = 4 = (-1)·188 + 16·12.

\n

Sposób 1 - rozwijanie rekurencji od dołu (pre-order) i z powrotem

\n

Krok 1: zejście rekurencji (oblicz a, b dla każdego wywołania)

\n

i=1: a=188, b=12, r = 188 mod 12 = 8 (bo 188 = 15·12 + 8). Wywołaj RozszerzonyEuklides(12, 8).
i=2: a=12, b=8, r = 12 mod 8 = 4. Wywołaj RozszerzonyEuklides(8, 4).
i=3: a=8, b=4, r = 8 mod 4 = 0. Wywołaj RozszerzonyEuklides(4, 0).
i=4: a=4, b=0 - przypadek bazowy, zwracamy (x, y) = (1, 0).

\n

Krok 2: powrót z rekurencji (oblicz x, y)

\n

i=4: (x, y) = (1, 0). NWD(4, 0) = 4 = 1·4 + 0·0. ✓

\n

i=3: a=8, b=4, dzielnik (a div b) = 8 div 4 = 2. Z rekurencji (x', y') = (1, 0).

\n\n

i=2: a=12, b=8, (a div b) = 12 div 8 = 1. (x', y') = (0, 1).

\n\n

i=1: a=188, b=12, (a div b) = 188 div 12 = 15. (x', y') = (1, -1).

\n\n

Sposób 2 - implementacja Python rekurencyjna

\n

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

\n

x, y = rozszerzony_euklides(188, 12)
print(f'x = {x}, y = {y}') # x = -1, y = 16
print(f'sprawdzenie: {x}188 + {y}12 = {x188 + y12}') # 4

\n

Iteracje (trace):
Wywołanie(188, 12): r = 8
Wywołanie(12, 8): r = 4
Wywołanie(8, 4): r = 0
Wywołanie(4, 0): return (1, 0)
Powrót do (8,4): x = 0, y = 1 - 2*0 = 1 → return (0, 1)
Powrót do (12,8): x = 1, y = 0 - 1*1 = -1 → return (1, -1)
Powrót do (188,12): x = -1, y = 1 - 15*(-1) = 16 → return (-1, 16)

\n

Reference informatyczny - Rozszerzony algorytm Euklidesa

\n
Reference - Extended Euclidean Algorithm:
- Klasyczny Euklides: NWD(a, b) = NWD(b, a mod b), bazowy NWD(a, 0) = a.
- Rozszerzony Euklides dodaje obliczenie x, y takich że a·x + b·y = NWD(a, b) (tożsamość Bézouta).
- Algorytm rekurencyjny: pre-order zejście, post-order powrót z formułami:
- x = y'
- y = x' - (a div b)·y'
- Zastosowania: odwracanie modularne (RSA, kryptografia), rozwiązywanie równań Diofantosa.
- Złożoność: O(log min(a, b)) - tyle samo co klasyczny Euklides.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 3.1, max 2 pkt):
- 2 pkt - poprawne uzupełnienie kolumn a i b ORAZ kolumn x i y
- 1 pkt - poprawne tylko a i b ALBO tylko x i y
- 0 pkt - niepełna lub błędna albo brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}