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

Odpowiedz Nowy wątek
2014-12-30 17:16
0

Witam, chodzi mi o algorytm w zad. 2. w podpunkcie b) w tym dokumencie:
http://www.cke.edu.pl/images/[...]_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

edytowany 2x, ostatnio: Defozoo, 2014-12-30 17:35

Pozostało 580 znaków

2014-12-30 18:03

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

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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