{"id":"informatyka-2017-maj-matura-rozszerzona/zad/2.3","paper_id":"informatyka-2017-maj-matura-rozszerzona","number":"2.3","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2017,"month":"maj","level":"rozszerzona","text":"Zadanie 2.3. (0-2)\nPodaj najmniejszą liczbę całkowitą x większą od 100, dla której wynikiem wywołania\nlicz(x) będzie 0.\nOdpowiedź:\nMiejsce na obliczenia\nWypełnia\negzaminator\nNr zadania\n2.1.\n2.2.\n2.3.\nMaks. liczba pkt.\n2\n2\n2\nUzyskana liczba pkt.\nMIN_1R","answer":null,"answer_text":"Zadanie 2.3. (0-2)\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […],\nz zastosowaniem podejścia algorytmicznego.\n5) posługuje się podstawowymi technikami\nalgorytmicznymi;\n9) stosuje rekurencję w prostych sytuacjach\nproblemowych\n16) opisuje własności algorytmów na\npodstawie ich analizy;\n17) ocenia zgodność algorytmu ze\nspecyfikacją problemu;\nSchemat punktowania\n2 p. - za prawidłową odpowiedź.\n1 p. - za podanie innej wartości większej od 100, dla której wynikiem działania algorytmu\nbędzie 0.\n0 p. - za podanie innej błędnej odpowiedzi albo brak odpowiedzi.\nPoprawna odpowiedź:\n135","solution":"## Poprawna odpowiedź\n\n**x = 135**\n\n135 w binarnym to **10000111** (8 bitów, 4 jedynki, 4 zera). licz(135) = 4 - 4 = 0.\n\n## Sposób 1 - wykorzystanie wzoru z 2.1\n\nZ zadania 2.1 wiemy: **licz(x) = (liczba jedynek w bin(x)) - (liczba zer w bin(x))**.\n\nlicz(x) = 0 oznacza: **liczba jedynek = liczba zer** w zapisie binarnym x.\n\n**Wniosek:** x musi mieć parzystą liczbę bitów (2k bitów: k jedynek i k zer). Najmłodszy bit może być 0 lub 1, najstarszy zawsze 1.\n\n## Sposób 2 - szukamy najmniejszego x > 100\n\n100 w binarnym = 1100100 (7 bitów). Szukamy x > 100 z równą liczbą 0 i 1.\n\nLiczby 8-bitowe (najmniejsza = 128 = 10000000) zakres: 128-255.\n\nDla x = 128, 129, , 135 sprawdzamy:\n- 128 = 10000000: 1 jedynka, 7 zer → licz = -6\n- 129 = 10000001: 2 j, 6 z → -4\n- 130 = 10000010: 2 j, 6 z → -4\n- 131 = 10000011: 3 j, 5 z → -2\n- 132 = 10000100: 2 j, 6 z → -4\n- 133 = 10000101: 3 j, 5 z → -2\n- 134 = 10000110: 3 j, 5 z → -2\n- **135 = 10000111: 4 j, 4 z → licz = 0** ✓\n\nMniejsze liczby? Sprawdźmy też 7-bitowe (64-127):\n- Liczba 7-bitowa ma 7 bitów; równa liczba 0 i 1 wymaga **parzystej liczby bitów** - niemożliwe!\n- Wszystkie 7-bitowe mają licz(x) parzyste? Tak: 7 = 1 + 6 lub 3 + 4 lub 5 + 2 lub 7 + 0 → różnica nieparzysta. Niemożliwe licz = 0.\n\nWięc x > 100 z licz = 0 musi być co najmniej 8-bitowe, czyli x ≥ 128. Sprawdzone - najmniejsze takie x to **135**.\n\n## Sposób 3 - weryfikacja symulacją (Python)\n\n```python\ndef licz(x):\nif x == 1:\nreturn 1\nw = licz(x // 2)\nif x % 2 == 1:\nreturn w + 1\nelse:\nreturn w - 1\n\nfor x in range(101, 200):\nif licz(x) == 0:\nprint(x)\nbreak\n# wynik: 135\n\nSymulacja licz(135) krok po kroku:\n- licz(135): bit=1 → w = licz(67), wynik = w+1\n- licz(67): bit=1 → w = licz(33), wynik = w+1\n- licz(33): bit=1 → w = licz(16), wynik = w+1\n- licz(16): bit=0 → w = licz(8), wynik = w-1\n- licz(8): bit=0 → w = licz(4), wynik = w-1\n- licz(4): bit=0 → w = licz(2), wynik = w-1\n- licz(2): bit=0 → w = licz(1), wynik = w-1\n- licz(1) = 1\n- licz(2) = 0; licz(4) = -1; licz(8) = -2; licz(16) = -3\n- licz(33) = -3 + 1 = -2\n- licz(67) = -2 + 1 = -1\n- licz(135) = -1 + 1 = **0** ✓\n\n## Reference algorytmiczny - bilans bitów\n\n> Reference - bilans bitów w zapisie binarnym:\n> - Suma j + z = liczba bitów (długość zapisu).\n> - Różnica j - z = licz(x) (z zadania 2.1).\n> - Aby j = z konieczne: parzysta długość zapisu. Najmniejsze x o takiej własności i > 100 to liczba 8-bitowa, najmłodsza spełniająca to 10000111 = 135.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.3, max 2 pkt):\n> - **2 pkt** - za **135**\n> - **1 pkt** - za inną liczbę x > 100, dla której licz(x) = 0 (np. 139, 141, 142, 147, )\n> - **0 pkt** - błąd lub brak\n\n## Typowe pułapki\n\n- **Próba 100-127** - żadna 7-bitowa liczba nie da licz = 0 (nieparzysta długość).\n- **Pominięcie wymogu „>100\"** - 51 = 110011 daje licz = 0, ale 51 < 100.\n- **Błąd rachunkowy w zliczeniu bitów** - 135 = 128 + 4 + 2 + 1 = 10000111 (bit 7 + bity 0-2).\n\n## Złożoność obliczeniowa\n\n- Bezpośrednie szukanie x w pętli: O((x_wynik - 100) · log x_wynik) ≈ O(35 · 8) = O(280) - trywialne.","image":"img/informatyka-2017-maj-matura-rozszerzona/zad-2.3.webp","solution_image":null,"topics":null,"page_from":5,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2017 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 2.3. (0-2)
Podaj najmniejszą liczbę całkowitą x większą od 100, dla której wynikiem wywołania
licz(x) będzie 0.
Odpowiedź:
Miejsce na obliczenia
Wypełnia
egzaminator
Nr zadania
2.1.
2.2.
2.3.
Maks. liczba pkt.
2
2
2
Uzyskana liczba pkt.
MIN_1R

