{"id":"informatyka-2015-przykladowy-arkusz-cke-rozszerzona/zad/2","paper_id":"informatyka-2015-przykladowy-arkusz-cke-rozszerzona","number":"2","points":6,"ptype":"open","subject":"informatyka","category":"przykladowy","year":2015,"month":null,"level":"rozszerzona","text":"Zadanie 2. (0-6)\nCałkowity pierwiastek kwadratowy\nNiech\nbędzie dodatnią liczbą całkowitą. Całkowitym pierwiastkiem kwadratowym\nz liczby ݊ nazywamy dodatnią liczbę całkowitą ݇ taką, że\nכ݇\n൑݊\ni ሺ݇\n൅1ሻכ ሺ݇\n൅1ሻ൐݊\nNa przykład 3 jest całkowitym pierwiastkiem kwadratowym z liczb 9, 10, 11, 12, 13, 14 i 15.\nW tym zadaniu analizujemy algorytmy obliczania całkowitych pierwiastków z dodatnich\nliczb całkowitych, które mają być poprawne względem następującej specyfikacji:\nSpecyfikacja:\nDane: dodatnia liczba całkowita n\nWynik: dodatnia liczba całkowita k - całkowity pierwiastek kwadratowy z liczby n\nPrzykład: dla n = 39 wynikiem jest k = 6\na) W poniższym algorytmie uzupełnij instrukcję w wierszu (3) tak, żeby otrzymany algorytm\nbył poprawny względem podanej wcześniej specyfikacji.\n(1) k  1;\n(2) dopóki (k+1)*(k+1) ≤ n wykonuj\n(3)\nk  ;\nPodaj, ile razy warunek w wierszu (2) powyższego algorytmu jest sprawdzany\nodpowiednio dla n = 32 i n = 1024.\nn\nliczba sprawdzeń warunku w wierszu 2\n32\n1024\nMiejsce na obliczenia:\nb) W poniższym algorytmie uzupełnij instrukcję w wierszu (5) tak, żeby otrzymany algorytm\nbył poprawny względem podanej wcześniej specyfikacji.\n(1) k  1; m  n;\n(2) dopóki (k+1)*(k+1) ≤ n wykonuj\n(3)\ns  (k+m) div 2;\n(4)\njeśli s*s ≤ n to\n(5)\nk \n(6)\nw przeciwnym przypadku\n(7)\nm  s\nUwaga: użyty operator div oznacza dzielenie całkowite, tzn. s jest największą liczbą\ncałkowitą nie większą od (k+m)/2.\nc) Podaj, ile razy warunek w wierszu (2) z algorytmu z punktu b) jest sprawdzany\nodpowiednio dla n = 32 i n = 1024.\nn\nliczba sprawdzeń warunku w wierszu 2\n32\n1024\nMiejsce na obliczenia:","answer":null,"answer_text":"0","solution":null,"image":"img/informatyka-2015-przykladowy-arkusz-cke-rozszerzona/zad-2.webp","solution_image":null,"topics":null,"page_from":3,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":null,"text_source":"ocr","source_label":"Informatyka · Arkusz przykładowy · 2015 (rozszerzona)","subject_label":"Informatyka","category_label":"Arkusz przykładowy","text_html":"

Zadanie 2. (0-6)
Całkowity pierwiastek kwadratowy
Niech
będzie dodatnią liczbą całkowitą. Całkowitym pierwiastkiem kwadratowym
z liczby ݊ nazywamy dodatnią liczbę całkowitą ݇ taką, że
כ݇
൑݊
i ሺ݇
൅1ሻכ ሺ݇
൅1ሻ൐݊
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.
(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
Miejsce na obliczenia:
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
Miejsce na obliczenia:

","answer_text_html":"

0

","solutions":[]}