Dana jest tablica n-elementowa o nazwie t[n] Zadaniem algorytmu zapisanego w postaci kroków jest wypisanie sumy
| K1: i = 0; wynik = 0; K2: Dopóki i < n wykonuj K3 .. K4 K3: wynik ← wynik + t[i] K4: i ← i + 2 K5: wypisz wynik |
A. n-elementów tablicy.
B. sumy tych elementów tablicy, których wartości są nieparzyste.
C. co drugiego elementu tablicy.
D. sumy wszystkich elementów tablicy.
Pytanie z egzaminu CKE, styczeń 2016 (arkusz E.14-X-16.01).
Algorytm sumuje co drugi element tablicy, dokładniej elementy o indeksach 0, 2, 4, 6 itd., dopóki indeks i jest mniejszy od n. Na początku ustawiane jest i = 0 oraz wynik = 0. W każdej iteracji do zmiennej wynik dodawana jest wartość t[i], a potem i zwiększa się o 2. To właśnie krok i ← i + 2 jest tutaj najważniejszy, bo powoduje przeskakiwanie jednego elementu tablicy. Dla przykładu, jeśli tablica ma wartości t = [5, 10, 7, 3, 2], algorytm doda 5 + 7 + 2, czyli elementy t[0], t[2] i t[4]. Moim zdaniem warto zawsze śledzić zmienną sterującą pętlą na małym przykładzie, bo wtedy takie zadania robią się dużo prostsze. W praktycznym programowaniu, np. w JavaScript albo PHP, podobny schemat stosuje się przy przetwarzaniu wybranych pozycji tablicy, filtrowaniu danych według indeksu albo analizie próbek z większego zbioru. Dobra praktyka to pilnowanie warunku i < n, bo chroni on przed wyjściem poza zakres tablicy, co w wielu językach prowadzi do błędów albo niepoprawnych wyników.
W tym algorytmie kluczowe jest odróżnienie indeksu elementu od jego wartości. Zmienna i nie przechowuje wartości z tablicy, tylko numer pozycji, z której aktualnie pobierany jest element. Startuje od 0, więc pierwszy użyty element to t[0]. Następnie po każdym dodaniu wykonywane jest i ← i + 2, dlatego pętla nie przechodzi przez wszystkie indeksy po kolei, tylko przez 0, 2, 4, 6 i tak dalej. Z tego powodu nie można uznać, że algorytm liczy sumę wszystkich elementów tablicy. Gdyby tak było, zwiększanie indeksu wyglądałoby raczej jak i ← i + 1. Nie chodzi też o n-elementów tablicy, bo n oznacza rozmiar tablicy i służy tylko do określenia granicy pętli, a nie jest automatycznie liczone ani wypisywane jako wynik. Częsty błąd polega też na pomyleniu parzystości indeksu z nieparzystością wartości. Algorytm nigdzie nie sprawdza, czy t[i] jest nieparzyste, nie ma tam warunku typu t[i] mod 2 != 0. Dodawane są elementy leżące co drugą pozycję, niezależnie od tego, czy ich wartości są parzyste, nieparzyste, dodatnie czy ujemne. Z mojego doświadczenia najbezpieczniej jest rozpisać sobie kilka obiegów pętli: przed pierwszym obiegiem i = 0, potem i = 2, potem i = 4. Od razu widać, że algorytm omija indeksy 1, 3, 5. Taki sposób analizy jest bardzo przydatny przy czytaniu pseudokodu, debugowaniu pętli oraz przy pracy z tablicami w normalnym kodzie programu.