Iteracja i pętle

Mamy za zadanie obliczyć sumę liczb parzystych z przedziału a, b, gdzie ab 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.

Problem 1

Przygotuj i omów algorytm, który pobierze od użytkownika dwie liczby całkowite a oraz b, oznaczające początek i koniec przedziału a, b, a następnie obliczy sumę liczb parzystych z zadanego zakresu.

Specyfikacja problemu:

Dane:

  • a, b – liczby całkowite; kolejno: lewy i prawy kraniec przedziału,  b

Wynik:

Program wypisuje sumę liczb parzystych z przedziału a, b.

Aby rozwiązać przedstawiony problem, należy dla każdej liczby z przedziału a, b 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 a, b. 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 a, b.

R1K0TcYmaZPGJ1
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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ń:

R1RzXrDR60qwa1
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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

Problem 2

Przygotuj i omów algorytm, który pobierze od użytkownika dwie liczby całkowite a oraz b, oznaczające początek i koniec przedziału a, b, a następnie obliczy sumę liczb parzystych z zadanego zakresu. Zmodyfikuj przedstawiony wcześniej algorytm tak, aby wyeliminować konieczność każdorazowego sprawdzania parzystości liczby.

Specyfikacja problemu:

Dane:

  • a, b – liczby całkowite; kolejno: lewy i prawy kraniec przedziału,  b

Wynik:

Program wypisuje sumę liczb parzystych z przedziału a, b.

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:

R1DXYpqJnT7gz1
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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

Problem 3

Przygotuj i omów algorytm, który pobierze od użytkownika dwie liczby całkowite a oraz b, oznaczające początek i koniec przedziału a, b, a następnie obliczy sumę liczb parzystych z zadanego zakresu. W swoim rozwiązaniu skorzystaj ze wzoru na sumę ciągu arytmetycznego.

Specyfikacja problemu:

Dane:

  • a, b – liczby całkowite; kolejno: lewy i prawy kraniec przedziału,  b

Wynik:

Program wypisuje sumę liczb parzystych z przedziału a, b.

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 to liczba elementów, które chcemy zsumować, zaś  to pierwszy oraz ostatni element tego ciągu w zadanym przedziale.

W jaki sposób wyznaczyć ? Po raz kolejny skorzystamy z faktu, że sumujemy tylko liczby parzyste. Możemy zmodyfikować wartość lewego i prawego krańca przedziału (czyli ab) – 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 .

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:

RbJu9t8TJKWUn1
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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ą.

Problem 4

Przygotuj i omów algorytm, który pobierze od użytkownika n liczb i wyłoni spośród nich najmniejszą.

Specyfikacja problemu:

Dane:

  • n – liczba naturalna; liczba elementów wprowadzanych przez użytkownika; 

  • xIndeks dolny 1, xIndeks dolny 2, …, xIndeks dolny n – liczby całkowite podawane przez użytkownika

Wynik:

Program wypisuje najmniejszą spośród liczb podanych przez użytkownika.

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.

RHC1KvGSxHl721

Słownik

dekrementacja
dekrementacja

zmniejszanie wartości zmiennej o jeden

inkrementacja
inkrementacja

zwiększenie wartości zmiennej o jeden

zmienna sterująca pętlą (iterator)
zmienna sterująca pętlą (iterator)

zmienna tworzona i wykorzystywana do sterowania wykonaniem instrukcji iteracyjnej; zazwyczaj to zmienna typu porządkowego, np. liczba naturalna, całkowita lub wartość logiczna, aczkolwiek w niektórych językach, np. C++ i Java, typ zmiennej sterującej nie jest ograniczony