13.1. Алгоритм Евкліда пошуку найбільшого загального дільника двох цілих чисел

Задача

Надані числа a>0, b>0, a,b. Знайти найбільший загальний дільник (НЗД) для a,b.

Алгоритм

Для довільних цілих a і b НЗД можна знайти виходячи з відношень НЗД(0,0)=0, НЗД(a,b)=НЗД(b,a), НЗД(a,b)=НЗД(-a,b), НЗД(a,0)=|a|, застосовуючи алгоритм до u=|a| і v=|b|. Алгоритм Евкліда складається з двох етапів.

1. Якщо v=0, то НЗД(v,u)=u і алгоритм завершено.

2. Послідовно виконати операції r = (u mod v), u=v, v=r і повернутись до кроку 1.

Далі наведено два варіанта функції для визначення НЗД двох чисел. Перший варіант -рекурсивний. Для нього є характерним те, що глибина рекурсії, яка буде потрібна для обчислення НЗД для наданих чисел наперед невідома. Хоча і відомо, що вона завжди скінчена. Застосування рекурсії не завжди виправдане, бо дуже велика глибина рекурсії може привести до переповнення стеку і аварійного завершення роботи програми. При кожному виклику рекурсивної функції створюється нове покоління локальних об'єктів з такими ж іменами, що й при попередньому зверненні до функції, але зі своїми значеннями.

У обох варіантах функції для обчислення НЗД передбачається, що надані числа a,b є не від’ємними.

// алгоритм Евкліда, рекурсивна версія

long r_euclid(long a, long b)

{ long u,v,r;

if (v==0) return u;

else return r_euclid(v, u%v);

}

Другий варіант функції - циклічний, в ньому для обчислення НЗД використовується цикл.

// алгоритм Евкліда, циклічна версія

long c_euclid(long a, long b)

{ long u,v,r;

while (v!=0) { r = u % v;

u = v;

v = r;

}

return u;

}

Спробуйте виконати таку корисну вправу. Знайдіть відповідь на таке запитання: якщо числа a,b, для яких обчислюється НЗД, не перевищують надану величину M, то чому буде дорівнювати глибина рекурсії при виконанні функції r_euclid(a,b) та кількість циклів при виконанні функції c_euclid(a,b) у найгіршому випадку?