Zadanie 1.3, matura czerwiec 2017, informatyka rozszerzona

4 pktotwartetrudne (szac.)Czerwiec 2017

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 punkty

Liczbę 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.

Wypróbuj za darmo

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:

1 pkt

za poprawną organizację pętli.

2 pkt

za poprawny warunek sumy kwadratowej.

Algorytm II:

2 pkt

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.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.