MINP-R0-100-2505 • Otwarte rozszerzone • 9 pkt • Trudność: ★★★★☆

Zadanie 1

Matura z informatyki, maj 2025, poziom rozszerzony

Wymaganie:

II.1, II.2 – tworzenie i analiza algorytmów; III.2 – pisanie programów w wybranym języku, w tym rekurencyjnych i iteracyjnych wersji algorytmów.

Treść zadania

Zadanie 1. Funkcja rekurencyjna

Dana jest rekurencyjna funkcja przestaw, której parametrem jest nieujemna liczba całkowita:

przestaw(n):
    r ← n mod 100
    a ← r div 10
    b ← r mod 10
    n ← n div 100
    jeżeli n > 0
        w ← a + 10 * b + 100 * przestaw(n)
    w przeciwnym razie
        jeżeli a > 0
            w ← a + 10 * b
        w przeciwnym razie
            w ← b
    wynikiem jest w

Uwaga: Operator mod oznacza resztę z dzielenia, natomiast div – część całkowitą z dzielenia.

Zadanie 1.1. (0–3)

Uzupełnij tabelę – wpisz w drugiej kolumnie wynik funkcji przestaw(n) dla podanych wartości argumentu n oraz wpisz w trzeciej kolumnie liczbę wywołań funkcji przestaw łącznie z pierwszym wywołaniem z parametrem n.

n	Wynik działania funkcji przestaw	Liczba wywołań funkcji przestaw
316498	134689	3
43657688
154005710
998877665544321

Zadanie 1.2. (0–2)

Oceń prawdziwość podanych zdań. Zaznacz P, jeśli zdanie jest prawdziwe, albo F – jeśli jest fałszywe.

Niech n będzie liczbą k-cyfrową, gdzie k > 0. Liczba wywołań funkcji przestaw w zależności od k jest równa:

Lp.	Wyrażenie	P/F
1.	$\frac{k}{2}$	P / F
2.	$(k + 1) div 2$ (gdzie div oznacza dzielenie całkowite)	P / F
3.	$\frac{k}{2}$ gdy k parzyste; $\frac{k + 1}{2}$ gdy k nieparzyste	P / F
4.	$\frac{k + 1}{2}$	P / F

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łkowitej n da taką samą wartość jak przestaw(n).

Uwaga: Twój algorytm może używać wyłącznie zmiennych przechowujących liczby całkowite oraz może operować wyłącznie na liczbach całkowitych. Możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, resztę z dzielenia) oraz porównywanie liczb, instrukcje sterujące, przypisania do zmiennych lub samodzielnie napisane funkcje, wykorzystujące wyżej wymienione operacje. Zabronione jest używanie funkcji wbudowanych oraz operatorów innych niż wymienione, w tym – funkcji przestaw.

Specyfikacja:

Dane: n – nieujemna liczba całkowita
Wynik: w – nieujemna liczba całkowita, wynik działania taki sam jak po wykonaniu przestaw(n)

Źródło: arkusz CKE MINP-R0-100-2505. Otwórz oryginalny PDF

Rozwiązanie

1.1. Funkcja zamienia każdą parę cyfr (od najmłodszej strony) – cyfra dziesiątek i jedności są zamieniane miejscami, a wynik jest sklejany rekurencyjnie.

n	Wynik	Liczba wywołań
316498	134689	3
43657688	34567868	4
154005710	451050071	5
998877665544321	899788565544231 → należy rozpisać: krok po kroku zamieniamy pary "21→12", "43→34", "65→56", "77→77, …" → wynik: 899778856644321 → poprawnie: 998877665544321 → 899778856644321 (8 wywołań)	8

Wyjaśnienie liczby wywołań: liczba wywołań = ⌈k/2⌉, gdzie k to liczba cyfr (każde wywołanie konsumuje 2 cyfry, ostatnie może konsumować 1).

1.2.

$\frac{k}{2}$ — F (nie działa dla nieparzystych k)
$(k + 1) div 2$ — P (równoważne ⌈k/2⌉)
zdefiniowane przypadkami — P
$\frac{k + 1}{2}$ — F (nie działa dla parzystych k w arytmetyce całkowitej, daje wynik niecałkowity)

1.3. Wersja iteracyjna (Python):

def przestaw2(n):
    w = 0
    mnoznik = 1
    while n >= 100:
        r = n % 100
        a = r // 10
        b = r % 10
        w = w + mnoznik * (a + 10 * b)
        mnoznik = mnoznik * 100
        n = n // 100
    # ostatnie 1 lub 2 cyfry
    if n >= 10:
        a = n // 10
        b = n % 10
        w = w + mnoznik * (a + 10 * b)
    else:
        w = w + mnoznik * n
    return w

Algorytm iteruje od najmłodszych par cyfr, zamienia kolejność cyfr w parze i dokleja do wyniku, mnożąc przez odpowiednią potęgę 100.

Typowy błąd / pułapka

W 1.1 typowy błąd to nie zauważenie, że funkcja nie odwraca całej liczby, tylko zamienia cyfry w każdej parze (rozważanej od końca). W 1.2 – pomylenie dzielenia całkowitego z rzeczywistym. W 1.3 – próba napisania pętli, która konsumuje po 1 cyfrze zamiast po 2 (algorytm rekurencyjny przetwarza 2 cyfry naraz).

Strona arkusza CKE z treścią zadania

Zadanie 1 - informatyka 2025 PR — Strona arkusza CKE 2025 PR informatyka - zadanie 1 (funkcja rekurencyjna przestaw). Na podstawie: CKE 2025 Oryginalny PDF CKE, str. 4

Rozwiązanie krok po kroku

1.1 – analiza funkcji przestaw

Funkcja w każdej rekurencyjnej iteracji bierze dwie najmłodsze cyfry liczby (r = n mod 100), rozkłada je na cyfrę dziesiątek (a) i jedności (b), zamienia je miejscami (a + 10*b), a następnie skleja z wynikiem rekurencyjnego wywołania dla pozostałej części liczby (n div 100). Liczba wywołań to ⌈k/2⌉, gdzie k to liczba cyfr.

1.2 – wzór na liczbę wywołań

Poprawny wzór to ⌈k/2⌉, który zapisać można jako (k+1) div 2 (działa zarówno dla parzystych jak i nieparzystych k).

1.3 – wersja iteracyjna

Pętla while przetwarza liczbę “od końca” parami cyfr, używając mnożnika potęg 100 do umieszczenia wyniku na właściwych pozycjach. Obsługa końca: gdy zostaje 1 lub 2 cyfry, dokładamy je analogicznie jak w wersji rekurencyjnej (a > 0 lub nie).

Rozumiesz, jak to rozwiązać?

Przećwicz podobne typy zadań w aplikacji

matury-online.pl ma tysiące zadań pogrupowanych po dziedzinach. Sprawdź, czy temat „funkcja rekurencyjna, pseudokod, analiza algorytmu, przekształcanie zapisu cyfr, programowanie nierekurencyjne" zrobisz samodzielnie.

Otwórz matury-online.pl