Zadanie 1.3, matura maj 2018, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 1. Analiza algorytmu
Rozważamy następujący algorytm:
Dane:
n – liczba całkowita dodatnia
Wynik:
p – liczba całkowita dodatnia
```
p ← 1
q ← n
dopóki p < q wykonuj
s ← (p+q) div 2
(*) jeżeli s*s*s < n wykonaj
p ← s+1
w przeciwnym wypadku
q ← s
```
Uwaga: zapis div oznacza dzielenie całkowite.
Polecenie
1 punktDokończ zdanie. Wybierz i zaznacz właściwą odpowiedź spośród podanych.
Dla każdej liczby całkowitej n > 1 instrukcja oznaczona w algorytmie symbolem (*) wykona się
- Amniej niż 2 ⋅ log2 n razy.
- Bwięcej niż n/2, ale mniej niż n razy.
- Cwięcej niż n + 1, ale mniej niż 2n razy.
- Dwięcej niż n2 razy.
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Odpowiedz bezpośrednio w aplikacji
To zadanie może sprawdzić się automatycznie według klucza.
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
A
Schemat punktowania
za poprawną odpowiedź.
za podanie odpowiedzi błędnej albo brak odpowiedzi.
Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.
Komentarz. Instrukcja (*) oznacza porównanie w pętli wyszukiwania binarnego, które wykonuje się O(log n) razy.