MINP-R0-100-2305 • Otwarte rozszerzone • 11 pkt • Trudność: ★★★★☆

Zadanie 2

Matura z informatyki, maj 2023, poziom rozszerzony

Wymaganie:

I.2) do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych. I.3) objaśnia dobrany algorytm, uzasadnia poprawność rozwiązania na wybranych przykładach danych i ocenia jego efektywność (2.1). I.5) przedstawia sposoby reprezentowania w komputerze znaków, liczb […]. I+II.1) zapisuje za pomocą listy kroków, schematu blokowego lub pseudokodu i implementuje w wybranym języku programowania algorytmy poznane na wcześniejszych etapach […] (2.1). II.2) stosuje zasady programowania strukturalnego i obiektowego w rozwiązywaniu problemów. II.3) sprawnie posługuje się zintegrowanym środowiskiem programistycznym przy pisaniu, uruchamianiu i testowaniu programów. P.I.2) […] a) na liczbach: […] zamiany reprezentacji liczb między pozycyjnymi systemami liczbowymi […]. P.II.1) projektuje i programuje rozwiązania problemów z różnych dziedzin […].

Treść zadania

Zadanie 2. Liczby binarne

W tym zadaniu rozważamy binarny zapis liczb całkowitych dodatnich. Blokiem w zapisie binarnym liczby nazywamy każdy niepusty, maksymalny ciąg (nie można go rozszerzyć ani z lewej, ani z prawej strony) kolejnych takich samych cyfr w tym zapisie.

Przykład: liczba binarna 111110000110111 składa się z pięciu bloków — trzech bloków złożonych z jedynek (11111, 11 i 111) i dwóch bloków złożonych z zer (0000 i 0). Liczba binarna 1111111111111111 składa się z jednego bloku złożonego z jedynek.

Zadanie 2.1. (0–3) Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danej dodatniej całkowitej liczby n obliczy liczbę bloków w jej zapisie binarnym. Przykład: dla 67 (1000011₂) wynikiem jest 3, dla 245 (11110101₂) wynikiem jest 5.

Uwaga: wolno korzystać tylko z instrukcji sterujących, operatorów arytmetycznych (dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego i reszty z dzielenia), operatorów logicznych, porównań, instrukcji przypisania lub samodzielnie napisanych funkcji. Zabronione jest używanie funkcji wbudowanych, w tym zwłaszcza funkcji zamiany między systemami pozycyjnymi i konwersji między typami danych.

Specyfikacja:

Dane: n – dodatnia liczba całkowita
Wynik: b – liczba bloków w zapisie binarnym liczby n

Informacja do zadań 2.2. i 2.3. W pliku bin.txt znajduje się 100 wierszy. Każdy wiersz zawiera zapis binarny dodatniej liczby całkowitej składający się z co najwyżej dwudziestu cyfr (0 lub 1).

Zadanie 2.2. (0–2) Podaj, ile liczb w pliku bin.txt składa się z co najwyżej dwóch bloków (zgodnie z definicją bloku podaną wcześniej). Dla danych z pliku bin_przyklad.txt poprawna odpowiedź to 3.

Zadanie 2.3. (0–2) Wypisz największą z liczb zapisanych w pliku bin.txt. Dla danych z pliku bin_przyklad.txt poprawna odpowiedź to 10001111110111100000.

Zadanie 2.4. (0–1) Dla nieujemnych liczb całkowitych a i b wynikiem operacji a XOR b jest liczba, której kolejne bity są wyliczane z odpowiadających sobie bitów liczb a i b: bit wyniku jest równy 1, gdy bity są różne, a 0, gdy są takie same (krótszy zapis uzupełniamy zerami z lewej strony). Przykłady z arkusza: 4₁₀ XOR 7₁₀ = 100₂ XOR 111₂ = 011₂ = 3₁₀; 6₁₀ XOR 11₁₀ = 0110₂ XOR 1011₂ = 1101₂ = 13₁₀. Oblicz (123₁₀ XOR 101101₂) XOR 2D₁₆. Wynik podaj w systemie dziesiętnym.

Zadanie 2.5. (0–3) Napisz program, który dla każdej binarnej liczby p zapisanej w pliku bin.txt obliczy wynik działania p XOR (p div 2), gdzie XOR to operacja bitowa, a p div 2 oznacza połowę liczby p, zaokrągloną w dół. Otrzymane wyniki podaj w systemie binarnym. Zapisz je do pliku wyniki2_5.txt w kolejności występowania liczb w pliku bin.txt, każdy wynik w oddzielnym wierszu.

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

Rozwiązanie

