Pętle (iteracje i rekurencja).docx

Pętle (iteracje i rekurencja)

Pętla for … to… do

Gdyby zdarzyło Ci się kiedyś zasnąć w autobusie komunikacji miejskiej -mógłbyś się zaniepokoić. Nie byłby to jednak wielki problem, gdyby okazało się, że masz wystarczająco dużo czasu, nie złapał Cię kontroler biletów i co najważniejsze minęło akurat tyle czasu, że znowu zbliżasz się do właściwego przystanku.

Ten dość abstrakcyjny przykład pokazuje działanie pętli. Tak jak autobus jeździ określoną trasą przez wszystkie przystanki, tak pętla zaczyna się w określonym miejscu i wykonuje po kolei wszystkie zaplanowane instrukcje. Tak samo jak autobus pokonuje całą trasę wielokrotnie, tak samo pętla powraca do początku wielokrotnie. Gdy wykonana zostanie ostatnia instrukcja zaplanowana w tym okresie pętli, program momentalnie przeskakuje do jej początku.

Pętla wykonuje wielokrotnie jakąś operację. Przypuśćmy że chcesz aby Twój program wypisał liczby od 1 do 1000. Co zrobisz? Czy będzie Ci się chciało pisać:

begin
 WriteLn(‘1’);
 WriteLn(‘2’);
 WriteLn(‘3’);
 WriteLn(‘4’);
 {...}
 WriteLn(‘1000’);
end.

Zajęłoby to na pewno dużo czasu. Nie tylko czasu, ale nie spełniałoby wszystkich oczekiwań programisty. Np. gdy chcesz aby program wykonał jakąś czynność określoną ilość razy, którą poda użytkownik nie byłbyś w stanie określić kiedy ma nastąpić koniec.

Jednym z prostszych rozwiązań jest wykonywanie kodu aż do momentu spełnienia przez program warunku.

label petla;
var i : Integer;
begin
 i := 0;
 petla:
   Inc(i); {Inc czyli i:=i+1}
   WriteLn(i);
 if i<1000 then goto petla;
end.

Mniej więcej tak właśnie wyglądają pętle. Na szczęście nie trzeba pisać aż tyle, żeby jakąś oprogramować. Powyższy przykład pokazuje jak samemu można napisać pętlę. Kod pętli zazwyczaj polega właśnie na takiej idei opisanej poniżej:

Początek pętli:
Wykonaj jakieś zadanie (np. wyświetl jakiś napis)
Zwiększ zmienną i o 1 (i := i + 1)
Sprawdź czy i jest mniejsze niż maksymalna wartość (np. 1000)
Jeśli mniejsze skocz z powrotem do początku pętli
Jeśli nie, wykonuj kod dalej...

Ideą większości pętli jest możliwość sprawdzenia, który raz się ona powtarza. Zazwyczaj pętla udostępnia pewną zmienną, która za każdym razem jest automatycznie zwiększana o 1 albo zmniejszana. W programie będzie Ci potrzebne częste korzystanie z tej zmiennej.

Pętle pozwalają rozwiązać problem wykonania dowolnego zadania z dowolną liczbą powtórzeń. Dzięki nim wpisujesz tylko liczbę powtórzeń i w taki sposób układasz instrukcje aby wiedziały, który raz się wykonują. Zobacz przykład, który całkowicie poradzi sobie z problemem liczenia od 1 do 1000.

var i:Integer;
begin
for i:=1 to 1000 do
  WriteLn(i);
end.

…I wszystko. Całość zajmuje tylko 5 lini. Wewnątrz pętli masz dostęp do zmiennej „i”, która po kolei przyjmuje wartości od 1 do 1000. Po zwiększeniu wartości zmiennej „i” pętla ta wykonuje instrukcję WriteLn(i), a więc po kolei WriteLn(1), WriteLn(2), WriteLn(3)… Oczywiście jeśli chcesz w pętli użyć więcej instrukcji niż tylko WriteLn musisz poinformować o tym komputer, bo niestety sam się nie domyśli. Możesz użyć BEGIN i END;

var i:Integer;
begin
for i:=1 to 1000 do
 begin
  WriteLn(i);
  {Jeszcze inne instrukcje}
 end;
end.

Pętla for … downto… do

Gdybyś chciał, aby pętla odliczała z góry w dół, zamiast słowa TO musisz wpisać DOWNTO. Pierwsza liczba musi być wtedy większa od drugiej.

var i:Integer;
begin
for i:=1000 downto 1 do
 begin
  WriteLn(i);
  {Jeszcze inne instrukcje}
 end;
end.

Teraz i będzie przyjmowało kolejno wartości: 1000, 999, 998, 997.... 1. Oczywiście zmienna może mieć dowolną nazwę. Tak się przyjęło w programowaniu, że najczęściej stosuje się "i" oraz "j".

Zagnieżdżanie pętli

Pętle można dowolnie zagnieżdżać. Znaczy to, że może istnieć pętla w pętli. Głębokość zagnieżdżenia jest nieograniczona. Zagnieżdżenia pętli są bardzo często wykorzystywane. Uwaga, wewnątrz pętli nie wolno używać tej samej nazwy zmiennej do pętli wewnętrznej. W ten sposób mógłbyś zawiesić program.

Przykład pokaże w jaki sposób robi się zagnieżdżenia.

var i, j:Integer;
begin
 for i:=1 to 10 do
 begin
   Write(i : 3);
   for j:=1 to 10 do
    Write(j : 3);
   WriteLn;
 end;
end.

