Zadanie 2, specimen 2015, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Polecenie
6 punktówCałkowity pierwiastek kwadratowy
Niech n będzie dodatnią liczbą całkowitą. Całkowitym pierwiastkiem kwadratowym z liczby n nazywamy dodatnią liczbę całkowitą k taką, że k ⋅ k ≤ n i (k + 1) ⋅ (k + 1) > n. Na przykład 3 jest całkowitym pierwiastkiem kwadratowym z liczb 9, 10, 11, 12, 13, 14 i 15. W tym zadaniu analizujemy algorytmy obliczania całkowitych pierwiastków z dodatnich liczb całkowitych, które mają być poprawne względem następującej specyfikacji:
Specyfikacja:
Dane: dodatnia liczba całkowita n
Wynik: dodatnia liczba całkowita k – całkowity pierwiastek kwadratowy z liczby n
Przykład: dla n = 39 wynikiem jest k = 6
a) W poniższym algorytmie uzupełnij instrukcję w wierszu (3) tak, żeby otrzymany algorytm był poprawny względem podanej wcześniej specyfikacji.2 punkty
```
(1) k ← 1;
(2) dopóki (k+1)*(k+1) ≤ n wykonuj
(3) k ← ;
```
Podaj, ile razy warunek w wierszu (2) powyższego algorytmu jest sprawdzany odpowiednio dla n = 32 i n = 1024.
| n | liczba sprawdzeń warunku w wierszu 2 |
|---|---|
| 32 | |
| 1024 |
b) W poniższym algorytmie uzupełnij instrukcję w wierszu (5) tak, żeby otrzymany algorytm był poprawny względem podanej wcześniej specyfikacji.2 punkty
```
(1) k ← 1; m ← n;
(2) dopóki (k+1)*(k+1) ≤ n wykonuj
(3) s ← (k+m) div 2;
(4) jeśli s*s ≤ n to
(5) k ←
(6) w przeciwnym przypadku
(7) m ← s
```
Uwaga: użyty operator div oznacza dzielenie całkowite, tzn. s jest największą liczbą całkowitą nie większą od (k+m)/2.
c) Podaj, ile razy warunek w wierszu (2) z algorytmu z punktu b) jest sprawdzany odpowiednio dla n = 32 i n = 1024.2 punkty
| n | liczba sprawdzeń warunku w wierszu 2 |
|---|---|
| 32 | |
| 1024 |
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ę
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
a) Uzupełnienie: k ← k+1.
| n | Liczba sprawdzeń |
|---|---|
| 32 | 5 |
| 1024 | 32 |
b) Uzupełnienie: k ← s.
c)
| n | Liczba sprawdzeń |
|---|---|
| 32 | 6 |
| 1024 | 6 |
Schemat punktowania
a)
poprawne uzupełnienie instrukcji i tabeli.
poprawne uzupełnienie algorytmu lub tabeli.
inna odpowiedź lub brak odpowiedzi.
b)
poprawne uzupełnienie instrukcji.
inna odpowiedź lub brak odpowiedzi.
c)
poprawne uzupełnienie tabeli dla n=32 oraz dla n=1024.
poprawne uzupełnienie tabeli dla n=32 lub dla n=1024.
inna odpowiedź lub brak odpowiedzi.