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.
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
|
1 | true | 2 | 2
|
2 | true | 4 | 3
|
3 | true | 8 | 4
|
4 | true | 16 | 5
|
5 | true | 32 | -
|
6 | false (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.
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.
 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.
|