2.1. Algorytm na liczbach (bez zamiany na napis — tego zabrania treść). Odczytujemy kolejne bity od najmłodszego (n mod 2) i zwiększamy licznik przy każdej zmianie cyfry; tak wygląda przykładowe rozwiązanie z zasad oceniania CKE:

b ← 1
poprzednia ← n mod 2
n ← n div 2
dopóki n > 0
    cyfra ← n mod 2
    jeśli cyfra ≠ poprzednia
        b ← b + 1
    poprzednia ← cyfra
    n ← n div 2

Dla 67 (1000011₂) → bloki 1, 0000, 11 → b = 3. Dla 245 (11110101₂) → bloki 1111, 0, 1, 0, 1 → b = 5.

2.2. Odpowiedź z zasad oceniania CKE: 10. W programie liczba bloków to 1 + liczba miejsc, w których sąsiednie cyfry napisu się różnią:

count = 0
for line in open("bin.txt"):
    s = line.strip()
    bloki = 1 + sum(1 for i in range(1, len(s)) if s[i] != s[i - 1])
    if bloki <= 2:
        count += 1
print(count)

2.3. Odpowiedź z zasad oceniania CKE: 1110100011100011100. Zapisy nie mają zer wiodących, więc większa jest liczba o dłuższym zapisie, a przy równej długości – większa leksykograficznie:

print(max((l.strip() for l in open("bin.txt")), key=lambda s: (len(s), s)))

2.4. Odpowiedź: 123.

123₁₀ = 1111011₂
101101₂ = 45₁₀
2D₁₆ = 2·16 + 13 = 45₁₀ = 101101₂

1111011₂ XOR 0101101₂ = 1010110₂ (86₁₀); 1010110₂ XOR 0101101₂ = 1111011₂ = 123₁₀. Ten sam wynik widać od razu: x XOR 45 XOR 45 = x.

2.5. Program:

with open("bin.txt") as f, open("wyniki2_5.txt","w") as out:
    for line in f:
        p = int(line.strip(), 2)
        r = p ^ (p // 2)
        out.write(bin(r)[2:] + "\n")

Wynikiem p XOR (p div 2) jest kod Graya liczby p. Zasady oceniania CKE podają 100 wyników dla pliku bin.txt (3 pkt za wyniki w systemie binarnym, 2 pkt – za poprawne wyniki zapisane dziesiętnie).

Typowy błąd / pułapka

Zad. 2.1 — liczba bloków to 1 + liczba zmian cyfry (zarówno 0→1, jak i 1→0). Zamiana liczby na napis binarny funkcją wbudowaną jest w 2.1 zabroniona. Zad. 2.4 — przed wykonaniem XOR sprowadź wszystkie liczby do tej samej podstawy (najwygodniej binarnej); 101101 jest tu zapisem dwójkowym, a 2D – szesnastkowym. Zad. 2.5 — wyniki trzeba zapisać w systemie binarnym; za wyniki dziesiętne zasady oceniania dają 2 pkt z 3.

Strona arkusza CKE z treścią zadania

Zadanie 2 - informatyka 2023 PR — Strona arkusza CKE 2023 PR informatyka - zadanie 2 (Liczby binarne). Na podstawie: CKE 2023 Oryginalny PDF CKE, str. 8

Rozwiązanie

2.1. Algorytm zliczający bloki

Idea: blok kończy się tam, gdzie zmienia się cyfra. Liczba bloków = liczba zmian + 1.

def liczba_blokow(n):
    # tylko operacje na liczbach całkowitych (funkcje wbudowane typu bin() są w 2.1 zabronione)
    b = 1
    poprzednia = n % 2
    n = n // 2
    while n > 0:
        cyfra = n % 2
        if cyfra != poprzednia:
            b += 1
        poprzednia = cyfra
        n = n // 2
    return b

2.2. Liczby o ≤ 2 blokach

Liczba ma 1 blok ⇔ same jedynki (bo liczba dodatnia, więc zaczyna się od 1). Liczba ma 2 bloki ⇔ kilka 1, potem kilka 0 (zaczyna od 1, kończy zerem) – żadne inne wzorce.

count = sum(1 for line in open("bin.txt") if liczba_blokow(int(line.strip(), 2)) <= 2)
print(count)  # 10

2.3. Największa liczba

Porównujemy po (długość, wartość binarna):

print(max((l.strip() for l in open("bin.txt")), key=lambda s: (len(s), s)))

2.4. XOR ze zmianą systemów

Sprowadzamy wszystkie do binarnego, XOR-ujemy po bitach, konwertujemy na dziesiętny.

2.5. Kod Graya

g = p XOR (p >> 1) to standardowa formuła zamiany na kod Graya.

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 „liczby binarne, bloki, XOR, operacje bitowe, programowanie” zrobisz samodzielnie.

Otwórz matury-online.pl