Iteracja i pętle

Mamy za zadanie obliczyć sumę liczb parzystych z przedziału $\langle$a, b$\rangle$, gdzie a i b są liczbami całkowitymi. Zgodnie z poleceniem w tym przedziale będziemy rozważać tylko liczby całkowite. Jest to zadanie wymagające zastosowania iteracji, czyli wielokrotnego wykonania tych samych czynności.

Aby rozwiązać przedstawiony problem, należy dla każdej liczby z przedziału $\langle$a, b$\rangle$ sprawdzić, czy jest ona parzysta, a jeżeli tak, dodać ją do wartości zmiennej suma przechowującej sumę kolejnych liczb parzystych. Te czynności trzeba wykonać wielokrotnie, w zależności od tego, ile liczb znajduje się w przedziale $\langle$a, b$\rangle$. Algorytm przedstawimy w postaci schematu blokowego.

W schemacie zastosujemy pętlę, czyli będziemy wielokrotnie wykonywać te same zestawy instrukcji. W naszym przypadku pętla będzie wykonywać się, dopóki i będzie mniejsze lub równe b.

Zmiennej i przypisujemy wartość a, czyli wartość początku sprawdzanego przedziału. Przy każdym wykonaniu pętli do zmiennej i dodajemy liczbę 1, aż do momentu, kiedy zmienna i będzie większa od b (czyli liczby będącej końcem przedziału).

Oto schemat blokowy algorytmu obliczającego i wypisującego sumę liczb parzystych z przedziału $\langle$a, b$\rangle$.

Omówmy kolejne etapy algorytmu.

• Rozpoczynamy od wczytania dwóch wartości: a oraz b. Są to odpowiednio lewy i prawy koniec przedziału.

• Następnie inicjalizujemy zmienne i oraz suma. Pierwszej przypisujemy wartość a, drugiej zero. Zmienna i jest tzw. zmienną sterującą. Wykorzystujemy ją, aby określić, ile razy powinny być wykonane instrukcje zapisane wewnątrz pętli. Po wykonaniu całego bloku poleceń zwiększamy wartość i o 1. W rezultacie będziemy mogli zakończyć działanie pętli po dokładnie tylu cyklach, ile jest wymaganych do poprawnego rozwiązania problemu.

• Kolejnym etapem jest skonstruowanie warunku pętli. Instrukcje wewnątrz pętli będą wykonywać się, dopóki zmienna i będzie mniejsza lub równa b. Jeżeli okaże się, że ten warunek nie jest spełniony, możemy wypisać obliczoną sumę na ekranie i zakończyć program. Gdy zmienna i jest jednak mniejsza lub równa b, trzeba ponownie wykonać instrukcje wewnątrz pętli.

• Sprawdzamy parzystość liczby, czyli obliczamy resztę z dzielenia zmiennej i przez 2. Jeżeli reszta wynosi 0 (czyli w sytuacji, gdy liczba jest parzysta), dodajemy wartość zmiennej i do wartości zmiennej suma. Następnie dokonujemy inkrementacjiinkrementacjainkrementacji zmiennej i.

• Wracamy na początek pętli i ponownie sprawdzamy warunek. Przedstawione operacje będą wykonywane b - a + 1 razy. W momencie, gdy zmienna i osiągnie wartość  b + 1, warunek wykonania pętli nie będzie już spełniony. Na ekranie zostanie wyświetlona suma liczb parzystych; jest to ostania czynność opisana w algorytmie.

Spróbujmy zmodyfikować schemat blokowy. Warunek decydujący o wykonaniu kolejnego cyklu pętli lub jej zakończeniu umieścimy na końcu sekwencji poleceń:

Zwróćmy uwagę, że niezależnie od wartości zmiennej sterującej i oraz budowy warunku, operacje zapisane wewnątrz pętli zostaną wykonane co najmniej jeden raz. Wynika to ze zmiany miejsca pojawienia się warunku pętli („czy zmienna i jest mniejsza lub równa b?”). Wartość logiczna takiego wyrażenia jest obecnie sprawdzana dopiero po wykonaniu całego bloku instrukcji.