","answer_text_html":"

Zadanie 2.3. (0-2)
III. Rozwiązywanie problemów
i podejmowanie decyzji […],
z zastosowaniem podejścia algorytmicznego.

\n
  1. posługuje się podstawowymi technikami
\n

algorytmicznymi;

\n
  1. stosuje rekurencję w prostych sytuacjach
\n

problemowych

\n
  1. opisuje własności algorytmów na
\n

podstawie ich analizy;

\n
  1. ocenia zgodność algorytmu ze
\n

specyfikacją problemu;
Schemat punktowania
2 p. - za prawidłową odpowiedź.
1 p. - za podanie innej wartości większej od 100, dla której wynikiem działania algorytmu
będzie 0.
0 p. - za podanie innej błędnej odpowiedzi albo brak odpowiedzi.
Poprawna odpowiedź:
135

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

x = 135

\n

135 w binarnym to 10000111 (8 bitów, 4 jedynki, 4 zera). licz(135) = 4 - 4 = 0.

\n

Sposób 1 - wykorzystanie wzoru z 2.1

\n

Z zadania 2.1 wiemy: licz(x) = (liczba jedynek w bin(x)) - (liczba zer w bin(x)).

\n

licz(x) = 0 oznacza: liczba jedynek = liczba zer w zapisie binarnym x.

\n

Wniosek: x musi mieć parzystą liczbę bitów (2k bitów: k jedynek i k zer). Najmłodszy bit może być 0 lub 1, najstarszy zawsze 1.

\n

Sposób 2 - szukamy najmniejszego x > 100

\n

100 w binarnym = 1100100 (7 bitów). Szukamy x > 100 z równą liczbą 0 i 1.

\n

Liczby 8-bitowe (najmniejsza = 128 = 10000000) zakres: 128-255.

\n

Dla x = 128, 129, , 135 sprawdzamy:

\n\n

Mniejsze liczby? Sprawdźmy też 7-bitowe (64-127):

\n\n

Więc x > 100 z licz = 0 musi być co najmniej 8-bitowe, czyli x ≥ 128. Sprawdzone - najmniejsze takie x to 135.

\n

Sposób 3 - weryfikacja symulacją (Python)

\n

```python
def licz(x):
if x == 1:
return 1
w = licz(x // 2)
if x % 2 == 1:
return w + 1
else:
return w - 1

\n

for x in range(101, 200):
if licz(x) == 0:
print(x)
break

\n

wynik: 135

\n

Symulacja licz(135) krok po kroku:

\n\n

Reference algorytmiczny - bilans bitów

\n
Reference - bilans bitów w zapisie binarnym:
- Suma j + z = liczba bitów (długość zapisu).
- Różnica j - z = licz(x) (z zadania 2.1).
- Aby j = z konieczne: parzysta długość zapisu. Najmniejsze x o takiej własności i > 100 to liczba 8-bitowa, najmłodsza spełniająca to 10000111 = 135.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 2.3, max 2 pkt):
- 2 pkt - za 135
- 1 pkt - za inną liczbę x > 100, dla której licz(x) = 0 (np. 139, 141, 142, 147, )
- 0 pkt - błąd lub brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}