następny punkt »

1. Pojęcie pętli iteracyjnej

Często instrukcję lub grupę instrukcji trzeba wykonać wielokrotnie, powtarzając je znowu i znowu, aż do chwili, gdy zostanie spełniony jakiś warunek (w szczególności np. dotyczący liczby powtórzeń). Każde powtórzenie instrukcji lub ich grupy nazywa się iteracją, a językowa konstrukcja pozwalająca na ich powtarzanie - pętlą iteracyjną.

Wyobraźmy sobie np., że trzeba policzyć sumę i iloczyn kolejnych dodatnich  liczb całkowitych. Nie znając pojęcia pętli iteracyjnej musielibyśmy zapisać to w następujący sposob:

int suma = 0;
int iloczyn = 1;
int i = 1;
suma += i;
iloczyn *= i;
i++;
suma += i;
iloczyn *= i;
i++;
suma += i;
iloczyn *=i;
...

Widzimy tu wielokrotnie powtarzające się fragmenty kodu. Oczywiście powinniśmy je umieścić w pętli.

Przy tym jednak istotne jest, aby dobrze sformułować warunki zakończenia działania pętli. Przecież nie możemy próbować sumować i mnożyć wszystkich liczb całkowitych, bo nasz program nie zakończyłby nigdy działania.
Ogólnie, warunki zakończenia działania pętli można podać w dwojaki sposób:

  • jako liczbę iteracji do wykonania (liczbę powtórzeń instrukcji umieszczonych w pętli) - np. zsumowac i pomnożyć 20 pierwszych dodatnich liczb całkowitych
  • jako jakiś inny warunek - np. sumować i mnożyć kolejne liczby aż do chwili, gdy ich iloczyn stanie się równy lub większy od 100000.

W instrukcjach sterujących, które wprowadzają pętle, ze względu na lepszą czytelność programu  podaje się warunki kontynuacji , a nie zakończenia pętli. Wykonanie pętli można jednak przerwać w jej środku - i wtedy warunek, który sprawdzimy, by przerwać pętlę - będzie warunkiem zakończenia działania pętli. Na to rozróżnienie warto początkowo zwracać baczną uwagę,

Na samym początku lepszemu zrozumieniu działania pętli sprzyja obrazowanie ich za pomocą schematów blokowych. Działanie bardziej skomplikowanych pętli dodatkowo należy prześledzić - iteracja po iteracji (oczywiście nie wszystkie, np. kilka poczatkowych iteracji i kilka końcowych).

Zobaczmy to na przykładzie  podnoszena do potęgi podanej liczby całkowitej.
Naszym pierwszym zadaniem jest policzenie n-tej potęgi (n>=0) podanej liczby całkowitej a.

Pętle o znanej liczbie iteracji zapisujemy zwykle za pomoca instrukcji for (...)

W naturalny sposób możemy zapisać to jako n-krotne mnożenie tej liczby przez samą siebie: a*a*a... Będziemy mieli n - iteracji. W każdej i-ej iteracji (1<= i <=n) zmienna wynik będzie miała wartość a w potędze i.

Sposób działania takiej pętli iteracyjnej ilustruje poniższy schemat blokowy.

Rys

Możemy sprawdzić działanie pętli "z kartką i ołówkiem" dla jakiegoś zestawu danych wejściowych, np. a = 2 i n = 5.

Iteracja
Wartość
zmiennej i
Wartość warunku
kontynuacji pętli 
Wartość zmiennej wynik
1
1true2
2
2true4
3
3true8
4
4true16
5
5true32
-
6false (pętla kończy działanie)32

Zwróćmy uwagę, że w tym algorytmie - po zakończeniu pętli - zmienna i będzie miała wartość o jeden większą od liczby wykonanych iteracji (chociaż traktowaliśmy ją jako licznik iteracji, to nie możemy powiedzieć, że pętla wykonała się i-razy).
Czy jesteśmy pewni poprawności tego algorytmu? Czy dobrze dobraliśmy wartość początkową i oraz rodzaj warunku kontynuacji?
Nie wystarczy rozpatrzeć tylko jednego, wybranego przebiegu obliczeń. Warto przyjrzeć się także  warunkom brzegowym zadania. Mamy podnosić dowolną liczbę całkowitą do potęgi całkowitej n >= 0. Co się zatem stanie, gdy n = 0? Pętla nie wykona się ani razu (bo i = 1 jest mniejsze od n = 0), ale wynik będzie poprawny (bo zmienną wynik zainicjowaliśmy wartością 1).
Ten sam efekt (poprawnego działania) można uzyskać gdyby zamiast i = 1 napisać i = 0, a zamiast i <= n napisać i < n. (oczywiście zwróćmy uwagę, że algorytm jest poprawny tylko dla n >= 0).


