# Informatyka — zadanie 3.2

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2015-05/zad/3.2
> Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej.

- arkusz: Informatyka · Matura · maj 2015 (rozszerzona)
- rok: 2015
- poziom: rozszerzona
- typ: open
- punkty: 3
- działy: Programowanie i algorytmika, algorytmy

## Treść

Kontekst - patrz zadanie 3.1.

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 (x, y), dla której NWD(a, b) = a·x + b·y.

Uzupełnij brakujące argumenty w kroku 3 i wynik w kroku 4 algorytmu RozszerzonyEuklides.

## Rozwiązanie — maturazai.pl (AI)

## Poprawna odpowiedź

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

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

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

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

**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).

Wynik rekurencji w treści to (x', y'). W algorytmie używamy zmiennych (x, y), więc oznaczamy:
- po wywołaniu RozszerzonyEuklides(b, r) zmienna `x` = x' (pierwsza zwrócona) oraz `y` = y' (druga zwrócona).

**Krok 4:** zwracamy parę będącą NOWYM (x, y) dla wywołania (a, b):
- nowe X = stare y' = `y`
- nowe Y = stare x' - (a div b) · stare y' = `x - (a div b)·y`

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

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

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)

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

**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).

**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)

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

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

> 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').

## Schemat oceniania CKE

> 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

## Typowe pułapki

- 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)`.
- Krok 4: pomylenie kolejności (x, y) - pierwsze powinno być stare `y` (nie `x`!).
- Krok 4: zapomnienie minus przy (a div b)·y.
- Pomylenie a div b z a mod b - dwie różne wartości!
- 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.

## Złożoność obliczeniowa

- Czas: O(log min(a, b)) (jak klasyczny Euklides).
- Pamięć: O(log min(a, b)) (stos rekurencji).

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2015-05/zad/3.2)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2015-05%2Fzad%2F3.2)

## Podobne zadania

- [Zadanie 3.3](https://matura.lol/question/informatyka-2026-maj-matura-rozszerzona/zad/3.3) — Zadanie 3.3. (0-4) Prefiksosufiksem pary słów s1, s2 nazywamy słowo, które jest początkiem s1 (czyli s1 zaczyna się tym słowem) oraz końcem s2 (czyli s2 kończy 
- [Zadanie 1.3](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/1.3) — Zadanie 1.3. (0-4) W postaci pseudokodu lub w wybranym języku programowania napisz nierekurencyjną funkcję przestaw2, która dla danej nieujemnej liczby całkowit
- [Zadanie 2.2](https://matura.lol/question/informatyka-2025-maj-matura-stara-rozszerzona/zad/2.2) — Zadanie 2.2. (0-4) W postaci pseudokodu lub w wybranym języku programowania napisz algorytm, który dla liczby bazowej n obliczy liczbę falistą f o tej samej baz
- [Zadanie 1.2](https://matura.lol/question/informatyka-2022-maj-matura-rozszerzona/zad/1.2) — Zadanie 1.2. (0-4) Zapisz w pseudojęzyku lub wybranym języku programowania algorytm, który dla danego ciągu n dodatnich liczb całkowitych zapisanego w tablicy A

_Ostatnia aktualizacja danych: 2026-10-03_