Zadanie 2
Matura z informatyki, maj 2024, poziom rozszerzony
Wymaganie: P.I.1) planuje kolejne kroki rozwiązywania problemu, z uwzględnieniem podstawowych etapów myślenia komputacyjnego […]. P.I.2) stosuje przy rozwiązywaniu problemów z różnych dziedzin algorytmy poznane w szkole podstawowej oraz algorytmy: a) na liczbach: […] zamiany reprezentacji liczb między pozycyjnymi systemami liczbowymi […]. P.I.4) […] analizuje algorytmy na podstawie ich gotowych implementacji. P.II.1) projektuje i programuje rozwiązania problemów z różnych dziedzin […]. I.2) do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych. I.5) przedstawia sposoby reprezentowania w komputerze znaków, liczb […] (2.2).
Treść zadania
Zadanie 2. Cyfry
Przeanalizuj poniższy algorytm, który dla danej nieujemnej liczby całkowitej n oblicza liczbę całkowitą c.
b ← 1
c ← 0
dopóki n > 0 wykonuj
a ← n mod 10
n ← n div 10
jeżeli (a mod 2 = 0)
c ← c + b * (a div 2)
w przeciwnym razie
c ← c + b
b ← b * 10
Uwaga: x mod y, x div y oznaczają — odpowiednio — resztę i iloraz z dzielenia całkowitego x przez y.
Zadanie 2.1. (0–2) Uzupełnij tabelę – dla każdej z podanych liczb wpisz wartość zmiennej c po wykonaniu algorytmu oraz liczbę wykonań instrukcji c ← c + b.
| n | wartość c | liczba wykonań c ← c + b |
|---|---|---|
| 33658 | 11314 | 3 |
| 542102 | ||
| 87654321012345678 |
Zadanie 2.2. (0–1) Podaj wartość c po wykonaniu algorytmu dla osiemnastocyfrowej liczby całkowitej n, w której pierwszych sześć cyfr to 3, następnych sześć cyfr to 6, a pozostałych sześć cyfr to 9.
c = …
Źródło: arkusz CKE MINP-R0-100-2405. Otwórz oryginalny PDF
Rozwiązanie
2.1. Odpowiedź z zasad oceniania CKE:
| n | wartość c | liczba wykonań c ← c + b |
|---|---|---|
| 33658 | 11314 | 3 |
| 542102 | 121101 | 2 |
| 87654321012345678 | 41312111011121314 | 8 |
Instrukcja c ← c + b wykonuje się raz dla każdej nieparzystej cyfry n; cyfra parzysta a zostaje zastąpiona przez a div 2, a nieparzysta przez 1.
2.2. Liczba: n = 333333 666666 999999 (18 cyfr; od lewej do prawej).
Algorytm przetwarza cyfry od najmłodszej (mod 10), pomnożone przez kolejne potęgi 10 (zmienna b).
- Cyfra parzysta a: dokłada do c wartość b * (a/2)
- Cyfra nieparzysta a: dokłada do c wartość b (czyli traktuje cyfrę nieparzystą tak, jakby była "1" na danej pozycji)
Analiza grupami sześciu cyfr (od najmłodszych):
Pozycje 1–6 (cyfra 9, nieparzysta): dla każdej z 6 cyfr c += b. Suma wkładów: 1 + 10 + 100 + 1000 + 10000 + 100000 = 111 111.
Pozycje 7–12 (cyfra 6, parzysta, a div 2 = 3): dla każdej c += 3 * b. Suma: 3 * (10⁶ + 10⁷ + 10⁸ + 10⁹ + 10¹⁰ + 10¹¹) = 3 * 111 111 * 10⁶ = 333 333 000 000.
Pozycje 13–18 (cyfra 3, nieparzysta): dla każdej c += b. Suma: 10¹² + 10¹³ + … + 10¹⁷ = 111 111 * 10¹² = 111 111 000 000 000 000.
Wynik:
c = 111 111 + 333 333 000 000 + 111 111 000 000 000 000
c = 111 111 333 333 111 111
Uwaga: (1) algorytm przetwarza cyfry od końca (mod 10 zwraca cyfrę jedności), ale każda cyfra trafia do c na tę samą pozycję, na której stała w n — wynik nie jest odwrócony; (2) dla cyfry nieparzystej dodajemy samo b, a nie b · a; (3) w 2.1 liczba wykonań c ← c + b to liczba nieparzystych cyfr n.
Strona arkusza CKE z treścią zadania
Rozwiązanie
Symulacja w Pythonie (weryfikacja):
n = int("333333" + "666666" + "999999") # 333333666666999999
b, c = 1, 0
while n > 0:
a = n % 10
n = n // 10
if a % 2 == 0:
c += b * (a // 2)
else:
c += b
b *= 10
print(c) # 111111333333111111Wynik: c = 111 111 333 333 111 111
Algorytm tworzy nową liczbę dziesiętną, w której:
- każda cyfra parzysta a w oryginale → cyfra a/2 w wyniku,
- każda cyfra nieparzysta w oryginale → cyfra 1 w wyniku.
Sprawdzenie reguły: 9 → 1, 6 → 3, 3 → 1 — pasuje do wyniku 111111333333111111.
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 „analiza algorytmu, cyfry parzyste, operacje mod i div, zapis dziesiętny liczby” zrobisz samodzielnie.
Otwórz matury-online.pl