Darmowe konto pozwoli wrócić do niego później.
Polecenie
Cał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
Darmowe konto pozwoli wrócić do niego później.
a) W poniższym algorytmie uzupełnij instrukcję w wierszu (3) tak, żeby otrzymany algorytm był poprawny względem podanej wcześniej specyfikacji.
(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.
(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.
| n | liczba sprawdzeń warunku w wierszu 2 |
|---|---|
| --- | --- |
| 32 | |
| 1024 |
a) k := k+1; liczba sprawdzeń: n=32 to 5, n=1024 to 32
b) k := s
c) liczba sprawdzeń: n=32 to 6, n=1024 to 6
a) 2 pkt – poprawne uzupełnienie instrukcji i tabeli; 1 pkt – poprawne uzupełnienie algorytmu lub tabeli
b) 2 pkt – poprawne uzupełnienie instrukcji
c) 2 pkt – poprawne uzupełnienie tabeli dla n=32 oraz dla n=1024; 1 pkt – poprawne uzupełnienie tabeli dla n=32 lub dla n=1024
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.