Algorytm B dla bystrzaków

Dostałem takie pytanie

Mam problem z napisaniem programu algorytm b ,nie wiem w jaki sposób wrócić do wcześniejszego kroku, nie rozumiem w jaki sposób mam wykorzystać schemat blokowy do napisania kodu.

Ciężka sprawa, bo jest to pytanie z gruntu tych najbardziej podstawowych.

Popatrzmy raz jeszcze na algorytm:

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

Proszę spokojnie na niego spojrzeć i zastanowi się czy rozumie Pan/Pani (rozumie w sensie potrafi wykonać za pomocą kartki i ołówka) wszystkie polecenia.

Jeżeli tak, proszę algorytm przeliczyć dla następujących danych

\(u = 258\) i \(v=640\).

15 minut przerwy

Wyszło? Proszę sprawdzić czy wynik jest poprawny (to znaczy czy otrzymana liczba rzeczywiście jest NWD dla podanych liczb).

5 minut przerwy

Wyszło?

Jeżeli nie — raz jeszcze (ale tym razem dla \(u=121\; v=22\)).

Zakładam, ze w końcu wyjdzie.

Teraz bierzemy się za programowanie

Najpierw krok 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.

Wszystkie zmienne są całkowite. W algorytmie występują zmienne: \(u\), \(v\), \(k\), \(t\) , więc deklarujemy je:

int u, v, w, k;

Nadajemy wartości początkowe zmiennym u, v i k:

u = 258;
v = 640;
k = 0;

Wymienione w tym punkcie operacje należy wykonywać do chwili gdy przynajmniej jedna z nich przestanie być parzysta¹. Czyli warunkiem rozpoczęcia i kontynuowania pętli jest parzystość obu liczb.

Do dyspozycji mamy dwa podstawowe rodzaje pętli:

1. while (najpierw sprawdza czy warunek jest spełniony, później wykonuje operacje);
2. do — while (wchodzi do pętli, wykonuje operację i sprawdza czy warunek jest spełniony).

Wybieramy oczywiście while (proszę się zastanowić czemu?).

Teraz jak sprawdzić czy liczba jest parzysta? Najprościej podzielić przez dwa i sprawdzić jaka jest reszta. Do wyliczania reszty z dzielenia służy operator %.

Zatem będzie to jakoś tak:

while (u % 2 == 0 && v % 2 == 0)
{
    u = u / 2;
    v = v / 2;
    k = k + 1;
}

Chyba jest to jasne: tak długo jak u jest parzyste i v jest parzyste wykonuj…

Po wyjściu z pętli jedna (lub obie) z liczb u, v jest nieparzysta.

Teraz krok 2.

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

To jest chyba dosyć proste. Użyjemy poleceń if (jeżeli) i goto (przejdź do kroku).

if (u % 2 == 1)    // Jeżeli u jest nieparzyste…
{
    t = -v;
    goto krok4;
}
else               // …w przeciwnym razie u jest parzyste
{
    t = u;
}

Z instrukcji if wychodzimy albo za pomocą polecenia goto krok4 albo po przejściu przez gałąź else. Jak wychodzimy do kroku 4 to nie wiemy jaka liczba jest w t (parzysta czy nie). Po przejściu przez else w t jest wartość parzysta (czemu?).

Kroki 3 i 4:

Rozpatruję razem bo są ze sobą związane.

Przyjmij \(t \leftarrow t/2\). Zaprogramujemy to w oczywisty sposób. (Dodaję etykietę krok3 żeby można było do tego kroku wrócić):

krok3:
t = t / 2;

Jeżeli \(t\) jest parzyste to wróć do kroku 3 (znowu dodam etykietę krok4)

krok4:
if (t % 2 == 0)
    goto krok3;

Krok 5

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

To jest łatwe. Użyję instrukcji if

if (t > 0)
    u = t;
else
    v = -t;

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

Pierwsza część oczywista:

t = u - v;

teraz polecenie if

if (t != 0)
    goto krok3;

tu się chwilkę zatrzymajmy. wartości u i v powstaję w kroku poprzednim (5) z wartości t , gdy przestanie ona być parzysta, więc na pewno są liczbami nieparzystymi; różnica dwu liczb nieparzystych jest parzysta, zatem spokojnie możemy przejść do kroku 3 gdzie będziemy tę wartość dzielili przez dwa.

Gdy t jest równe zero — skończyliśmy obliczenia i pozostaje całkiem skomplikowana rzecz do zrobienia: wyliczenie wartości \(u \cdot 2^k\). Język C nie zna operatora potęgowania. Mamy do dyspozycji trzy rozwiązania:

1. Wypisać wartości u i k i powiedzieć użytkownikowi żeby sobie sam to wyliczył.
2. Użyć funkcji pow( \(\alpha\), \(\beta\)), która potrafi dla wartości typu double wyliczyć \(\alpha^\beta\) (uwzględniając wszystkie matematyczne ograniczenia).
3. Napisać prosty program w pętli mnożący u „przez siebie” k razy:

int wynik = 1;
while (k > 0)
{
    wynik = wynik * u;
    k = k - 1;
}

(Gdy k jest zero — \(2^k\) to 1; czyli chyba jest dobrze.)

Teraz możemy wydrukować ostateczny wynik:

printf("NWD wynosi %d\n", u * wynik);

Mam nadzieję, że ten przydługawy opis nieco rozjaśnia. Słowny opis algorytmu przerobiłem na program w C. Gdyby wcześniej wyrysować schemat blokowy łatwiej byłoby zidentyfikować pętle.

W algorytmie tym powrót realizowany jest w kroku 4 (przejdź do kroku 3) i w kroku 6 (znowu przejdź do kroku 3). Użyłem polecenia goto. I to są dwie pętle realizowane przez algorytm.