{"id":"informatyka-2015-maj-matura-rozszerzona/zad/4.2","paper_id":"informatyka-2015-maj-matura-rozszerzona","number":"4.2","points":3,"ptype":"open","subject":"informatyka","category":"matura","year":2015,"month":"maj","level":"rozszerzona","text":"Kontekst - patrz zadanie 4.1.\n\nPrzykład: dla zestawu liczb 101011010011001100000, 10001001, 100100, 101010010101011011000, 100011 - trzy liczby są podzielne przez 2 i dwie liczby są podzielne przez 8.\n\nPodaj, ile liczb w pliku liczby.txt jest podzielnych przez 2 oraz ile liczb jest podzielnych przez 8.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n- **podzielne przez 2: 500**\n- **podzielne przez 8: 123**\n\n## Sposób 1 - sprawdzanie końcówki zapisu binarnego\n\n**Kluczowa obserwacja:**\n- Liczba binarna jest **podzielna przez 2** ⟺ kończy się na **0** (ostatni bit = 0).\n- Liczba binarna jest **podzielna przez 4** ⟺ kończy się na **00**.\n- Liczba binarna jest **podzielna przez 8** ⟺ kończy się na **000** (3 ostatnie bity = 0).\n- Ogólnie: podzielna przez 2^k ⟺ kończy się k zerami.\n\n**Python:**\n```python\nlicznik_2 = 0\nlicznik_8 = 0\nwith open('liczby.txt') as f:\nfor linia in f:\ns = linia.strip()\nif s.endswith('0'):\nlicznik_2 += 1\nif s.endswith('000'):\nlicznik_8 += 1\nprint('podzielne przez 2:', licznik_2) # 500\nprint('podzielne przez 8:', licznik_8) # 123\n\n## Sposób 2 - implementacja w C++ i Pascal\n\n**C++:**\n```cpp\n#include \n#include \n#include \nusing namespace std;\n\nint main() {\nifstream plik(\"liczby.txt\");\nstring s;\nint p2 = 0, p8 = 0;\nwhile (plik >> s) {\nint n = s.length();\nif (s[n-1] == '0') p2++;\nif (n >= 3 && s.substr(n-3) == \"000\") p8++;\n}\ncout << \"przez 2: \" << p2 << endl; // 500\ncout << \"przez 8: \" << p8 << endl; // 123\nreturn 0;\n}\n\n**Pascal:**\n```pascal\nprogram Podzielnosc;\nvar\nf: TextFile;\ns: String;\nn, p2, p8: Integer;\nbegin\nAssignFile(f, 'liczby.txt');\nReset(f);\np2 := 0; p8 := 0;\nwhile not Eof(f) do\nbegin\nReadln(f, s);\nn := Length(s);\nif (n >= 1) and (s[n] = '0') then Inc(p2);\nif (n >= 3) and (s[n] = '0') and (s[n-1] = '0') and (s[n-2] = '0') then Inc(p8);\nend;\nCloseFile(f);\nWriteln('przez 2: ', p2);\nWriteln('przez 8: ', p8);\nend.\n\n## Reference informatyczny - podzielność w systemie binarnym\n\n> Reference - Bity i podzielność:\n> - Bit najmniej znaczący (LSB) decyduje o parzystości: 0 = parzysta, 1 = nieparzysta.\n> - **Podzielność przez 2^k** ⟺ k najmłodszych bitów = 0.\n> - **Podzielność przez 3** w binarnym: brak prostej reguły, trzeba modulo arytmetyką.\n> - **Mod 2^k**: w arytmetyce komputerowej `n & ((1< - W tym zadaniu działamy na **string** (liczby za duże dla int), więc sprawdzamy ostatnie znaki.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 4.2, max 3 pkt):\n> - **3 pkt** - poprawne obie liczby (przez 2: 500, przez 8: 123)\n> - **2 pkt** - poprawna tylko liczba podzielnych przez 8 ALBO tylko 250 wierszy (wynik: 121/27)\n> - **1 pkt** - poprawna tylko liczba podzielnych przez 2\n> - **0 pkt** - niepełna lub błędna albo brak\n\n## Typowe pułapki\n\n- **Podzielność przez 8 = trzy ostatnie zera**, nie tylko ostatnia cyfra (= podzielne przez 2).\n- **Off-by-one w indeksowaniu Pascal**: `s[Length(s)]` to ostatni znak (od 1!), w C++ `s[n-1]` (od 0).\n- **Plik z liczbami < 3 bity** - może spowodować błąd, sprawdź `n >= 3` przed `s[n-3]`.\n- Łatwo pomylić: \"podzielna przez 8\" ⟹ \"podzielna przez 2\" (relacja zawierania) - tutaj liczymy DZIELONE PRZEZ 2 (500) i ODDZIELNIE przez 8 (123).\n- Whitespace na końcu - `s.strip()` usuwa `\\n`, `\\r`, spacje. Bez tego ostatni znak to `\\n`.\n- **Trick połowy**: liczba podzielnych przez 2 = 500 to dokładnie połowa, więc dystrybucja końcówek bitów jest jednorodna.\n\n## Złożoność obliczeniowa\n\n- Sprawdzenie końcówki: O(1) (stała liczba znaków).\n- Przetworzenie pliku: O(N · L), gdzie N = 1000, L = 250. Praktycznie O(N) = O(1000).\n- Pamięć: O(L).","image":null,"solution_image":null,"topics":null,"page_from":null,"source":"maturazai","answer_source":null,"answer_text_source":null,"solution_source":"maturazai","text_source":"maturazai","source_label":"Informatyka · Matura · maj 2015 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Kontekst - patrz zadanie 4.1.

\n

Przykład: dla zestawu liczb 101011010011001100000, 10001001, 100100, 101010010101011011000, 100011 - trzy liczby są podzielne przez 2 i dwie liczby są podzielne przez 8.

\n

Podaj, ile liczb w pliku liczby.txt jest podzielnych przez 2 oraz ile liczb jest podzielnych przez 8.

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

Poprawna odpowiedź

\n
  • podzielne przez 2: 500
  • podzielne przez 8: 123
\n

Sposób 1 - sprawdzanie końcówki zapisu binarnego

\n

Kluczowa obserwacja:

\n
  • Liczba binarna jest podzielna przez 2 ⟺ kończy się na 0 (ostatni bit = 0).
  • Liczba binarna jest podzielna przez 4 ⟺ kończy się na 00.
  • Liczba binarna jest podzielna przez 8 ⟺ kończy się na 000 (3 ostatnie bity = 0).
  • Ogólnie: podzielna przez 2^k ⟺ kończy się k zerami.
\n

Python:
```python
licznik_2 = 0
licznik_8 = 0
with open('liczby.txt') as f:
for linia in f:
s = linia.strip()
if s.endswith('0'):
licznik_2 += 1
if s.endswith('000'):
licznik_8 += 1
print('podzielne przez 2:', licznik_2) # 500
print('podzielne przez 8:', licznik_8) # 123

\n

Sposób 2 - implementacja w C++ i Pascal

\n

C++:
```cpp
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

\n

int main() {
ifstream plik("liczby.txt");
string s;
int p2 = 0, p8 = 0;
while (plik >> s) {
int n = s.length();
if (s[n-1] == '0') p2++;
if (n >= 3 && s.substr(n-3) == "000") p8++;
}
cout << "przez 2: " << p2 << endl; // 500
cout << "przez 8: " << p8 << endl; // 123
return 0;
}

\n

Pascal:
```pascal
program Podzielnosc;
var
f: TextFile;
s: String;
n, p2, p8: Integer;
begin
AssignFile(f, 'liczby.txt');
Reset(f);
p2 := 0; p8 := 0;
while not Eof(f) do
begin
Readln(f, s);
n := Length(s);
if (n >= 1) and (s[n] = '0') then Inc(p2);
if (n >= 3) and (s[n] = '0') and (s[n-1] = '0') and (s[n-2] = '0') then Inc(p8);
end;
CloseFile(f);
Writeln('przez 2: ', p2);
Writeln('przez 8: ', p8);
end.

\n

Reference informatyczny - podzielność w systemie binarnym

\n
Reference - Bity i podzielność:
- Bit najmniej znaczący (LSB) decyduje o parzystości: 0 = parzysta, 1 = nieparzysta.
- Podzielność przez 2^k ⟺ k najmłodszych bitów = 0.
- Podzielność przez 3 w binarnym: brak prostej reguły, trzeba modulo arytmetyką.
- Mod 2^k: w arytmetyce komputerowej n & ((1<<k)-1) to n mod 2^k (operacja AND).
- W tym zadaniu działamy na string (liczby za duże dla int), więc sprawdzamy ostatnie znaki.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 4.2, max 3 pkt):
- 3 pkt - poprawne obie liczby (przez 2: 500, przez 8: 123)
- 2 pkt - poprawna tylko liczba podzielnych przez 8 ALBO tylko 250 wierszy (wynik: 121/27)
- 1 pkt - poprawna tylko liczba podzielnych przez 2
- 0 pkt - niepełna lub błędna albo brak
\n

Typowe pułapki

\n
  • Podzielność przez 8 = trzy ostatnie zera, nie tylko ostatnia cyfra (= podzielne przez 2).
  • Off-by-one w indeksowaniu Pascal: s[Length(s)] to ostatni znak (od 1!), w C++ s[n-1] (od 0).
  • Plik z liczbami < 3 bity - może spowodować błąd, sprawdź n >= 3 przed s[n-3].
  • Łatwo pomylić: "podzielna przez 8" ⟹ "podzielna przez 2" (relacja zawierania) - tutaj liczymy DZIELONE PRZEZ 2 (500) i ODDZIELNIE przez 8 (123).
  • Whitespace na końcu - s.strip() usuwa \\n, \\r, spacje. Bez tego ostatni znak to \\n.
  • Trick połowy: liczba podzielnych przez 2 = 500 to dokładnie połowa, więc dystrybucja końcówek bitów jest jednorodna.
\n

Złożoność obliczeniowa

\n
  • Sprawdzenie końcówki: O(1) (stała liczba znaków).
  • Przetworzenie pliku: O(N · L), gdzie N = 1000, L = 250. Praktycznie O(N) = O(1000).
  • Pamięć: O(L).
"}]}