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 = 6W 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 ss ≤ 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