Częstym błędem przy konstrukcji pętli iteracyjnych jest wykonywanie iteracji o jeden raz za dużo lub jeden raz za mało


Ale nie możemy oczywiście całkiem dowolnie, na wyczucie stosować znaku < zamiast <= lub inicjowac zmiennej i zerem lub jedynką. Nie ma tu złotych reguł - dobór zależy od starannej analizy poprawności algorytmu. W przypadku tak prostego zadania o jakim była mowa przed chwilą nie ma tu większych problemów, ale w bardziej złożonych przypadkach właściwy dobór liczby iteracji może sprawiać kłopoty.


Rozważmy teraz inne zadanie. Mamy oto określić do jakiej parzystej potęgi n (n>=0) należy podnieść podaną liczbę całkowitą a (a > 1), aby osiągnąć wynik co najmniej równy  zadanej wielkości (którą określimy jako wartość całkowitą cel).


Przed lekturą dalszego tekstu proszę spróbować samodzielnie zbudować schemat blokowy rozwiązania tego zadania.


Rozpatrujemy parzyste potęgi n liczby a. Niech w oznacza wynik potęgowania.
Dla n = 2 w = a*a.
Dla n = 4 w = a*a*a*a.
Dla n = 6 w = a*a*a*a*a*a
Itd.
A zatem jeśli  na początku w = 1, to następnie w pętli możemy uzyskiwać kolejne potęgi za pomocą wyrażenia:
w = w *a * a

Nie wiemy jednak z góry ile razy powinna wykonać się pętla. Naszym celem jest przecież określenie liczby n, a nie podniesienie a do znanej potęgi n.
Warunkiem kontynuacji pętli powinno być porównanie uzyskiwanych wartości w z zadaną liczbą cel.
Powiedziano: "osiągnąć wynik co najmniej równy  zadanej wielkości cel". A to oznacza, że pętla ma być kontynuowana dopóki w jest mniejsze od cel. Proszę zwrócić uwagę: nie równe lub mniejsze, ale mniejsze!
W samej pętli musimy nie tylko wyliczać bieżący wynik potęgowania, ale również zwiększać n (i to zawsze o 2, bo potęgi mają być parzyste).
A jaką początkową wartość powinno mieć n?
Oczywiście 0, bowiem takie są warunki zadania (cel - jest dowolną liczbą całkowitą,  n zaś może być >=0). Zatem np. dla cel <= 1, właściwą odpowiedzią jest n = 0 (bo zmienna w początkowo rowna jest 1, co jest większe lub równe wartości zmiennej cel,  pętla nie wykona się ani razu, ale dowolne a podniesione do potęgi 0 jest równe 1).

Pokazuje to następujący schemat blokowy.

Rys

Warunkowe pętle iteracyjne zapisujemy zwykle za pomocą instrukcji while

Mamy tu zatem pętlę, która kończy działanie nie na skutek wyczerpania limitu iteracji, ale ze względu na niespełnienie warunku, który z liczbą iteracji nie ma nic wspólnego. Takie pętle możemy nazwać warunkowymi pętlami iteracyjnymi.

Bardzo ważną sprawą przy programowaniu pętli jest zagwarantowanie zakończenia ich działania. Często - przy niezbyt starannej analizie warunków zadania, przy jakichś konkretnych wartościach danych, możemy uzyskać pętle działające w nieskończoność.

Np. prawidłowe działanie obu omówionych wyżej algorytmów zależy od konkretnej reprezentacji liczb w języku. Jeżeli wyniki potęgowania będziemy przedstawiać jako liczby typu int, to pierwszy algorytm (przy dużych a i n ) nie da prawidłowych wyników, a drugi może się zapętlić (tzn, petla będzie wykonywana w nieskończoność). Wynika to z tego, że w którymś momecie (przy dużych a i n) wynik potęgowania nie będzie mieścił się w obszarze pamięci przeznaczonym do przechowywania liczb typu int.

Problem
Zauważmy też, że formułując drugie zadanie (znaleźć parzyste nieujemne n, takie, że a podniesione do potęgi n jest co najmniej równe cel ) podano warunek a>1.



Co się stanie, gdy uchylimy ten warunek i powiemy, że a może być dowolną liczbą całkowitą? Czy dla każdego a  (przy dowolnym całkowitym cel) pętla będzie miała zagwarantowane zakończenia?
Proszę sprobować samodzielnie rozwiązać tę zagadkę, a później spojrzeć na rozwiązanie.


 następny punkt »