algorytm Euklidesa

pochodzacy sprzed 2300 lat algorytm obliczania Ä najwiekszego wspólnego dzielnika (NWD) dwóch liczb, zamieszczony przez Euklidesa w dziele Elementy. Dane wejsciowe: liczby calkowite nieujemne a i b. A.E. mozna wypowiedziec nastepujaco: (1) jesli b = 0, to NWD = a i koniec; (2) wykonaj czynnosci okreslone w p. 1, podstawiajac w miejsce a liczbe b i w miejsce b liczbe a mod b, czyli reszte z dzielenia calkowitego a przez b. Oto funkcja Euclid realizujaca a.E. w jezyku ANSI C:

int Euclid(int a, int b) 
{ 
  if (b == 0) return a; 
  else return Euclid(b, a % b); 
} 

Reklama

Podobne hasła:

Encyklopedia Internautica

Reklama

Reklama

Reklama