1 Pętle

Tematem przewodnim zajęć jest zapoznanie się z dwiema podstawowymi konstrukcjami do tworzenia pętli:

Polecenia while
```
while ( warunek )
{
...
}
```
Polecenie do – while
```
do
{
...
} while ( warunek );
```

W miejscu gdzie pojawiają się trzy kropeczki wstawiamy polecenie/polecenia, które będą wykonywane w pętli tak długo, jak długo warunek jest prawdziwy.

Polecenie while (oraz do – while) istotnie różnią się od polecenia if. Na pierwszy rzut oka różnica nie jest specjalnie wielka:

if (m > n)
{
    m = m - n;
}

while (m > n)
{
    m = m - n;
}

ale istota pierwszego przykładu (if) jest taka: sprawdź czy $m$ jest większe od $n$ i jeżeli tak jest wykonaj operację odejmowania ($m = m - n$) zapisując wynik w $m$.

W drugim przypadku (while) tak długo jak $m$ jest większe od $n$ wykonuj operację odejmowania ($m = m - n$).

W pierwszym przypadku będzie jedno sprawdzenie i (gdy wynik będzie pozytywny) jedno wykonanie odejmowania.

W przypadku drugim będzie cykl: sprawdzenie warunku — ewentualne wykonanie odejmowania; zawsze po wykonanym odejmowaniu sprawdzany będzie ponownie warunek. Gdy warunek nie będzie spełniony — przechodzimy do wykonywania kolejnego polecenia.

Algorytm Euklidesa

Wszystkie zmienne są typu int!

Zadania do wykonania

Zapoznać się z różnymi wariantami algorytmu Euklidesa zaprogramowanymi w Blockly:
- wersja z odejmowaniem ~~opisana na pierwszym wykładzie~~
  oraz
- wersja z resztą.
Napisać program realizujący algorytm Euklidesa (preferowana jest wersja „z resztą”. Algorytm powinien być zaprogramowany na co najmniej dwa sposoby: z wykorzystanie instrukcji while i do – while. Ewentualnym, trzecim sposobem może być użycie pętli for.

Wersja „z resztą”

Dane są dwie dodatnie liczby całkowite $m$ i $n$. Należy znaleźć ich największy wspólny dzielnik, tj. największą dodatnią liczbę całkowitą, która dzieli bez reszty zarówno $m$ jak i $n$.

[E1] : [Znajdowanie reszty] Podziel $m$ przez $n$ i niech $r$ oznacza resztę z tego dzielenia.
[E2] : [Czy wyszło zero?] Jeśli $r=0$, zakończ algorytm; odpowiedzią jest $n$.
[E3] : [Upraszczanie] Wykonaj $m \leftarrow n$, $n \leftarrow r$ i wróć do kroku E1.

Wersja „z odejmowaniem"

Jeżeli $m$ jest równe $n$ — koniec, największym wspólnym dzielnikiem jest $n$.
Jeżeli $m> n$ przyjmij $m\leftarrow m-n$; w przeciwnym razie przyjmij $n\leftarrow n-m$
Przejdź do kroku 1.

lub raczej, wersję zmodyfikowaną:

Tak długo jak $m \ne n$ powtarzaj:
1. Jeżeli $m> n$ przyjmij $m\leftarrow m-n$; w przeciwnym razie przyjmij $n\leftarrow n-m$
Największym wspólnym dzielnikiem jest $n$.

Na czym polega problem?

Porównajmy uproszczone schematy blokowe

Algorytmu E
flowchart LR AA((Start)) ---> A[Instrukcja1] ---> B{warunek} --->|Nie| C[Instukcja2] ---> A B --->|Tak| AAA((Stop))
polecenia while
flowchart LR AA((Start)) ---> A{warunek} --->|Tak| B[Instrukcja] --- A A --->|Nie| AAA((Stop))
petli do
flowchart LR AA((Start)) ---> A[Instrukcja] ---> B{Warunek} --->|Tak| A B -->|Nie| AAA((Stop))

while zaczyna się od warunku, jak jest spełniony — wykonujemy jakieś polecenia i powtarzamy

do — najpierw wykonujemy jakieś polecenie, później sprawdzamy warunek i jeżeli jest spełniony — powtarzamy.

Algorytm E ma instrukcje przed warunkiem (jak do) i po warunku (jak while). Natomiast jego istotą jest aby operacje były wykonywane w kolejności:

instrukcje 1 $\rightarrow$ warunek $\rightarrow$ instrukcje 2 $\rightarrow$ instrukcje 1 $\rightarrow$ warunek $\rightarrow$ instrukcje 2 $\rightarrow$ …$\rightarrow$ warunek

W każdym przypadku korzystając ze standardowych poleceń pętlowych trzeba te „nadmiarowe" instrukcje uwzględnić.

Laboratorium 2: Algorytm Euklidesa