# Informatyka — zadanie 1.1 > Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2018-05/zad/1.1 > Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej. - arkusz: Informatyka · Matura · maj 2018 (rozszerzona) - rok: 2018 - poziom: rozszerzona - typ: open - punkty: 3 - działy: Programowanie i algorytmika, algorytmy ## Treść Zadanie 1. Analiza algorytmu Rozważamy następujący algorytm: **Dane:** n - liczba całkowita dodatnia **Wynik:** p - liczba całkowita dodatnia Uwaga: zapis div oznacza dzielenie całkowite. Podaj wynik działania algorytmu dla wskazanych w tabeli wartości n. n | p 28 | ? 64 | ? 80 | ? ## Rozwiązanie — maturazai.pl (AI) ## Poprawna odpowiedź | n | p | | 28 | **4** | | 64 | **4** | | 80 | **5** | ## Sposób 1 - interpretacja algorytmu **Algorytm to wyszukiwanie binarne najmniejszej liczby p takiej, że p³ ≥ n.** Inicjalizacja: p = 1, q = n. Pętla `while p < q` w każdej iteracji: - s = (p+q) div 2 - Jeśli s³ < n → szukamy w prawej części: p = s+1 - W przeciwnym razie → szukamy w lewej części: q = s Koniec gdy p = q. Wynik to **p = ⌈∛n⌉** (sufit pierwiastka sześciennego). ## Sposób 2 - symulacja krok po kroku ### n = 28 Szukamy p takiego, że p³ ≥ 28. Sprawdzamy: 3³=27 < 28, 4³=64 ≥ 28 → **p = 4**. | 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** ✓. ### n = 64 4³ = 64 ≥ 64 ✓ → **p = 4**. | 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** ✓. ### n = 80 4³ = 64 < 80, 5³ = 125 ≥ 80 → **p = 5**. | 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** ✓. ## Sposób 3 - implementacja Python (weryfikacja) ```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 informatyczny - wyszukiwanie binarne > Reference - Wyszukiwanie binarne (binary search): > - 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. ## Schemat oceniania CKE > Klucz CKE (zadanie 1.1, max 3 pkt): > - **3 pkt** - wszystkie 3 wartości p prawidłowe > - **2 pkt** - 2 prawidłowe > - **1 pkt** - 1 prawidłowa > - **0 pkt** - wszystkie błędne ## Typowe pułapki - **Pomyłka warunku `<` vs `≤`** - wpływa na to, gdzie przesuwa się p i q. Tu jest `s³ < n` (ostry). - **div = dzielenie całkowite** - `(p+q) div 2` to floor; w Pythonie `//`, w C++ `/` dla int. - **Pomylenie warunku zakończenia** - kończymy gdy `p = q` (nie `p > q`). - **Niepoprawne s³** - uważać na 14³ = 2744, 32³ = 32768 (duże liczby, ale w int wystarczy). - **Pomyłka „64³” zamiast „4³”** - czytanie n jako liczby do potęgowania, podczas gdy potęgujemy s. - **Mylenie p i q** - p to dolna granica, q to górna; szukamy minimalnego. ## Złożoność obliczeniowa - W każdej iteracji przedział `[p, q]` zmniejsza się o połowę. - Liczba iteracji: O(log n). - Każda iteracja: stały koszt (mnożenie + porównanie). - **Łącznie: O(log n)** operacji. ## Linki - [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2018-05/zad/1.1) - [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2018-05%2Fzad%2F1.1) ## Podobne zadania - [Zadanie 3](https://matura.lol/question/informatyka-2026-maj-matura-rozszerzona/zad/3) — Zadanie 3. Pary slow W pliku tekstowym pary.txt znajduje sie 500 par slow zlozonych z liter alfabetu angielskiego a, b, , z. Kazda para slow jest zapisana w oso - [Zadanie 2](https://matura.lol/question/informatyka-2026-maj-matura-rozszerzona/zad/2) — Zadanie 2. Dodawanie Rozwazamy dodawanie pisemne dwoch liczb zapisanych w systemie dziesietnym, zilustrowane na przykladzie. Przeniesienie: 1 1 1 1 Liczba a: 2 - [Zadanie 4.2](https://matura.lol/question/informatyka-2020-lipiec-matura-rozszerzona-2/zad/4.2) — Zadanie 4.2. (0-4) Podaj wszystkie te identyfikatory dokumentów z pliku identyfikator.txt, których seria lub numer są palindromami, czyli czytane od lewej do pr - [Zadanie 4.2](https://matura.lol/question/informatyka-2018-maj-matura-rozszerzona-2/zad/4.2) — Kontekst - patrz zadanie 4.1. Znajdź słowo, w którym występuje największa liczba **różnych** liter. Wypisz to słowo i liczbę występujących w nim różnych liter. _Ostatnia aktualizacja danych: 2026-10-03_