Zadanie 1.3, matura czerwiec 2017, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 1. Sitko
Rozważmy następującą procedurę, której parametrem jest dodatnia liczba całkowita n.
```
Procedura Sitko(n)
dla i=1,2,…,n wykonuj
Czyjest[i] ← fałsz
j ← 1
dopóki j*j < n wykonuj
j ← j+1
dla i = 2,3,…,j wykonuj
kw ← i * i
poz ← kw
dopóki poz ≤ n
(*) Czyjest[poz] ← prawda
poz ← poz + kw
```
Polecenie
4 punktyLiczbę całkowitą nazwiemy kwadratową, jeżeli da się ją przedstawić w postaci a ⋅ b2 + c ⋅ d2, 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:
n – dodatnia liczba całkowita
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:
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
Przykładowe algorytmy:
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;
```
Schemat punktowania
Algorytm I:
za poprawną organizację pętli.
za poprawny warunek sumy kwadratowej.
Algorytm II:
za poprawny warunek.
Razem: 4 pkt.
Komentarz. 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.