Informacje dla kandydatów

O Największym Wspólnym Dzielniku

Największy wspólny dzielnik dwóch dodatnich liczb naturalnych \(a\) oraz \(b\) jest zdefiniowany następująco:
$$NWD(a, b) = \max \{k: k | a \wedge k | b\},$$
czyli jest to największa liczba naturalna jednocześnie dzieląca liczby a i b.

Posiada on następujące własności:
$$
\begin{array}{rl}
W_1: & NWD(a, a) = a\\
W_2: & a > b \rightarrow NWD(a, b) = NWD(a-b, b)\\
W_3: & a < b \rightarrow NWD(a, b) = NWD(a, b-a)
\end{array}
$$
Pierwsza własność jest oczywista (wynika bezpośrednio z definicji). Druga wymaga pewnego, ale prostego, uzasadnienia. Trzecia własność jest symetryczną wersją własności drugiej. Z własności tych wynika natychmiastowy sposób obliczania NWD: odejmuj liczbę mniejszą od większej tak długo aż staną się równe.

Oto przykład:

NWD(20, 14) = NWD(6, 14) = NWD(6, 8) = NWD(6, 2) = NWD(4, 2) = NWD(2, 2) = 2.


A oto przekształcenie tego algorytmu w pseudo-kod:

ASSUME: a > 0, b > 0;
WHILE (a <> b) DO
  IF (a > b) THEN a := a - b
                  ELSE b := b - a
OD;
RETURN a;
W każdej iteracji pętli tego algorytmu liczba \(a+b\) ulega zmniejszeniu, a z tego łatwo wynika (dlaczego?), że algorytm ten skończy wykonywanie pętli po skończonej liczbie kroków. Rozważmy wartości zmiennych \(a\) i \(b\) przed rozpoczęciem pętli i obliczmy \(K = NWD(a,b)\). Z własności \(W_2\) i \(W_3\) funkcji NWD wynika, że liczba ta nie ulega zmianie w trakcie działania pętli. Jest więc jej niezmiennikiem. Zatem po jej zakończeniu mamy \(a = K\).

Powyższy rozumowanie jest typowe dla algorytmiki. Zauważmy jednak, że do tej pory tylko rozpoczęliśmy analizę tego algorytmu. Kolejnym ważnym zagadnieniem jest analiza jego złożoności obliczeniowej. Nie będziemy tego wątku tutaj analizować, gdyż powyższy algorytm nie jest optymalny. Dosyć wyczerpującą analizę ulepszonej wersji algorytmu znaleźć można na Wikipedii.

A teraz zajmijmy się aspektem programistycznym rozważanego algorytmu.

Oto jak go można zrealizować w różnych językach programowania:

C

  while (a!=b)
   if (a>b) a-=b;
   else b-=a;

Python

while a != b:
  if a > b:
    a = a - b
  else:
    b = b - a 

Ada

WHILE a/=b LOOP
  IF a>b THEN a:=a-b;
         ELSE b:=b-a;
  END IF;
END LOOP;

Prolog

nwd(A,A,A).
nwd(A,B,C):- A > B, A1 is A-B, 
             nwd(A1,B,C).
nwd(A,B,C):- B > A, B1 is B-A,
             nwd(A,B1,C).

Fortran

DO WHILE (A .NE. B)
  IF (A .GT. B) THEN
    A=A-B
  ELSE
    B=B-A
  END IF
END DO

Cobol

PERFORM WITH TEST BEFORE UNTIL a EQUAL b
IF A GREATER B THEN
  SUBTRACT b FROM a
ELSE
  SUBTRACT a FROM b
END-IF
END-PERFORM

Haskel 98

nwd a b =
  if a>b then
    nwd (a-b) b
   else if a < b then
     nwd a (b-a)
   else
     a
Chyba czujesz już wyraźnie czym różni się ALGORYTMIKA od prostego RZEMIOSŁA PROGRAMISTYCZNEGO.
Katedra Informatyki
Politechnika Wrocławska
Wydział Podstawowych Problemów Techniki