Главная » Free Pascal » Вычисление наибольшего общего делителя Free Pascal

0

Исторически одним из первых рекурсивных алгоритмов является способ вы- числения наибольшего общего делителя (НОД) двух целых чисел, приписываемый Евклиду. Алгоритм Евклида базируется на трех следующих фактах:

± НОД( n1 , n2 ) = НОД( n2 , n1 ). Этот факт сомнения не вызывает;

± НОД(0, n2 ) = n2 . Так как ноль делится на любое число, то и этот факт является истинным;

± НОД( n1 , n2 ) = НОД( n2 , n3 ), где n3  = n1  mod n2

( n1 > n2 ).

Справедливость третьего факта вытекает из равенства n1 = k ´ n2 + n3  ( ³ 1). Алгоритм Евклида включает следующие шаги:

1.                       Раздели большее на меньшее ( n1 / n2 ) и найди остаток от деления ( n3 ).

2.                       Замени НОД( n1 , n2 ) на НОД( n3 , n2 ).

3.                       Если n3 = 0, то НОД = n2 . В противном случае повтори шаги 1 и 2.

Первый вариант функции NOD, в точности повторяющий шаги алгоритма Евк- лида, выглядит так, как представлено в листинге 9.10.

   Листинг 9.10. Функ ция  NOD                                                   

function NOD(n1,n2:integer):integer; var

tmp: integer; begin

if n1 > n2 then begin

tmp:=n1; n1:=n2; n2:=tmp; end;

if n1 = 0 then NOD:=n2

else NOD:=NOD(n2 mod n1, n1); end;

Так как NOD(n1,n2)=NOD(n2,n1), то перестановку n1 и n2 можно не делать — функция NOD иногда лишний раз будет вхолостую обращаться сама к себе. Поэтому приведенный вариант функции NOD можно сократить:

function NOD(n1,n2:integer):integer; begin

if n1 = 0 then NOD:=n2

else NOD:=NOD(n2 mod n1, n1); end;

Выглядит изящнее, но работает медленнее, чем предыдущий вариант.

Не забывайте, что при каждом входе в рекурсивную функцию под ее локальные переменные и рабочие ячейки для хранения промежуточных результатов выделя- ются новые ячейки памяти.

Источник: Кетков, Ю. Л., Свободное программное обеспечение. FREE PASCAL для студентов и школьников, Ю. Л. Кетков, А. Ю. Кетков. — СПб.: БХВ-Петербург, 2011. — 384 с.: ил. + CD-ROM — (ИиИКТ)

По теме:

  • Комментарии