Algorytm iteracyjny – algorytm, który uzyskuje wynik przez iterację, czyli powtarzanie danej operacji początkowo określoną liczbę razy lub aż do spełnienia określonego warunku. Niektóre problemy można rozwiązać zarówno za pomocą algorytmu iteracyjnego, jak i rekurencyjnego.
Przykład 1
| Algorytm obliczający sumę n kolejnych liczb począwszy od 1. Dane:
n – ilość liczb, które chcemy do siebie dodać, i – iteracja (pętla), Suma – suma n liczb. Pierwszy blok operacyjny nie jest zasadniczą instrukcją. Jest on potrzebny, aby ustalić na wstępnie, że suma wynosi zero, gdyż jeszcze nic do siebie nie dodano. Nie wykonano też żadnej iteracji i dopiero po pierwszej pętli będziemy mogli sprawdzić warunek. Warunek (ustalony licznik) mówi nam, że pętla ma być tyle razy wykonywana, ile liczb planujemy do siebie dodać. Jest to logiczne, gdyż z każdą pętlą dodajemy kolejną liczbę. Aby pętla mogła działać prawidłowo i działała w czasie skończonym, musimy stworzyć kolejne instrukcje. i:=i+1 oznacza, że ilość wykonanych pętli ma zostać zwiększona o jeszcze jedną pętlę. Suma:=Suma+i oznacza sumę liczb wykonanych w pętli. Suma:= 0 (ponieważ jeszcze nic nie dodano) Suma + 1 (Suma + 1) + 2 (Suma + 1 + 2) + 3 … Suma:= Suma+i gdzie i będzie zwiększane od 1 do n |
|
| Kiedy już liczba pętli będzie równa ilości liczb, które chcemy do siebie dodać zostanie spełniony warunek: i=n. Wówczas algorytm podaje sumę tych liczb i kończy działanie (lewa strona schematu blokowego). | |
Przykład 2
Algorytm obliczający sumę n kolejnych liczb parzystych.
Algorytm będzie wyglądał podobnie do powyższego. Różnice:
w bloku warunkowym postawimy warunek: i=2*n
Jeżeli chcemy dodać kolejne 3 liczby parzyste, to musimy przeanalizować dwa razy tyle liczb: 1, 2, 3, 4, 5, 6
W bloku operacyjnym zamiast: i:=i+1 na i:= i + 2, gdyż obchodzi nas tylko co druga pętla.
Jeżeli chcemy sprawdzić, czy dana liczba jest parzysta, musimy ją podzielić na dwa. Wynik bez reszty oznacza, że liczba jest parzystą.
Jak wykonać to w algorytmie?
Musi być spełniony warunek:
a mod 2 = 0
gdzie a to dowolna liczba.
Zadanie 1
Przykładowy program zawierający instrukcje iteracyjne
Hodowca królików chciałby dowiedzie się, kiedy liczba zwierząt przekroczy liczbę miejsc w klatkach, którymi dysponuje. Hodowlę zaczyna od jednej pary królików. Wiadomo, że para dorosłych królików (tj. starszych niż 3 miesiące) ma średnio co 3 miesiące dwoje młodych. Hodowca dysponuje klatkami mogącymi pomieścić 1000 królików. Napisz program, który pozwoli wyliczyć, za ile miesięcy zabraknie miejsc w klatkach.
Rozwiązanie
Dane: 1000 – liczba królików, które hodowca może pomieścić w klatkach, n – liczba królików, które aktualnie posiada hodowca.
Oczekiwany wynik: m – liczba miesięcy, za ile zabraknie miejsc w klatkach. (Już po m-3 miesiącach hodowca powinien rozważyć kupno nowych klatek).
Analiza zadania: Po 3 miesiącach hodowca będzie miał 2 dorosłe króliki i 2 młode króliki, razem 4 króliki. Po kolejnych 3 miesiącach hodowca będzie miał 4 dorosłe króliki i 4 młode króliki, razem 8 królików. Po kolejnych 3 miesiącach hodowca będzie miał 8 dorosłych królików i 8 młodych królików, razem 16 królików. Zauważmy, że co 3 miesiące podwaja się liczba królików.
Algorytm w postaci listy kroków – WHILE
- m podstaw 0
- n podstaw 2
- Dopóki n <= 1000 wykonuj
- n podstaw 2n
- m podstaw m + 3
- Wyświetl wartość m.
- Zakończ program.
