Zadanie 2, specimen 2015, informatyka rozszerzona

6 pktotwarteśrednie (szac.)Specimen 2015

Darmowe konto pozwoli wrócić do niego później.

Zadanie

Polecenie

6 punktów

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

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.

nliczba 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

nliczba sprawdzeń warunku w wierszu 2
32
1024

Korepetytor

Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.

Wypróbuj za darmo

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.

nLiczba sprawdzeń
325
102432

b) Uzupełnienie: k ← s.

c)

nLiczba sprawdzeń
326
10246

Schemat punktowania

a)

2 pkt

poprawne uzupełnienie instrukcji i tabeli.

1 pkt

poprawne uzupełnienie algorytmu lub tabeli.

0 pkt

inna odpowiedź lub brak odpowiedzi.

b)

2 pkt

poprawne uzupełnienie instrukcji.

0 pkt

inna odpowiedź lub brak odpowiedzi.

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.

0 pkt

inna odpowiedź lub brak odpowiedzi.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.