Darmowe konto pozwoli wrócić do niego później.
Polecenie
Liczbę całkowitą nazwiemy kwadratową, jeżeli da się ją przedstawić w postaci a*b² + c*d², gdzie a, b, c, d są dodatnimi liczbami całkowitymi oraz b i d są większe od 1.
Załóżmy, że dla danej dodatniej liczby całkowitej n z pomocą procedury Sitko(n) obliczymy tablicę Czyjest[1..n].
Wykorzystując tablicę Czyjest, zapisz (w postaci pseudokodu, listy kroków lub wybranego języka programowania) algorytm, który sprawdza, czy dana liczba całkowita k, 1 ≤ k ≤ n jest liczbą kwadratową. Twój algorytm powinien być zgodny z następującą specyfikacją:
Specyfikacja:
Dane:
Darmowe konto pozwoli wrócić do niego później.
Czyjest [1..n] – tablica długości n obliczona w wyniku działania procedury Sitko(n)
k – liczba całkowita, 1 ≤ k ≤ n
Wynik:
– prawda, gdy k jest liczbą kwadratową, fałsz w przeciwnym przypadku
Algorytm I:
for (int i=1; i<=n; i++)
for (int j=i; j<=n; j++)
if (Czyjest[i] && Czyjest[j] && i+j==k)
return true
return false
Algorytm II:
int i=1;
int j=n;
while (i<j)
if (!Czyjest[i] || i+j<k)
i += 1
else
if (!Czyjest[j] || i+j>k)
j -= 1
else
return true;
return false;
poprawna organizacja pętli.
poprawny warunek sumy kwadratowej (Algorytm I) lub poprawny warunek (Algorytm II).
pozostała część algorytmu.
Akceptowalne są różne notacje (pseudokod, lista kroków, język programowania). Algorytm powinien sprawdzać, czy k da się przedstawić jako suma dwóch liczb kwadratowych z tablicy Czyjest.
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.