Matura informatyka grudzień 2024, zadanie 1 (pozycje jedynek) — rozwiązanie · Variant — matura z informatyki

J(n) wypisuje pozycje jedynek w binarnym zapisie liczby, licząc od 1 od najmłodszego bitu. Bity wyciągasz przez % 2, przesuwasz przez // 2, a licznik pozycji rośnie co krok.

Arkusz CKE — grudzień 2024, test diagnostyczny, rozszerzony

Zasada

def J(n):
    b = 1                        # numer pozycji, liczony od 1
    while n > 0:
        if n % 2 == 1:
            print(b)             # bit zapalony → wypisz pozycję
        n = n // 2
        b = b + 1

To ten sam schemat co przeglądanie cyfr liczby — tylko zamiast cyfr dziesiętnych czytasz bity, a zamiast wartości wypisujesz numer pozycji.

Zadanie 1.1 — uzupełnienie tabeli

`n`	zapis dwójkowy	`J(n)`
19	10011	(1, 2, 5)
6	110	(2, 3)
42	101010	(2, 4, 6)
75	1001011	(1, 2, 4, 7)

Ostatni wiersz idzie wstecz: skoro jedynki stoją na pozycjach 1, 2, 4 i 7, to n = 2⁰ + 2¹ + 2³ + 2⁶ = 1 + 2 + 8 + 64 = 75.

Zadanie 1.2 — algorytm

Kod z sekcji „Zasada" jest gotową odpowiedzią. Warunki z treści — tylko liczby całkowite, bez konwersji typów — są spełnione: % 2 i // 2 to operatory arytmetyczne, a b to zwykły licznik.

Nie zamieniaj liczby na napis binarny. Zadanie tego zabrania, a i tak nie trzeba — % 2 daje najmłodszy bit, // 2 go usuwa, i działa to dla dowolnie wielkiej liczby.

Gdzie tracisz punkty

Numeracja pozycji. Liczysz od 1, od bitu najmłodszego, czyli od prawej. Nie od 0 i nie od lewej. Pomyłka w punkcie startowym przesuwa cały wynik i kosztuje całe zadanie.
Odwrócona kolejność przy czytaniu wstecz. Mając J(n), składasz n jako sumę potęg dwójki o wykładnikach o jeden mniejszych niż pozycje.
Użycie bin(). Kuszące i zabronione.

Co tak naprawdę liczysz

J(n) to lista potęg dwójki, które sumują się do n. Każda liczba ma dokładnie jeden taki rozkład — to jest właśnie definicja zapisu binarnego.

Liczba zapalonych bitów ma swoją nazwę: waga Hamminga, po angielsku popcount. Procesory mają osobną instrukcję sprzętową, która liczy ją w jednym takcie, bo przydaje się w kryptografii, korekcji błędów transmisji i silnikach szachowych, gdzie szachownicę trzyma się jako 64-bitową liczbę. Twoje maturalne J(n) to ta sama operacja, tylko wypisuje pozycje zamiast ich liczby.