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\ne 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=121v=22$).

Zakładam, ze w końcu wyjdzie.

Teraz bierzemy się za programowanie, czyli patrząc na powyższy zapis algorytmu zabieramy się za programowanie każdego kroku.

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 % (w normalnym świecie nazywa się on modulo).

Zatem będzie to jakoś tak (== to operator logiczny porównania dwu wartości, a &&, to operator logicznego I (AND po angielsku)):

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

I one właśnie powinny być zastąpione odpowiednimi poleceniami realizowania pętli (while lub do – while; pętlam for niespecjalnie sie nada, ale można 😄).