# Informatyka — zadanie 3.1

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2015-05/zad/3.1
> 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: 2
- działy: Programowanie i algorytmika, algorytmy

## Treść

Zadanie 3. Rozszerzony algorytm Euklidesa
Algorytm Euklidesa to algorytm wyznaczania największego wspólnego dzielnika (NWD)
dwóch liczb całkowitych a > 0 i b ≥ 0.
Specyfikacja:
Dane:
liczby całkowite, a > 0 i b ≥ 0,
Wynik:
największy wspólny dzielnik liczb a i b.
Algorytm NWD:
Krok 1.
Jeżeli b = 0, to NWD jest równy a i zakończ wykonywanie algorytmu.
Krok 2.
Oblicz r jako resztę z dzielenia a przez b.
Krok 3.
Zastąp a przez b, natomiast b przez r.
Krok 4.
Przejdź do kroku 1.
W niektórych zastosowaniach informatycznych potrzebujemy wyrazić największy wspólny
dzielnik dwóch liczb całkowitych a, b w następujący sposób:
ܦሺܽ,ܾሻ=ܽ
∙ݔ+ܾ
∙ݕ,
gdzie x i y są liczbami całkowitymi.
Do wyznaczenia wartości x i y wykorzystywana jest następująca zależność:
dla ݎ=ܽ
݉
݋݀ ܾ różnego od zera oraz liczb całkowitych x’, y’ takich, że
ܦሺܾ, ݎሻ=ܾ
∙ݔᇱ+ ݎ∙ݕ′,
parę liczb (x, y) można wyrazić wzorami:
ݔ= ݕᇱ
ݕ= ݔᇱ-ሺܽ ݀݅
ݒ ܾሻ∙ݕ′
Uwaga:
a mod b, a div b oznaczają odpowiednio resztę i iloraz z dzielenia całkowitego a przez b.
Wypełnia
egzaminator
Nr zadania
2.3.
2.4.
2.5.
Maks. liczba pkt.
1
1
1
Uzyskana liczba pkt.
MIN_1R
Opisana zależność pozwala na rekurencyjne obliczenie pary liczb (x, y).
Niech RozszerzonyEuklides(a, b) będzie rekurencyjną funkcją realizującą ten pomysł.
Działanie funkcji zilustrujmy przykładem.
Przykład dla a = 231, b = 30
i - nr
wywołania
NWD (a, b)
Zagnieżdżanie
rekurencji
←
Powrót
z rekurencji
→
Wynik
x
Wynik
y
Wartość a
w i-tym
wywołaniu
Wartość b
w i-tym
wywołaniu
1
231
30
↓
↑
3
-23
2
30
21
↓
↑
-2
3
3
21
9
↓
↑
1
-2
4
9
3
↓
↑
0
1
5
3
0
↓
↑
1
0
Zatem NWD(231, 30) = 3 · 231 + (-23) · 30.

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

## Poprawna odpowiedź

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

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

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

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

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

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

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

i=3: a=8, b=4, dzielnik (a div b) = 8 div 4 = 2. Z rekurencji (x', y') = (1, 0).
- x = y' = **0**
- y = x' - (a div b)·y' = 1 - 2·0 = **1**
- Sprawdzenie: NWD(8, 4) = 4 = 0·8 + 1·4 ✓

i=2: a=12, b=8, (a div b) = 12 div 8 = 1. (x', y') = (0, 1).
- x = y' = **1**
- y = x' - 1·y' = 0 - 1·1 = **-1**
- Sprawdzenie: NWD(12, 8) = 4 = 1·12 + (-1)·8 = 12 - 8 = 4 ✓

i=1: a=188, b=12, (a div b) = 188 div 12 = 15. (x', y') = (1, -1).
- x = y' = **-1**
- y = x' - 15·y' = 1 - 15·(-1) = 1 + 15 = **16**
- Sprawdzenie: NWD(188, 12) = 4 = (-1)·188 + 16·12 = -188 + 192 = **4** ✓

## Sposób 2 - implementacja Python rekurencyjna

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

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

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)

## Reference informatyczny - Rozszerzony algorytm Euklidesa

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

## Schemat oceniania CKE

> 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

## Typowe pułapki

- Pomylenie a div b (dzielenie całkowite) z a / b (zmiennoprzecinkowe). 188 div 12 = 15, nie 15.666.
- Niepoprawne stosowanie formuły y = x' - (a div b)·y' - łatwo zapomnieć minus.
- Pomylenie x i x' (apostrof oznacza wartość z rekurencji niżej, bez apostrofu - z aktualnego poziomu).
- Brak sprawdzenia: a·x + b·y musi się równać NWD.
- Pomyłka w `a mod b` dla 188, 12 - to 8 (188 = 15·12 + 8).

## Złożoność obliczeniowa

- Liczba wywołań rekurencyjnych: O(log min(a, b)) (twierdzenie Lamé).
- Pamięć: O(log min(a, b)) (stos rekurencji).
- Czas: **O(log min(a, b))**.

## Linki

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

## Podobne zadania

- [Zadanie 3](https://matura.lol/question/informatyka-2007-maj-matura-rozszerzona/zad/3) — Zadanie 3. (11 pkt) W tabeli podany jest algorytm, który pozwala obliczyć wartość pewnej sumy dla danej dodatniej liczby całkowitej n. 3.1. Podaj, jaką wartość 
- [Zadanie 8](https://matura.lol/question/informatyka-2026-maj-matura-rozszerzona/zad/8) — Zadanie 8. Sieć sklepów W trzech plikach tekstowych o nazwach klienci.txt, transakcje.txt, opis_transakcji.txt zapisano dane o sprzedaży towarów w pewnej sieci 
- [Zadanie 6.3](https://matura.lol/question/informatyka-2016-maj-matura-rozszerzona-2/zad/6.3) — Zadanie 6.3. (0-5) W pliku dane_6_3.txt zapisano 3 000 par słów, po jednej parze w wierszu, oddzielonych pojedynczym znakiem odstępu. Drugie słowo w każdej parz
- [Zadanie 3.3](https://matura.lol/question/informatyka-2022-grudzien-probna-rozszerzona/zad/3.3) — Zadanie 3.3. (0-4) Hipoteza Goldbacha głosi, że każda liczba parzysta większa od 2 jest sumą dwóch liczb pierwszych. Nie wiemy, czy ta hipoteza jest prawdziwa d

_Ostatnia aktualizacja danych: 2026-10-03_