Darmowe konto pozwoli wrócić do niego później.
Polecenie
Zadanie 2.2. (0–4)
Zaproponuj algorytm, który dla całkowitego n ≥ 2 wyznaczy wszystkie triady c1, c2 i ck, gdzie 1≤k≤n (k może być równe 1 lub 2), w zadanym ciągu liczb c1,c2,…,cn.
Swój algorytm zapisz zgodnie z poniższą specyfikacją.
Specyfikacja:
Dane: n – liczba elementów ciągu liczb, n ≥ 2
Darmowe konto pozwoli wrócić do niego później.
Wynik: liczba wszystkich triad c1, c2 i ck w ciągu c1,c2,…,cn, 1 ≤ k ≤ n
Algorytm:
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.
Przykładowe rozwiązania:
Algorytm za 4 punkty:
1) k ← 1; licznik ← 0
2) min ← cj – ci; max ← cj + ci
3) dopóki ck < max oraz k<n+1
a) jeśli ck > min: licznik ← licznik + 1
b) k ← k+1
4) Zwróć wartość licznik jako wynik
Algorytm za 3 punkty (przeglądany jest cały zbiór C, sprawdzany warunek trójkąta):
1) licznik ← 0
2) dla kolejnych k ← 1, 2,...n
a) jeśli (cj-ci<ck oraz cj+ci>ck) licznik ← licznik+1;
3) zwróć wartość licznik jako wynik
Algorytm za 4 punkty:
1) k ← i+1;
2) jeśli ci + ck > cj to
a) m ← k+1
b) dopóki ci + cm > cj oraz m>0: m← m – 1
c) pocz ← m
3) wpp
a) m ← j – 1
b) dopóki ci+ cm > cj: m ← m – 1
poprawne wartości początkowe.
poprawna organizacja pętli.
poprawne wyznaczanie końcowej wartości.
rozwiązanie, którego czas działania jest mniejszy niż liniowy.
4) kon ← j
5) dopóki ci+cj>ckon oraz kon ≤n: kon ← kon + 1
6) zwróć wartość kon – pocz
Algorytm za 4 punkty (nie wykonujemy niepotrzebnych porównań):
1) min ← cj-ci; max ← cj+ci; k ← 1
2) while (ck <= min) k ← k+1;
3) pocz ←k;
4) k ← j;
5) while (ck>=max and k>pocz) k ← k-1;
6) koniec ← k
7) zwróć wartość koniec-pocz + 1