Zadanie 1.1. (0-3)
Podaj wynik działania algorytmu dla wskazanych w tabeli wartości n.
n
p
28
64
80
Miejsce na obliczenia.
MIN_1R
Zadanie 1.1. (0-3)
Wymagania ogólne
Wymagania szczegółowe
III. Rozwiązywanie problemów
i podejmowanie decyzji […] z zastosowaniem
podejścia algorytmicznego.
i podejmowanie decyzji […], stosowanie
podejścia algorytmicznego.
Zdający:
i stosuje:
a) algorytmy na liczbach całkowitych,
podstawie ich analizy;
\nspecyfikacją problemu;
\nprzez algorytm.
Schemat punktowania
3 p. - za prawidłową odpowiedź w trzech wierszach.
2 p. - za prawidłową odpowiedź w dwóch wierszach.
1 p. - za prawidłową odpowiedź w jednym wierszu.
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Poprawna odpowiedź
n
p
28
4
64
4
80
5
| n | p |
| 28 | 4 |
| 64 | 4 |
| 80 | 5 |
Algorytm to wyszukiwanie binarne najmniejszej liczby p takiej, że p³ ≥ n.
\nInicjalizacja: p = 1, q = n. Pętla while p < q w każdej iteracji:
Koniec gdy p = q. Wynik to p = ⌈∛n⌉ (sufit pierwiastka sześciennego).
\nSzukamy p takiego, że p³ ≥ 28. Sprawdzamy: 3³=27 < 28, 4³=64 ≥ 28 → p = 4.
\n| iter | p | q | s | s³ | s³<28? | nowe p | nowe q |
| 1 | 1 | 28 | 14 | 2744 | NIE | 1 | 14 |
| 2 | 1 | 14 | 7 | 343 | NIE | 1 | 7 |
| 3 | 1 | 7 | 4 | 64 | NIE | 1 | 4 |
| 4 | 1 | 4 | 2 | 8 | TAK | 3 | 4 |
| 5 | 3 | 4 | 3 | 27 | TAK | 4 | 4 |
Kończymy: p = q = 4 ✓.
\n4³ = 64 ≥ 64 ✓ → p = 4.
\n| iter | p | q | s | s³ | s³<64? | p | q |
| 1 | 1 | 64 | 32 | 32768 | NIE | 1 | 32 |
| 2 | 1 | 32 | 16 | 4096 | NIE | 1 | 16 |
| 3 | 1 | 16 | 8 | 512 | NIE | 1 | 8 |
| 4 | 1 | 8 | 4 | 64 | NIE | 1 | 4 |
| 5 | 1 | 4 | 2 | 8 | TAK | 3 | 4 |
| 6 | 3 | 4 | 3 | 27 | TAK | 4 | 4 |
Kończymy: p = q = 4 ✓.
\n4³ = 64 < 80, 5³ = 125 ≥ 80 → p = 5.
\n| iter | p | q | s | s³ | s³<80? | p | q |
| 1 | 1 | 80 | 40 | 64000 | NIE | 1 | 40 |
| 2 | 1 | 40 | 20 | 8000 | NIE | 1 | 20 |
| 3 | 1 | 20 | 10 | 1000 | NIE | 1 | 10 |
| 4 | 1 | 10 | 5 | 125 | NIE | 1 | 5 |
| 5 | 1 | 5 | 3 | 27 | TAK | 4 | 5 |
| 6 | 4 | 5 | 4 | 64 | TAK | 5 | 5 |
Kończymy: p = q = 5 ✓.
\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
for n in [28, 64, 80]:
print(f"n={n}: p={algorytm(n)}")
Wynik:
n=28: p=4
n=64: p=4
n=80: p=5
Reference - Wyszukiwanie binarne (binary search):\n
- Wyszukuje element/wartość spełniającą warunek monotoniczny.
- Idea: dzielimy przedział na pół, sprawdzamy środek, kierujemy się w prawą lub lewą połowę.
- Złożoność: O(log n).
- Tu zastosowanie: znalezienie minimalnego p takiego, że p³ ≥ n. Funkcja monotoniczna (p³ rośnie z p) - idealna dla binary search.
Reference - Pierwiastek całkowity (integer cube root):
-⌈∛n⌉to najmniejsze całkowite p z p³ ≥ n.
- Można policzyć:p = round(n ** (1/3))lub szukaniem binarnym.
- Dla n = 64: ∛64 = 4 (idealny sześcian). Dla n = 27: ∛27 = 3.
Klucz CKE (zadanie 1.1, max 3 pkt):\n
- 3 pkt - wszystkie 3 wartości p prawidłowe
- 2 pkt - 2 prawidłowe
- 1 pkt - 1 prawidłowa
- 0 pkt - wszystkie błędne
< vs ≤ - wpływa na to, gdzie przesuwa się p i q. Tu jest s³ < n (ostry).(p+q) div 2 to floor; w Pythonie //, w C++ / dla int.p = q (nie p > q).[p, q] zmniejsza się o połowę.