{"id":"informatyka-2018-maj-matura-rozszerzona/zad/1.2","paper_id":"informatyka-2018-maj-matura-rozszerzona","number":"1.2","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2018,"month":"maj","level":"rozszerzona","text":"Zadanie 1.2. (0-2)\nPodaj najmniejszą oraz największą liczbę n, dla której wynikiem działania algorytmu będzie\np = 10.\nMiejsce na obliczenia.\nOdpowiedź: Najmniejsza liczba to , największa liczba to","answer":null,"answer_text":"Zadanie 1.2. (0-2)\nWymagania ogólne\nWymagania szczegółowe\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […],\nz zastosowaniem podejścia algorytmicznego.\n5. Rozwiązywanie problemów\ni podejmowanie decyzji […] stosowanie\npodejścia algorytmicznego.\nZdający:\n11) opisuje podstawowe algorytmy\ni stosuje:\na) algorytmy na liczbach całkowitych,\n16) opisuje własności algorytmów na\npodstawie ich analizy;\n17) ocenia zgodność algorytmu ze\nspecyfikacją problemu;\n18) oblicza liczbę operacji wykonywanych\nprzez algorytm.\nSchemat punktowania\n2 p. - za dwie poprawne odpowiedzi.\n1 p. - za jedną poprawną odpowiedź.\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nPoprawna odpowiedź\n730, 1000","solution":"## Poprawna odpowiedź\n\n**Najmniejsza n: 730**\n\n**Największa n: 1000**\n\n## Sposób 1 - wyprowadzenie z definicji p\n\nZ zadania 1.1 wiemy, że algorytm zwraca `p = ⌈∛n⌉` - najmniejsze p takie, że **p³ ≥ n**.\n\n**Aby p = 10:**\n- 10³ ≥ n musi być spełnione → n ≤ 1000.\n- 9³ < n musi być spełnione (inaczej wynik byłby 9 lub mniejszy) → n > 729 → n ≥ 730.\n\n**Zakres: 729 < n ≤ 1000**, czyli **n ∈ {730, 731, , 1000}**.\n\n- Najmniejsza n = **730**.\n- Największa n = **1000**.\n\n## Sposób 2 - weryfikacja na granicach\n\n### n = 729 → czy p = 9?\n9³ = 729 ≥ 729 ✓, więc p = 9 (nie 10). Granica dolna jest WYŁĄCZONA z zakresu p=10.\n\n### n = 730 → czy p = 10?\n9³ = 729 < 730, 10³ = 1000 ≥ 730. Najmniejsze p z p³ ≥ 730 to **10** ✓.\n\n### n = 1000 → czy p = 10?\n10³ = 1000 ≥ 1000 ✓, najmniejsze p z p³ ≥ 1000 to **10** ✓.\n\n### n = 1001 → czy p = 11?\n10³ = 1000 < 1001, 11³ = 1331 ≥ 1001. p = **11**, nie 10. Granica górna 1000 jest WŁĄCZONA do zakresu p=10.\n\n## Sposób 3 - implementacja Python (skanowanie)\n\n```python\ndef algorytm(n):\np, q = 1, n\nwhile p < q:\ns = (p + q) // 2\nif s ** 3 < n:\np = s + 1\nelse:\nq = s\nreturn p\n\nzakres_p10 = [n for n in range(700, 1010) if algorytm(n) == 10]\nprint(\"Min:\", min(zakres_p10)) # 730\nprint(\"Max:\", max(zakres_p10)) # 1000\nprint(\"Liczność:\", len(zakres_p10)) # 271\n\n## Reference informatyczny - sufit pierwiastka sześciennego\n\n> Reference - Sufit funkcji odwrotnej:\n> - Niech `f` będzie monotoniczna rosnąca i całkowitoliczbowa.\n> - Wartość `g(n) = min { k : f(k) ≥ n }` jest funkcją odwrotną \"od góry\".\n> - Dla f(k) = k³: g(n) = ⌈∛n⌉.\n> - **Zakres wartości n** dla którego g(n) = m: `f(m-1) < n ≤ f(m)`, czyli `(m-1)³ < n ≤ m³`.\n>\n> Reference - Sześciany potęg 10:\n> - 9³ = 729\n> - 10³ = 1000\n> - 11³ = 1331\n> - 12³ = 1728\n> - 13³ = 2197\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 1.2, max 2 pkt):\n> - **2 pkt** - obie wartości prawidłowe (min = 730, max = 1000)\n> - **1 pkt** - jedna prawidłowa\n> - **0 pkt** - błędne lub brak\n\n## Typowe pułapki\n\n- **Min = 729** - pomyłka. Dla n=729 wynik to p=9 (bo 9³=729 ≥ 729). Algorytm ma warunek `s³ < n` (ostry), więc 9³ = n daje p = 9.\n- **Max = 999** - pomyłka. Dla n=1000 wynik to p=10 (bo 10³=1000 ≥ 1000). 1000 JEST w zakresie.\n- **Pomylenie krańców otwartych i zamkniętych** - z definicji algorytmu zakres to (9³, 10³] = (729, 1000] = {730, , 1000}.\n- **Niepoprawne wyliczenie 9³ lub 10³** - proste, ale uczniowie potrafią się pomylić.\n\n## Złożoność obliczeniowa\n\n- Obliczenie zakresu: O(1) (wzór).\n- Liczność zakresu: 1000 - 730 + 1 = 271 liczb.","image":"img/informatyka-2018-maj-matura-rozszerzona/zad-1.2.webp","solution_image":null,"topics":null,"page_from":3,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2018 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1.2. (0-2)
Podaj najmniejszą oraz największą liczbę n, dla której wynikiem działania algorytmu będzie
p = 10.
Miejsce na obliczenia.
Odpowiedź: Najmniejsza liczba to , największa liczba to

