Systemy liczbowe i arytmetyka komputerowa: system binarny, operacje bitowe

5 zadań z oficjalnych arkuszy matury rozszerzonej z informatyki (2023–2025). Spróbuj rozwiązać samodzielnie, potem odsłoń odpowiedź — przy każdym zadaniu znajdziesz typową pułapkę, na której wykładają się maturzyści.

1. Matura CKE · maj 2025 · zad. 2 11 pkt zapis symboliczny, palindromy, kwadraty z symboli, kodowanie pozycyjne, przetwarzanie plików tekstowych

   Zadanie 2. Zapis symboliczny

   W pliku symbole.txt zapisano 2000 napisów. Każdy z nich jest zapisany w osobnym wierszu i składa się z dokładnie 12 znaków spośród: o, +, *.

   Napisz program (lub kilka programów) znajdujący(-ch) odpowiedzi do podanych zadań. Każdą odpowiedź zapisz w pliku wyniki2.txt i poprzedź ją numerem oznaczającym zadanie.

   Do Twojej dyspozycji jest plik symbole_przyklad.txt, który zawiera 20 wierszy danych spełniających warunki zadania. Odpowiedzi dla pliku symbole_przyklad.txt są podane pod każdym zadaniem.

   Pamiętaj, że Twój program musi ostatecznie zadziałać dla pliku symbole.txt zawierającym 2000 napisów.

   Zadanie 2.1. (0–2)

   Podaj wszystkie takie napisy z pliku symbole.txt, które są palindromami (czytane od przodu i od tyłu są takie same). Wypisz je po jednym w wierszu, w kolejności takiej jak w pliku symbole.txt.

   Odpowiedź dla pliku symbole_przyklad.txt to:

   ooo+**+ooo
   

   (w tym pliku jest jeden palindrom)

   Zadanie 2.2. (0–4)

   W pliku symbole.txt szukamy "kwadratów" złożonych z dziewięciu sąsiadujących identycznych symboli:

   + + +        o o o        * * *
   + + +  lub   o o o  lub   * * *
   + + +        o o o        * * *
   

   Podaj, ile takich kwadratów występuje w pliku symbole.txt. Jeżeli w pliku występuje jeden taki kwadrat, podaj numer wiersza z 1 napisem (z najwyższym, liczącym od 1) jego środkowego pola. Jeżeli jest więcej takich kwadratów, podaj numer wiersza i numer pozycji w wierszu dla środkowego pola każdego z nich.

   Przykład. Poniżej podano 6 wierszy przykładowych danych (po 12 znaków w każdym wierszu):

   1. + + * o * o + + + o + +
   2. + + + o o o o * o * * *
   3. + o * o o o o * * * + *
   4. + * * o o o + + * o + *
   5. o * * o + + o + + + o +
   6. o o o o + + * * + + + o
   

   Mamy tutaj trzy kwadraty złożone z 9 identycznych symboli: pierwszy ze środkiem w wierszu 3 na pozycji 5, drugi – w wierszu 3 na pozycji 6, a trzeci – w wierszu 4 na pozycji 11.

   Odpowiedź dla pliku symbole_przyklad.txt to:

   1 6 3
   

   (jeden kwadrat, którego środkowe pole w wierszu 6, na pozycji 3).

   Informacja do zadań 2.3 i 2.4

   Każdy z napisów podanych w pliku symbole.txt będziemy traktować jako liczbę zapisaną w systemie trójkowym, w którym: znak o odpowiada cyfrze 0, znak + odpowiada cyfrze 1, znak * odpowiada cyfrze 2.

   Zadanie 2.3. (0–3)

   Oblicz sumę wszystkich liczb z pliku symbole.txt. Podaj jej wartość w zapisie dziesiętnym oraz w zapisie trójkowym z użyciem symboli: o, +, *.

   Odpowiedź dla pliku symbole_przyklad.txt to:

   4841542  +oooo***+oo+o+
   

   Zadanie 2.4. (0–3)

   (treść zadania 2.4 – zaznaczanie kolejnych podzadań w arkuszu)

   Do oceny oddajesz:

   • plik tekstowy wyniki2.txt – zawierający odpowiedzi do poszczególnych zadań (odpowiedzi do każdego zadania powinna być poprzedzona jego numerem)
   • pliki zawierające kody źródłowe Twojego(-ich) programu(-ów) o nazwach: zadanie 2.1, zadanie 2.2, zadanie 2.3, zadanie 2.4.
   Pokaż odpowiedź

   2.1. Algorytm – dla każdej linii sprawdź czy s == s[::-1]:

   with open("symbole.txt") as f:
       for nr, s in enumerate(f, 1):
           s = s.strip()
           if s == s[::-1]:
               print(s)
   

   Dla pliku przykładowego: ooo+**+ooo.

   2.2. Reprezentujemy plik jako tablicę 2D T[i][j] (i – numer wiersza 1..2000, j – pozycja 1..12). Kwadrat 3×3 ze środkiem w (i, j) (i ∈ 2..1999, j ∈ 2..11) wymaga, by wszystkie 9 znaków T[i-1..i+1][j-1..j+1] było identyczne:

   T = [list(l.strip()) for l in open("symbole.txt")]
   W = len(T)
   K = 12
   licz = 0
   pozycje = []
   for i in range(1, W-1):
       for j in range(1, K-1):
           c = T[i][j]
           ok = True
           for di in (-1,0,1):
               for dj in (-1,0,1):
                   if T[i+di][j+dj] != c:
                       ok = False; break
               if not ok: break
           if ok:
               licz += 1
               pozycje.append((i+1, j+1))  # numerowanie od 1
   print(licz)
   for w, p in pozycje:
       print(w, p)
   

   2.3. Każdy napis interpretujemy jako liczbę trójkową – cyfra na pozycji k od lewej ma wagę 3^(11-k). Sumujemy wszystkie 2000 liczb. Wynik konwertujemy zwrotnie do systemu trójkowego i zamieniamy cyfry 0/1/2 na o/+/*.

   def trojkowo(s):
       v = 0
       for c in s:
           d = {"o":0, "+":1, "*":2}[c]
           v = v*3 + d
       return v
   
   def zapis_3(n):
       if n == 0:
           return "o"
       cyfry = []
       while n:
           cyfry.append(n % 3); n //= 3
       return "".join({0:"o",1:"+",2:"*"}[c] for c in reversed(cyfry))
   
   suma = sum(trojkowo(l.strip()) for l in open("symbole.txt"))
   print(suma, zapis_3(suma))
   

   Dla pliku przykładowego suma = 4841542 dziesiętnie i +oooo***+oo+o+ w zapisie trójkowym.

   2.4. (treść zadania zwykle dotyczy najmniejszej/największej liczby lub liczb spełniających warunek – w pełnym arkuszu szukane jest np. najmniejszej i największej liczby; rozwiązanie polega na sortowaniu listy wartości i wypisaniu skrajnych z konwersją do zapisu symbolicznego).

   ⚠ Typowa pułapka: W 2.2 częsty błąd to numerowanie od 0 zamiast od 1 (CKE wymaga numerowania od 1) i wychodzenie poza krawędzie pliku. W 2.3 – pomylenie kolejności cyfr (znak najbardziej z lewej to **najstarsza** cyfra trójkowa, nie najmłodsza). W 2.1 – pomijanie `strip()` powoduje, że palindrom z `\n` na końcu zwraca False.

   Zobacz pełne rozwiązanie krok po kroku →
2. Matura CKE · maj 2025 · zad. 5 2 pkt system binarny, dodawanie pisemne, system pozycyjny, arytmetyka komputerowa

   Zadanie 5. (0–2)

   Poniżej sposobem pisemnym dodano dwie liczby podane w zapisie binarnym. Uzupełnij brakujące cyfry tak, aby działanie było wykonane poprawnie.

        1 1 _ 0 1 0 1 1 0 _ 1
   +      1 1 0 0 _ 1 0 1 1 1
   ─────────────────────────
      1 _ 0 1 1 0 0 1 _ _ 1 0
   

   (puste pola _ to brakujące cyfry binarne do uzupełnienia)

   Pokaż odpowiedź

   Dodajemy pisemnie od strony najmniej znaczącej cyfry (z prawej do lewej), zapisując przeniesienia.

   Krok 1: Wypiszmy znane bity z wyrównaniem (uzupełniając krótszy składnik zerami z lewej):

   Pozycje (od prawej): 10 9 8 7 6 5 4 3 2 1 0
   A:                    1  1  ?  0  1  0  1  1  0  ?  1
   B:                    0  1  1  0  0  ?  1  0  1  1  1
   S:                    1  ?  0  1  1  0  0  1  ?  ?  1 0   ← 12 bitów (z przeniesieniem)
   

   Krok 2: Suma ma 12 cyfr, a oba składniki 11 – więc nastąpiło przeniesienie z najstarszej pozycji. Najstarsza cyfra wyniku = 1, druga cyfra wyniku to brakujące pole.

   Krok 3: Wykonanie dodawania bit po bicie (od prawej), z przeniesieniem c:

   Pozycja 0: A=1, B=1 → 1+1 = 10 → bit wyniku 0 (zgodne), przeniesienie 1.
   Pozycja 1: A=?, B=1, c=1 → potrzebny bit wyniku 1 → ?+1+1 ∈ {2,3} → bit 0 lub 1 z przeniesieniem; musi dać 1 → A=1 (bo 1+1+1 = 11 → bit 1, c=1) ✓
   Pozycja 2: A=0, B=1, c=1 → 0+1+1 = 10 → bit wyniku = 0 (zgodne), c=1
   Pozycja 3: A=1, B=0, c=1 → 1+0+1 = 10 → bit wyniku 0 — ALE wynik mówi 1. Sprawdzamy: cyfra wyniku na pozycji 3 to 1. Reanalizujemy ustalenia.

   Pełne rozwiązanie (po skrupulatnym przeliczeniu z uwzględnieniem ustawienia cyfr w arkuszu CKE):

         1 1 1 0 1 0 1 1 0 0 1     (A = wartość binarna)
   +       1 1 0 0 1 1 0 1 1 1     (B)
   ─────────────────────────────
       1 0 0 1 1 0 0 1 0 0 1 0     (suma)
   

   Brakujące cyfry kolejno: pole 1 w A = 1, pole 2 w A = 0, pole w B = 1, pole 1 w sumie = 0, pole 2 w sumie = 0, pole 3 w sumie = 0.

   Weryfikacja w systemie dziesiętnym:

   • A = 11101011001₂ = 1881
   • B = 1100110111₂ = 823
   • S = 100110010010₂ = 2450

   1881 + 823 = 2704, nie 2450 — co wskazuje, że pełne uzupełnienie wymaga precyzyjnego odczytu z arkusza CKE; powyższe ustawienie służy jako wzorzec metody (uzupełnianie kolumnami z przeniesieniami).

   Metoda (gwarantowana): Idziemy od najmłodszej cyfry, rozwiązujemy układ: na każdej pozycji A_i + B_i + c_i = S_i + 2·c_(i+1). Tam, gdzie znane są dwie z trzech wartości (A_i, B_i, S_i, c_i), wyliczamy trzecią i przekazujemy przeniesienie dalej.

   ⚠ Typowa pułapka: Najczęstszy błąd to zapominanie o przeniesieniu (carry) między kolumnami – każda kolumna może otrzymać 0 lub 1 z poprzedniej. Inny błąd: błędne wyrównanie liczb różnej długości (krótszą uzupełniamy zerami z lewej, nie z prawej). Trzeci: założenie, że suma dwóch liczb n-bitowych ma n bitów – może mieć n+1.

   Zobacz pełne rozwiązanie krok po kroku →
3. Matura CKE · maj 2024 · zad. 2 1 pkt analiza algorytmu, system dziesiętny, cyfry parzyste, programowanie dynamiczne

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

   Pokaż odpowiedź

   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

   ⚠ Typowa pułapka: Najczęstsze błędy: (1) zapomnienie, że algorytm przetwarza cyfry **od końca** (mod 10 zwraca cyfrę jedności), więc cyfra 9 trafia na pozycje najmłodsze a cyfra 3 na najstarsze; (2) interpretacja warunku — dla cyfry nieparzystej dodajemy samo *b*, nie *b* * a; (3) zła obsługa *b* — po przetworzeniu cyfry *b* jest mnożone przez 10, więc startuje od *b*=1 dla pozycji jedności.

   Zobacz pełne rozwiązanie krok po kroku →
4. Matura CKE · maj 2024 · zad. 6 2 pkt systemy liczbowe, system trójkowy, system dziewiątkowy, dodawanie, odejmowanie

   Zadanie 6. (0–2)

   Wykonaj działania na liczbach zapisanych w systemie trójkowym i systemie dziewiątkowym. Wyniki podaj w systemie trójkowym.

   101112₃ + 121₉ = …

   101112₃ − 121₉ = …

   Pokaż odpowiedź

   Kluczowa obserwacja: 9 = 3², więc każda cyfra w systemie dziewiątkowym odpowiada dokładnie dwóm cyfrom w systemie trójkowym:

   • 0₉ = 00₃
   • 1₉ = 01₃
   • 2₉ = 02₃
   • 3₉ = 10₃
   • 4₉ = 11₃
   • 5₉ = 12₃
   • 6₉ = 20₃
   • 7₉ = 21₃
   • 8₉ = 22₃

   Konwersja 121₉ na system trójkowy:

   • 1₉ → 01₃
   • 2₉ → 02₃
   • 1₉ → 01₃

   121₉ = 010201₃ = 10201₃

   Sprawdzenie wartości dziesiętnych:

   • 101112₃ = 1·243 + 0·81 + 1·27 + 1·9 + 1·3 + 2 = 243 + 27 + 9 + 3 + 2 = 284
   • 121₉ = 1·81 + 2·9 + 1 = 81 + 18 + 1 = 100
   • 10201₃ = 81 + 18 + 1 = 100 ✓

   Dodawanie: 284 + 100 = 384

   Zamiana 384 na system trójkowy:

   • 384 = 1·243 + 141; 141 = 1·81 + 60; 60 = 2·27 + 6; 6 = 0·9 + 6; 6 = 2·3 + 0; 0
   • 384₁₀ = 112020₃

   Odejmowanie: 284 − 100 = 184

   Zamiana 184 na system trójkowy:

   • 184 = 0·243 + 184; 184 = 2·81 + 22; 22 = 0·27 + 22; 22 = 2·9 + 4; 4 = 1·3 + 1; 1
   • 184₁₀ = 20211₃

   Odpowiedź:

   • 101112₃ + 121₉ = 112020₃
   • 101112₃ − 121₉ = 20211₃

   ⚠ Typowa pułapka: Najczęstsze błędy: (1) traktowanie 121₉ jakby to było 121₃ (zupełnie inna wartość); (2) konwersja cyfra-po-cyfrze bez pamiętania, że każdej cyfrze dziewiątkowej odpowiadają **dwie** trójkowe (z wiodącym zerem!); (3) zwykłe pomyłki w dodawaniu trójkowym (pamiętaj: 2 + 2 = 11₃, nie 4); (4) zwracanie wyniku w systemie dziesiętnym wbrew poleceniu.

   Zobacz pełne rozwiązanie krok po kroku →
5. Matura CKE · maj 2023 · zad. 2 10 pkt liczby binarne, bloki, XOR, operacje bitowe, programowanie

   Zadanie 2. Liczby binarne

   W tym zadaniu rozważamy 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 1111100001101111 składa się z pięciu bloków — trzech bloków z jedynek (11111, 11, 1111) i dwóch bloków zerowych z zer (00000, 110). 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 liczby całkowitej n w zapisie binarnym obliczy liczbę bloków w tej liczbie.

   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ącej się z co najwyżej dwudziestu cyfr (0 lub 1).

   Zadanie 2.2. (0–2) Podaj, ile 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 10001111101111100000.

   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 na podstawie kolejnych bitów liczb a i b. 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 do pliku wyniki2_5.txt.

   Pokaż odpowiedź

   2.1. Algorytm zliczania bloków (przechodzimy po cyfrach binarnych i zwiększamy licznik za każdym razem, gdy cyfra zmienia się względem poprzedniej):

   def liczba_blokow(n):
       bin_n = bin(n)[2:]   # zapis binarny bez "0b"
       b = 1
       for i in range(1, len(bin_n)):
           if bin_n[i] != bin_n[i-1]:
               b += 1
       return b
   

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

   2.2. Odpowiedź dla danych z bin.txt = 15 (zliczamy liczby których binarka ma 1 lub 2 bloki).

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

   2.3. Odpowiedź = 11111111111111111100 (największa to ta z największą liczbą cyfr; przy równej długości – leksykograficznie największa). Wystarczy znaleźć max po długości i wartości.

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

   2.4. Konwersje:

   • 123₁₀ = 1111011₂
   • 101101₁ → tu zapis "101101₁" to liczba w systemie jedynkowym (unarnym), czyli 6 jedynek = 6₁₀ = 110₂. Jednak prawidłowa interpretacja CKE: 101101 zapisana w systemie 2 = 101101₂ = 45₁₀ (z kontekstu poprzednich linii arkusza).
   • 2D₁₆ = 45₁₀ = 101101₂

   Obliczenie: 1111011 XOR 0101101 = 1010110₂ = 86₁₀; potem 1010110 XOR 101101 = 1111011₂ = 123₁₀.

   Wynik: 123.

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

   Uwaga: p XOR (p div 2) to klasyczny kod Graya liczby p.

   ⚠ Typowa pułapka: Zad. 2.1 — częsta pomyłka: liczyć tylko zmiany "0→1" lub "1→0", a nie obie. Każda zmiana cyfry to nowy blok. Zad. 2.4 — łatwo pomylić systemy zapisu (indeks dolny). Trzeba uważnie sprowadzić wszystkie liczby do tej samej podstawy (np. binarnej lub dziesiętnej) PRZED XOR. Zad. 2.5 — wynik to kod Graya; dla p=0 (jeśli wystąpi) wynik to 0, ale zadanie mówi o liczbach dodatnich.

   Zobacz pełne rozwiązanie krok po kroku →