6. Programowanie

Dziś programujemy

Zadanie 1

• Zaprogramować jako funkcję algorytm E (algorytm Eukildesa) wyznaczania największego wspólnego dzielnika dwu liczb $m$ i $n$ (całkowitych, większych od zera) opisany w następujący sposób:

  1. Niech $r$ będzie resztą z dzielenia $m$ przez $n$ (r = m % n;)¹

  2. Jeżeli $r = 0$ — największym wspólnym dzielnikiem jest $n$;

     W przeciwnym razie

  3. $m \leftarrow n$

     $n\leftarrow r$

     przejdź do kroku 1.

  Uwagi:

  • W MATLABie operację modulo realizuje funkcja mod(a, b) wyliczająca operację a % b

  Schemat blokowy algorytmu

  

Zadanie 2

Zaprogramować jako funkcję algorytm B (binarny² algorytm Eukildesa) wyznaczania największego wspólnego dzielnika dwu liczb $u$ i $v$ (całkowite, większe od zera) opisany w następujący sposób:

1. Przyjmij $k \leftarrow 0$, a następnie powtarzaj operacje: $k \leftarrow k+1$, $u \leftarrow u/2$, $v \leftarrow v/2$ zero lub więcej razy do chwili gdy przynajmniej jedna z liczb $u$ i $v$ przestanie być parzysta.

2. Jeśli $u$ jest nieparzyste to przyjmij $t \leftarrow -v$ i przejdź do kroku 4. W przeciwnym razie przyjmij $t \leftarrow u$.

3. (W tym miejscu $t$ jest parzyste i różne od zera).

   Przyjmij $t \leftarrow t/2$.

4. Jeśli $t$ jest parzyste to przejdź do 3.

5. Jeśli $t > 0$, to przyjmij $u \leftarrow t$, w przeciwnym razie przyjmij $v \leftarrow -t$.

6. Przyjmij $t \leftarrow u-v$. Jeśli $t \not = 0$ to wróć do kroku 3. W przeciwnym razie algorytm zatrzymuje się z wynikiem $u \cdot 2^k$.

Jak sprawdzić czy liczba jest parzysta?

Schemat blokowy algorytmu

Zwracam uwagę, iż w oryginalnym algorytmie pojawiają się określenia

• przejdź do kroku 4 (krok 2)
• przejdź do 3 (krok 4)
• wróć do kroku 3 (krok 6)

Polecenia te żądają zmiany kolejności wykonywania kodu i mogłyby być realizowane przez funkcję skoku. (Jest taka zarówno w C jak i C++).

Funkcji skoku nie ma w MATLABie

Trzeba algorytm zmodyfikować w taki sposób, żeby nie zmienić idei samego algorytmu i pozbyć się (niedostępnej w MATLABie) instrukcji goto.

Uwagi pomocnicze

1. Sprawdzić poprawność działania algorytmu korzystając z funkcji MATLABa gcd()
2. Jakiego typu danych powinniśmy użyć do obliczeń? (oczekuję dyskusji w sprawozdaniu)