","answer_text_html":"

Zadanie 1.2. (0-2)
Wymagania ogólne
Wymagania szczegółowe
III. Rozwiązywanie problemów
i podejmowanie decyzji […],
z zastosowaniem podejścia algorytmicznego.

\n
  1. Rozwiązywanie problemów
\n

i podejmowanie decyzji […] stosowanie
podejścia algorytmicznego.
Zdający:

\n
  1. opisuje podstawowe algorytmy
\n

i stosuje:
a) algorytmy na liczbach całkowitych,

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

podstawie ich analizy;

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

specyfikacją problemu;

\n
  1. oblicza liczbę operacji wykonywanych
\n

przez algorytm.
Schemat punktowania
2 p. - za dwie poprawne odpowiedzi.
1 p. - za jedną poprawną odpowiedź.
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Poprawna odpowiedź
730, 1000

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

Poprawna odpowiedź

\n

Najmniejsza n: 730

\n

Największa n: 1000

\n

Sposób 1 - wyprowadzenie z definicji p

\n

Z zadania 1.1 wiemy, że algorytm zwraca p = ⌈∛n⌉ - najmniejsze p takie, że p³ ≥ n.

\n

Aby p = 10:

\n\n

Zakres: 729 < n ≤ 1000, czyli n ∈ {730, 731, , 1000}.

\n\n

Sposób 2 - weryfikacja na granicach

\n
n = 729 → czy p = 9?
\n

9³ = 729 ≥ 729 ✓, więc p = 9 (nie 10). Granica dolna jest WYŁĄCZONA z zakresu p=10.

\n
n = 730 → czy p = 10?
\n

9³ = 729 < 730, 10³ = 1000 ≥ 730. Najmniejsze p z p³ ≥ 730 to 10 ✓.

\n
n = 1000 → czy p = 10?
\n

10³ = 1000 ≥ 1000 ✓, najmniejsze p z p³ ≥ 1000 to 10 ✓.

\n
n = 1001 → czy p = 11?
\n

10³ = 1000 < 1001, 11³ = 1331 ≥ 1001. p = 11, nie 10. Granica górna 1000 jest WŁĄCZONA do zakresu p=10.

\n

Sposób 3 - implementacja Python (skanowanie)

\n

```python
def algorytm(n):
p, q = 1, n
while p < q:
s = (p + q) // 2
if s ** 3 < n:
p = s + 1
else:
q = s
return p

\n

zakres_p10 = [n for n in range(700, 1010) if algorytm(n) == 10]
print("Min:", min(zakres_p10)) # 730
print("Max:", max(zakres_p10)) # 1000
print("Liczność:", len(zakres_p10)) # 271

\n

Reference informatyczny - sufit pierwiastka sześciennego

\n
Reference - Sufit funkcji odwrotnej:
- Niech f będzie monotoniczna rosnąca i całkowitoliczbowa.
- Wartość g(n) = min { k : f(k) ≥ n } jest funkcją odwrotną "od góry".
- Dla f(k) = k³: g(n) = ⌈∛n⌉.
- Zakres wartości n dla którego g(n) = m: f(m-1) < n ≤ f(m), czyli (m-1)³ < n ≤ m³.

Reference - Sześciany potęg 10:
- 9³ = 729
- 10³ = 1000
- 11³ = 1331
- 12³ = 1728
- 13³ = 2197
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 1.2, max 2 pkt):
- 2 pkt - obie wartości prawidłowe (min = 730, max = 1000)
- 1 pkt - jedna prawidłowa
- 0 pkt - błędne lub brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}