{"id":"informatyka-2019-maj-matura-rozszerzona/zad/4.1","paper_id":"informatyka-2019-maj-matura-rozszerzona","number":"4.1","points":3,"ptype":"open","subject":"informatyka","category":"matura","year":2019,"month":"maj","level":"rozszerzona","text":"Zadanie 4. Liczby\n\nW pliku liczby.txt zapisano 500 liczb całkowitych dodatnich po jednej w każdym wierszu. Każda liczba jest z zakresu od 1 do 100 000. Napisz program(-y) dający(-e) odpowiedzi do poniższych zadań. Zapisz uzyskane odpowiedzi w pliku wyniki4.txt, poprzedzając każdą z nich numerem odpowiedniego zadania.\n\nUwaga: Plik przyklad.txt zawiera przykładowe dane spełniające warunki zadania. Odpowiedzi dla danych z tego pliku są podane pod treściami zadań.\n\nPodaj, ile z podanych liczb jest potęgami liczby 3 (czyli liczbami postaci 1 = 3⁰, 3 = 3¹, 9 = 3² itd.).\n\nDla pliku przyklad.txt odpowiedź wynosi 2.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n**Liczba potęg liczby 3 w pliku liczby.txt: 18**\n\nPotęgi 3 w zakresie [1, 100 000]: 3⁰=1, 3¹=3, 3²=9, 3³=27, 3⁴=81, 3⁵=243, 3⁶=729, 3⁷=2187, 3⁸=6561, 3⁹=19683, 3¹⁰=59049 (3¹¹=177147 > 100 000).\n\n## Sposób 1 - implementacja Python (rekomendowana)\n\n**Idea 1: prekomputacja potęg + sprawdzenie przynależności.**\n\n```python\n# Wszystkie potęgi 3 ≤ 100000\npotegi = set()\np = 1\nwhile p <= 100000:\npotegi.add(p)\np *= 3\n# potegi = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049}\n\nlicznik = 0\nwith open('liczby.txt', encoding='utf-8') as f:\nfor linia in f:\nn = int(linia.strip())\nif n in potegi:\nlicznik += 1\n\nprint(licznik) # 18\n\n**Idea 2: dzielenie przez 3 dopóki się da.**\n\n```python\ndef jest_potega_3(n):\nwhile n % 3 == 0:\nn //= 3\nreturn n == 1\n\nlicznik = 0\nwith open('liczby.txt') as f:\nfor linia in f:\nn = int(linia.strip())\nif jest_potega_3(n):\nlicznik += 1\nprint(licznik) # 18\n\n## Sposób 2 - implementacja Pascal\n\n```pascal\nprogram PotegiTrojki;\nvar\nf: TextFile;\nn, licznik, m: LongInt;\nbegin\nAssignFile(f, 'liczby.txt');\nReset(f);\nlicznik := 0;\nwhile not Eof(f) do\nbegin\nReadLn(f, n);\nm := n;\nwhile (m mod 3 = 0) do m := m div 3;\nif m = 1 then licznik := licznik + 1;\nend;\nCloseFile(f);\nWriteLn('Liczba potęg 3: ', licznik);\nend.\n\n## Sposób 3 - implementacja C++\n\n```cpp\n#include \n#include \nusing namespace std;\n\nbool jestPotega3(long long n) {\nwhile (n % 3 == 0) n /= 3;\nreturn n == 1;\n}\n\nint main() {\nifstream plik(\"liczby.txt\");\nlong long n;\nint licznik = 0;\nwhile (plik >> n) {\nif (jestPotega3(n)) licznik++;\n}\ncout << \"Liczba potęg 3: \" << licznik << endl;\nreturn 0;\n}\n\n## Sposób 4 - weryfikacja dla przyklad.txt\n\nDla `przyklad.txt` odpowiedź wynosi **2** (zgodnie z treścią zadania). Oznacza to, że w pliku przykładowym są dokładnie 2 liczby będące potęgami 3 (np. 1 i 27).\n\n## Reference informatyczny - test na potęgę liczby\n\n> Reference - Sprawdzanie czy n jest potęgą k:\n> - **Algorytm dzielenia:** dzielimy n przez k dopóki dzieli się bez reszty. Jeśli zakończymy z n=1 → jest potęgą.\n> - **Złożoność:** O(log_k(n)).\n> - **Wariant prekomputacji:** generuj wszystkie potęgi k ≤ MAX, sprawdź przynależność. Złożoność: O(1) na zapytanie (z hashsetem).\n> - **Wariant logarytmiczny (z float):** `log(n)/log(k) ∈ Z`? - ALE niedokładny przez błędy floating-point. NIE używać w zadaniach CKE.\n> - **Dla potęgi 2:** trik `(n & (n-1)) == 0` (bit-tricky).\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 4.1, max 3 pkt):\n> - **3 pkt** - prawidłowa odpowiedź (18)\n> - **2 pkt** - wynik różniący się o 1 (np. pominięcie 1=3⁰ albo licznik od 0)\n> - **1 pkt** - wynik mniejszy o 2 lub 3 (pominięcie 2-3 liczb)\n> - **0 pkt** - błędna lub brak\n\n## Typowe pułapki\n\n- **Pominięcie 1 = 3⁰** - częsty błąd: \"potęgi to 3, 9, 27 \" bez liczby 1. Treść WYRAŹNIE pisze \"liczbami postaci 1 = 3⁰\".\n- **Floating-point** w teście `log3(n) ∈ Z` - błędy zaokrąglenia mogą dać fałszywe wyniki.\n- **`n % 3 == 0` na liczbach typu 12, 15** - to nie są potęgi 3, ale dzielą się przez 3. KLUCZ: po wszystkich dzieleniach trzeba zostać z 1.\n- **Off-by-one** przy liczeniu (start od 0 vs 1).\n- **Niepoprawne czytanie pliku** - pomylenie z `print` zamiast czytania linii.\n\n## Złożoność obliczeniowa\n\n- Czytanie pliku: O(n) - n = 500 wierszy.\n- Test na potęgę 3 metodą dzielenia: O(log₃(max)) = O(log(100000)) ≈ 11 operacji.\n- **Łączna złożoność: O(n · log(max)) ≈ 5500 operacji** (bardzo szybko).\n- Pamięć: O(1) (lub O(log(max)) dla zbioru potęg).","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 2019 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 4. Liczby

\n

W pliku liczby.txt zapisano 500 liczb całkowitych dodatnich po jednej w każdym wierszu. Każda liczba jest z zakresu od 1 do 100 000. Napisz program(-y) dający(-e) odpowiedzi do poniższych zadań. Zapisz uzyskane odpowiedzi w pliku wyniki4.txt, poprzedzając każdą z nich numerem odpowiedniego zadania.

\n

Uwaga: Plik przyklad.txt zawiera przykładowe dane spełniające warunki zadania. Odpowiedzi dla danych z tego pliku są podane pod treściami zadań.

\n

Podaj, ile z podanych liczb jest potęgami liczby 3 (czyli liczbami postaci 1 = 3⁰, 3 = 3¹, 9 = 3² itd.).

\n

Dla pliku przyklad.txt odpowiedź wynosi 2.

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

Poprawna odpowiedź

\n

Liczba potęg liczby 3 w pliku liczby.txt: 18

\n

Potęgi 3 w zakresie [1, 100 000]: 3⁰=1, 3¹=3, 3²=9, 3³=27, 3⁴=81, 3⁵=243, 3⁶=729, 3⁷=2187, 3⁸=6561, 3⁹=19683, 3¹⁰=59049 (3¹¹=177147 > 100 000).

\n

Sposób 1 - implementacja Python (rekomendowana)

\n

Idea 1: prekomputacja potęg + sprawdzenie przynależności.

\n

```python

\n

Wszystkie potęgi 3 ≤ 100000

\n

potegi = set()
p = 1
while p <= 100000:
potegi.add(p)
p *= 3

\n

potegi = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049}

\n

licznik = 0
with open('liczby.txt', encoding='utf-8') as f:
for linia in f:
n = int(linia.strip())
if n in potegi:
licznik += 1

\n

print(licznik) # 18

\n

Idea 2: dzielenie przez 3 dopóki się da.

\n

```python
def jest_potega_3(n):
while n % 3 == 0:
n //= 3
return n == 1

\n

licznik = 0
with open('liczby.txt') as f:
for linia in f:
n = int(linia.strip())
if jest_potega_3(n):
licznik += 1
print(licznik) # 18

\n

Sposób 2 - implementacja Pascal

\n

```pascal
program PotegiTrojki;
var
f: TextFile;
n, licznik, m: LongInt;
begin
AssignFile(f, 'liczby.txt');
Reset(f);
licznik := 0;
while not Eof(f) do
begin
ReadLn(f, n);
m := n;
while (m mod 3 = 0) do m := m div 3;
if m = 1 then licznik := licznik + 1;
end;
CloseFile(f);
WriteLn('Liczba potęg 3: ', licznik);
end.

\n

Sposób 3 - implementacja C++

\n

```cpp
#include <iostream>
#include <fstream>
using namespace std;

\n

bool jestPotega3(long long n) {
while (n % 3 == 0) n /= 3;
return n == 1;
}

\n

int main() {
ifstream plik("liczby.txt");
long long n;
int licznik = 0;
while (plik >> n) {
if (jestPotega3(n)) licznik++;
}
cout << "Liczba potęg 3: " << licznik << endl;
return 0;
}

\n

Sposób 4 - weryfikacja dla przyklad.txt

\n

Dla przyklad.txt odpowiedź wynosi 2 (zgodnie z treścią zadania). Oznacza to, że w pliku przykładowym są dokładnie 2 liczby będące potęgami 3 (np. 1 i 27).

\n

Reference informatyczny - test na potęgę liczby

\n
Reference - Sprawdzanie czy n jest potęgą k:
- Algorytm dzielenia: dzielimy n przez k dopóki dzieli się bez reszty. Jeśli zakończymy z n=1 → jest potęgą.
- Złożoność: O(log_k(n)).
- Wariant prekomputacji: generuj wszystkie potęgi k ≤ MAX, sprawdź przynależność. Złożoność: O(1) na zapytanie (z hashsetem).
- Wariant logarytmiczny (z float): log(n)/log(k) ∈ Z? - ALE niedokładny przez błędy floating-point. NIE używać w zadaniach CKE.
- Dla potęgi 2: trik (n & (n-1)) == 0 (bit-tricky).
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 4.1, max 3 pkt):
- 3 pkt - prawidłowa odpowiedź (18)
- 2 pkt - wynik różniący się o 1 (np. pominięcie 1=3⁰ albo licznik od 0)
- 1 pkt - wynik mniejszy o 2 lub 3 (pominięcie 2-3 liczb)
- 0 pkt - błędna lub brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}