MeZon Team
ГлавнаяО насДокументацияКаталог статейСсылкиОбратная связь

Алгоритм Евклида для нахождения наибольшего общего делителя (НОД).

Алгоритм Евклида — алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин.

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида теорию отношений, альтернативную по отношению теории отношений Евдокса, изложенной в V книге «Начал» Евклида. Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.

Описание

Пусть a и b целые числа, не равные одновременно нулю, и последовательность чисел a, b, r1 > r2 > r3 > ... >rn определена тем, что каждое rk — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть:

a = bq0 + r1
b = r1q1 + r2
r1 = r2q2 + r3
...
rk−2 = rk−1qk−1 + rk
...
rn−1 = rnqn

Тогда НОД(a,b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности.

Релизация Pascal

  function nod( a, b: longint): longint; 
  begin
   while (a <> 0) and (b <> 0) do begin
     if a >= b then 
       a:= a mod b 
     else 
       b:= b mod a;
   end;
   nod:= a + b;
  end;

Релизация Pascal в рекурсивном виде

  function nod(var a, b: longint): longint; 
  begin
   if (a = 0) or (b = 0) then
     if a = 0 then
       nod:= b
     else 
       nod:= a
   else 
     if a >= b then 
       nod:= nod( a mod b, b)
     else 
       nod:= nod( a, b mod a)
  end;

 

Главная | Новости | О нас | Проекты | Документация | Каталог статей | Ссылки | Обратная связь
Каталог TUT.BY © 2002-2017 MeZon Team, Minsk, Republic of Belarus.
Meta Zone Web Engine v4.9
2017.08.19 06:42:47