Matura próbna z informatyki 2014/2015 - czy takie dwie odpowiedzi są możliwe?

0

Witam, chodzi mi o algorytm w zad. 2. w podpunkcie b) w tym dokumencie:
http://www.cke.edu.pl/images/_EGZAMIN_MATURALNY_OD_2015/Przykladowe_arkusze/2015/informatka_PR/informatyka_PR_czI_A1.pdf

Niech n będzie dodatnią liczbą całkowitą. Całkowitym pierwiastkiem kwadratowym
z liczby n nazywamy dodatnią liczbę całkowitą ݇k taką, że kk<=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

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.

W odpowiedziach jest k=s;
Zastanawiam się, czy nie mogłoby tam być k=k+1;?

Tutaj napisany przeze mnie kod w C++:
http://goo.gl/YWkO4k

#include <iostream>

using namespace std;

int main()
{
   cout << "Hello World" << endl; 
   int k,m,n,s,p;
   k=1;
   cin >> n;
   m=n;
   p=0;
   while ((k+1)*(k+1)<=n)
   {
       p++;
       s=(k+m)/2;
       if (s*s<=n)
       {
           k=k+1;
       }
       else
       {
           m=s;
       }
   }
   p++;
   cout << k << endl << p << endl;
   
   return 0;
}

Gdzie p oznacza ile razy warunek while (dopóki) był sprawdzany, a reszta zmiennych wg zadania.

Oba kody (ten z k=s; oraz ten z k=k+1;) wydają się dawać te same wyniki (zmiennej k).

Pozdrawiam,
Defozo

2

Nie mogło by tak być, inaczej po co ten cały "algorytm"? Mógłbyś go zapisać po prostu jako:

k=1;
while ((k+1)*(k+1)<=n)
	k++;

Wywołaj sobie swój kod dla wiekszych liczb to zobaczysz różnicę. Twoj algorytm ma złożoność O(n^0.5) a prawidłowa odpowiedź O(log2 n)
http://pl.wikipedia.org/wiki/Wyszukiwanie_binarne

1 użytkowników online, w tym zalogowanych: 0, gości: 1