Pętle (iteracje i rekurencja)

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 wykonuje wszystkie instrukcje znajdujące się pomiędzy nią, więc nie trzeba używać poleceń BEGIN i END.

Znaczy: "Powtarzaj aż do momentu, gdy podany na końcu warunek będzie spełniony"

uses Crt;
begin
 repeat
 until KeyPressed;
end.

Powyższy przykład pokazuje w jaki sposób można zbudować program czekający na naciśnięcie dowolnego klawisza. Wykorzystuje on funkcję KeyPressed z modulu Crt, trzeba więc poinformować komputer że będziemy korzystali z Crt;

RunTime Error 200

Moduł Crt, napisany dla Pascala nie przewidywał takich szybkich komputerów jakie mamy dzisiaj. Przy uruchamianiu programu, może powodować błąd: "RunTime Error 200 Division by 0" jeśli nie został zainstalowany Patch do Turbo Pascala. Można go bez problemu ściągnąć z działu download tej strony internetowej.

Jeśli nie masz Patch'a a koniecznie chcesz napisać skrypt czekający na naciśnięcie dowolnego klawisza, możesz użyć bez modułu Crt:

begin
 repeat
 until Port[$60]<128;
end.

Port[$60] wskazuje na aktualny stan klawiatury. Jeśli Port[$60]=1 jest wciśnięty Escape, jeśli 2 F1 i tak po kolei cała klawiatura.

Pętla While ... do

Pętla While... do, z zastosowania, nieco przypomina repeat... until... Różni się miejscem i sposobem sprawdzania warunku. Znaczy "Dopóki warunek jest spełniony wykonuj". Różni się więc od repeat sposobem sprawdzania. W repeat gdy warunek był spełniony pętla kończyła się, tu gdy warunek jest NIE SPEŁNIONY pętla się kończy.

Poza tym w repeat zadanie z pętli wykonywało się chociaż raz, we while, gdy warunek jest nie spełniony, nie wykona się ani razu. Wynika to, z tego, że while sprawdza warunek przed pętlą, repeat po pierwszej pętli.

Przykład – oczekiwanie na naciśnięcie dowolnego klawisza:

uses Crt;
begin
 while not keypressed do ;
end.

Pętla while wymaga zastosowania begin, end, gdy mamy zamiar używać więcej niż jednej instrukcji.

Przykład – oczekwianie na naciśnięcie dowolnego klawisza, zliczanie wywołań pętli

uses Crt;
var i : LongInt;
begin
 while not keypressed do
 begin
   i := i + 1;
   WriteLn('Pętla wykonuje się po raz ', i);
 end;
end.

Warunkowe wychodzenie z pętli: break, continue

Gdy zamierzasz zbudować pętlę, z której można wydostać się pod jakimś warunkiem, nie sprecyzowanym w warunku pętli, lub przy pętli for, przed osiągnięciem ostatniej wartości użyj break. Break powoduje, że program zaczyna wykonywać się zaraz za pętlą. Kończy ją, bez osiągnięcia warunku kończącego.

Uwaga, w pętli zagnieżdżonej break spowoduje wyjście tylko z tej pętli, w której został użyty. Nie wyjdzie ze wszystkich pętli.

Słowo continue, powoduje przejście do kolejnego wywołania pętli.

Przykład użycia Break;

var i : LongInt;
begin
 i := 0;
 while i<100000 do
 begin
   i := i + 1;
   WriteLn('Pętla wykonuje się po raz ', i);
   if Port[$60] = 1 then break;
 end;
end.

W przykładzie pętla wykonała by się 100000 razy i zakończyła. Teraz możesz ją zakończyć również wcześniej gdy wciśniesz klawisz Escape.

Przykład użycia Continue;

var i : LongInt;
begin
 i := 0;
 while i<100000 do
 begin
   i := i + 1;
   if i mod 3 <> 0 then continue;
   WriteLn('Pętla wykonuje się po raz ', i);
 end;
end.

Pętla wykonuje się 100000 razy, ale informację o wywołaniu wyświetli tylko gdy jest ono podzielne przez 3 (reszta dzielenia -czyli mod zmiennej "i" przez 3 będzie równa 0)

Rekurencja

Czy patrzyłeś kiedyś w lustro, w którym było widać drugie lustro, a w tym lustrze znowu pierwsze lustro i w tym pierwszym znowu to drugie i tak bez końca? Obraz tworzy się praktycznie nieprzerwanie.

Być może też słyszałeś w dzieciństwie piosenkę o psie:

"Wlazł pies do budy i porwał mięsa ćwierć. A kucharz głupi zarąbał go na śmierć. A kucharz mądry co litość w sercu miał, wykopał mu dołeczek, wsadził psa i taki napis dał: "Wlazł pies do budy i porwał mięsa ćwierć. A kucharz głupi zarąbał go na śmierć. A kucharz mądry co litość w sercu miał, wykopał mu dołeczek, wsadził psa i taki napis dał: ""...itd""

Coś podobnego dzieje się w rekurencji. Rekurencja to wywołanie jakiejś metody przez samą siebie. W pewnym miejscu następuje ponowne wywołanie siebie od początku. Gdyby nie przerwać rekurencji, trwałaby w nieskończoność.

W programowaniu pewna procedura wywołuje siebie samą i coraz bardziej zagnieżdża się w swoim kodzie. Wiąże się to z odłożeniem pewnej pamięci na tzw. stos. Gdyby nie przerwać tego 'błędnego koła' pamięć w końcu się skończy, a program przestanie działać.

Rekurencję wykorzystuje się do niektórych metod, takich jak: wypełnianie obrazka jakimś kolorem, wykrywanie min w grze saper, obliczanie pewnych działań matematycznych. Przydaje się także podczas tworzenia drzew katalogów, wyszukiwania plików, budowania forum internetowych i wielu innych zastosowań. Przykład użycia rekurencji do obliczania silni, możesz zaobserwować w rozdziale poświęconym pisaniu funkcji.


Wyszukiwarka

Podobne podstrony:
Iteracja i rekurencja
Definicja Rekurencji i Iteracji
rekurencja-iteracja-wikipedia, Semestr 1
REKURENCJA I ITERACJA, Technik Informatyk, PROGRAMOWANIE
rekurencja-iteracja, Semestr 1
rekurencja-iteracja1, Semestr 1
14instrukcje iteracyjne (petle)
Definicja Rekurencji i Iteracji
Wzajemna regulacja gruczołów wydzielania wewnętrznego, pętle sprzężeń między gruczołami
Metody układania algorytmów rekurencja, metoda dziel i zwyciężaj, programowanie dynamiczne, metoda
mata2 rekurencja slajdy
mat bud - kruszywo metoda iteracji, Studia, II rok, Materiały Budowlane 2
06 Rekurencja
13 PP Rekurencjaid 14488 (2)
Algorytmy Rekurencja
Instrukcja iteracyjna For 1
36 Rekurencja

więcej podobnych podstron