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