Gdybyśmy wykorzystali zmodyfikowany algorytm do rozwiązania zadania przedstawionego na wstępie, okazałby się on równie skuteczny jak poprzednia wersja. Zestaw instrukcji zapisanych wewnątrz pętli zostałby wykonany tyle samo razy – gdy zmienna i przyjęłaby wartość większą od b, na ekranie pojawiłaby się suma liczb parzystych, a pętla zostałaby przerwana. Poprawność obu sposobów rozwiązania wynika z założenia, że a $\leqslant$ b, czyli że w przedziale znajduje się co najmniej jedna liczba.

Należy jednak zaznaczyć, że w pewnych przypadkach lepiej jest zastosować algorytm zgodny z pierwszym schematem blokowym, zaś w innych – użyć wariantu drugiego.

Zoptymalizowana wersja algorytmu

Przeanalizujmy algorytm ponownie i spróbujmy rozwiązać go innym sposobem.

Zauważmy, że liczby parzyste zawsze różnią się o 2, więc możemy wyeliminować konieczność sprawdzania podzielności – wystarczy, że iterator będzie zmieniał się o 2. Tak zmodyfikowany algorytm prezentuje się następująco:

Zwróćmy uwagę na konieczność upewnienia się, że początek sprawdzanego przedziału jest liczbą parzystą – jeżeli tak nie jest, dodajemy do niego jeden. Możemy to zrobić, ponieważ nieparzysta liczba i tak nie zostałaby dodana do sumy.

Suma liczb parzystych jako suma ciągu arytmetycznego

Ponieważ kolejne liczby parzyste różnią się od siebie o 2, jeszcze skuteczniejszym rozwiązaniem byłoby skorzystanie ze wzoru na sumę elementów ciągu arytmetycznego. Spójrzmy na jego postać ogólną:

gdzie $n$ to liczba elementów, które chcemy zsumować, zaś $a_1, a_n$ to pierwszy oraz ostatni element tego ciągu w zadanym przedziale.

W jaki sposób wyznaczyć $n$? Po raz kolejny skorzystamy z faktu, że sumujemy tylko liczby parzyste. Możemy zmodyfikować wartość lewego i prawego krańca przedziału (czyli a i b) – w przypadku nieparzystego a zwiększyć o 1, a w przypadku nieparzystego b zmniejszyć o 1. Liczbę wszystkich liczb całkowitych w przedziale możemy zapisać jako b - a + 1. Jeżeli ta wartość byłaby parzysta, liczby parzyste stanowiłyby dokładnie połowę jej elementów – jednak zawsze będzie ona nieparzysta, gdyż jest to wynik odejmowania dwóch liczb parzystych zwiększony o 1. Ponieważ oba krańce przedziału to liczby parzyste, liczb parzystych w przedziale będzie więcej niż nieparzystych. Oznacza to, że liczb parzystych w przedziale będzie $\frac{b-a+2}{2}$.

To wszystko daje nam następujący wzór pozwalający obliczyć sumę liczb parzystych w zadanym przedziale:

Algorytm wykorzystujący ten wzór prezentuje się następująco:

Wyszukiwanie minimum w zbiorze liczb

Przeanalizujmy teraz nieco trudniejszy przykład. Załóżmy, że w zbiorze liczb podanych przez użytkownika chcemy wskazać liczbę najmniejszą.

Algorytm znajdowania minimum (lub maksimum) ma zastosowanie nie tylko w problemach matematycznych, ale i w codziennym życiu – w ten sposób szukamy, np. sklepu z najniższą ceną interesującego nas produktu.

Aby rozwiązać problem, trzeba zacząć od wskazania dowolnego elementu jako najmniejszego. Następnie porównujemy go z kolejnym. Jeśli drugi element okaże się mniejszy, to on zaczyna być traktowany jako minimum. Kolejnym krokiem jest porównanie elementu aktualnie najmniejszego z trzecim elementem – i tak aż do końca badanego ciągu.

W algorytmie użyjemy zmiennych n, min oraz x. Zmienna n będzie liczbą danych, a zmienna x będzie przechowywać kolejne wprowadzone przez użytkownika wartości. Zmienna min posłuży do przechowywania liczby, która w danym momencie jest najmniejsza.

Słownik