Намиране на НОД на две цели поло

Намиране на НОД на две цели положителни числа

Задача: Дадени са целите числа А и В, А>B>0. Да се намери най-голямото цяло число, което дели без остатък както А, така и В.

Решение:

Ако не знаем алгоритъма на Евклид, бихме могли да решим задачата по следния начин. Проверяваме дали В не е общ делител. Ако не е, проверяваме за целите числа от В-1 до 1 дали не са общи делители. Първият намерен общ делител ще бъде НОД. Тази процедура обаче изисква много пресмятания. Алгоритъмът на Евклид с деление е по-бърз и се състои в следното.

За А и В е в сила представянето A=M1.B+N1, 0≤N1<B. Продължаваме с представяне на В и N1, N1 и N2 и т.н. докато получим Nk=0.

B=M2.N1+N2, 0≤N2<N1

N1=M3.N2+N3, 0≤N3<N2

……………………..

Nk-2=Mk.Nk-1+Nk, Nk=0

Тогава Nk-1 е НОД на А и В. Докато първият алгоритъм очевидно намира НОД на две числа, правилността на алгоритъма на Евклид се нуждае от доказателство.

Да илюстрираме работата на алгоритъма на Евклид с един пример.

Нека А=784, B=240. Последователно получаваме:

784=3.240+64

240=3.64+48

64=1.48+16

48=3.16+0

Следователно НОД на 784 и 240 е 16.

Със знак % в блоковите схеми е означана операцията пресмятане на остатък при деление.

За много масови задачи първият алгоритъм, за който се досетим, не е най-добрият. Създаването на качествен алгоритъм често е свързано с изучаването на свойствата на входните или изходните обекти. В редица случаи без такова математическо изследване въобще не е възможно създаването на алгоритъм.