Program wykonuje pierwszą pętle (dla zmiennej i) 10 razy. W pętli siedzi druga pętla (ze zmienną j), która za każdym razem jest wykonywana również 10 razy. Skutek będzie taki, że druga pętla od początku do końca wykona się 10 razy. Czyli dla zmiennej i = 1 j będzie przyjmowało wartości 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 i od początku dla i=2 znowu j= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3... i aż do i = 10 i j = 10

Wynik na ekranie będzie wyglądał tak:

1  1  2  3  4  5  6  7  8  9 10
2  1  2  3  4  5  6  7  8  9 10
3 ......
.
.
.
10 1  2  3  4  5  6  7  8  9 10

Warto zwrócić uwagę na to, że za pętlą i:=1 to 10 do jest begin! Dlaczego? Gdyby go nie było 10 razy wykonałaby się tylko następna instrukcja czyli Write(i : 3). Czyli po prostu program zrobiłby linię z napisem 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a potem wykonałby drugą pętlę tylko raz, czyli w szeregu wypisałby 1, 2, 3, 4, 5.. 10.

Jeśli zapomnisz o begin wyjdzie coś takiego

1  2  3  4  5  6  7  8  9 10
1  2  3  4  5  6  7  8  9 10

Trzeba pamiętać, że komputer nie domyśla się po wcięciach kodu, które bloki instrukcji ma wykonać w danej pętli. Te instrukcje muszą być razem umieszczone wewnątrz bloku: begin ... end;

Teraz bez problemu napiszemy tabliczkę mnożenia. Zmieni się tylko tyle, że zamiast wyświetlać zmienną i albo j będziemy wyświetlali i * j.

program tabliczka;
var i, j:Integer;
begin
 for i:=1 to 10 do
 begin
   for j:=1 to 10 do
     Write(j * i : 3);
   WriteLn;
 end;
end.

Najczęściej w szkołach nauczyciele zadają problem rysowania choinki z gwiazdek. Chodzi o to by uzyskać rysunek w trybie tekstowym.

Ile wierszy? 5

   *
  ***
 *****
*******
*********

Choinka z gwiazdek z warunkiem if

program choinka;
var i, j, w : Integer;
begin
 Write('Ile wierszy? ');
 ReadLn(w);

 for i:=1 to w do
 begin
   for j:=1 to w + i – 1 do
   if j >= w – (i – 1) then
     Write('*')
   else
     Write(' ');

   WriteLn;
 end;
end.

Choinka z gwiazdek z samymi pętlami

program choinka;
var i, j, w : Integer;
begin
 Write('Ile wierszy? ');
 ReadLn(w);

 for i:=1 to w do
 begin
   for j:=1 to w – i do Write(' ');
   for j:=1 to i * 2 - 1 do Write('*');
   WriteLn;
 end;
end.

Takich sposóbów rozwiązania może być bardzo wiele. Chodzi o to jak matematycznie zapisać rozwiązanie zadania przy pomocy zmiennych. Jak samemu znajdować takie matematyczne rozwiązania?

Najpierw tworzymy pętlę odpowiedzialną za rysowanie kolejnych linii choinki. Zaczynamy od czubka, kończymy na dole. Czyli ta pętla musi być od 1 do tylu, ile użytkownik wpisał wierszy. Przyjmijmy, że od 1 do "w", gdzie w jest zmienną, wczytaną z klawiatury. Po każdorazowym narysowaniu linii, trzeba przenieść kursor do linii następnej za pomocą WriteLn. Ale jeszcze przed przejściem do kolejnej linii trzeba przecież narysować igły w poziomie.

Z tego wynika, że wewnątrz tej pętli musi być jeszcze inna, która narysuje igły choinki. Jest to o tyle utrudnienie, że dla choinki, która ma 5 wierszy najpierw trzeba narysować 4 spacje i jedną gwiazdkę, potem 3 spacje i 3 gwiazdki, potem 2 spacje i 5 gwiazdek... itd.

Łatwo zauważyć, że liczba spacji z każdym wierszem maleje o 1. Na samej górze będzie tyle spacji co wierszy choinki – 1. Znowu liczba gwiazdek rośnie od 1, zwiększając się w każdym rzędzie o 2 gwiazdki. Wynika z tego, że:

Dla choinki o wysokości zapisanej w zmiennej "w"

W pętli od 1 do w rysujemy:
 1 rząd: w - 1 spacji, 1 gwiazdka
 2 rząd: w – 2 spacji, 3 gwiazdki
 3 rząd: w – 3 spacji, 5 gwiazdek
"w"rząd: w – w spacji, w * 2 – 1 gwiazdek

Czyli w jednej pętli muszą być dwie nowe pętle, z których jedna rysuje spacje, a druga gwiazdki. Teraz skąd będzie wiadomo, że gdy jesteśmy w pierwszym rzędzie, mamy od w odjąć 1 i narysować jedną gwiazdkę, a w drugim rzędzie od w odjąć 2 i narysować 3 gwiazdki?

Właśnie do tego służy zmienna skojarzona z pętlą! Pisaliśmy pętlę dla zmiennej i oraz j. Czyli w pierwszym rzędzie i będzie równe 1, w drugim i=2, w trzecim i=3, itd. To nam wystarczy.

Trzeba więc napisać pętlę ze spacjami od 1 do w – i, a pętlę z gwiazdkami od 1 do i * 2 - 1.

Nie sposób opisać wszystkich zadań, jakie wymyślą nauczyciele i nawet nie w tym rzecz. Każde zadanie, które dostaniesz, musisz po prostu sobie rozpisać, przemyśleć i zaprogramować.

Pętla REPEAT … UNTIL ….

W sytuacjach, gdy chcesz aby program wykonywał się aż do momentu spełnienia jakiegoś warunku pomocą jest pętla repeat until. Jest wyjątkowa pod tym względem, że wyk...