Pętle

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

1. Polecenia while
   
   while ( warunek ) { ... }

   1 2 3 4

   while ( warunek ) { ... }

2. Polecenie do – while
   
   do { ... } while ( warunek );

   1 2 3 4

   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:

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

Zadania do wykonania

1. Zapoznać się z różnymi wariantami algorytmu Euklidesa zaprogramowanymi w Blockly:
   • wersja z odejmowaniem opisana na pierwszym wykładzie
     oraz
   • wersja z resztą.
2. 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”

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\).

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

lub raczej, wersję zmodyfikowaną:

1. 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\)
2. Największym wspólnym dzielnikiem jest \(n\).

Wersja PDF tego dokumentu…

…pod adresem.

Wersja: data ostatniej modyfikacji