Творческая исследовательская работа нод и нок и их применение в практических задачах

2.2. Различные способы нахождения наибольшего общего делителя
натуральных чисел
1 способ метод полного перебора.
1. Выписываем все делители числа а;
2. Выписываем все делители числа b;
3. Выбираем среди них общие делители;
4. Среди общих делителей выбираем самое большое число – это и есть НОД(a, b).
Например: Найти НОД(32;48).
Делители 32: 1; 2; 4; 8; 16; 32; делители 48: 1; 2; 3; 4; 6; 8; 12; 16; 24; 48.
Общие делители 32; 48: 1; 2; 4; 8; 16. НОД(32; 48) = 16.
Если числа достаточно большие, то нахождение НОД(а;b) путем перечисления всех делителей чисел а и b - процесс трудоемкий и ненадежный.
2 способ разложение чисел на простые множители.
1. Находим разложение чисел на простые множители.
2. Подчеркиваем общие множители.
3. Находим произведение общих множителей у одного числа – НОД .
Например: НОД(36; 48) =2*2*3 =12.

48 24 12 6 3 1

2 2 2 2 3

36 18 9 3 1

2 2 3 3

Это способ удобен и надежен для вычисления НОД трех и более натуральных чисел, но иногда он сложен при поиске простого делителя числа.

2.3. Алгоритм Евклида и его применение
Этот алгоритм приписывают Евклиду, одному из величайших математиков древности. Евклид жил в III-II в до н.э. в Александрии. Он оставил несколько сочинений, известных в латинских и арабских переводах, наиболее значительное из которых – состоящие из 13 книг «Начала» («Elements»)- представляет собой систематическое изложение математики того времени.


1 алгоритм: Алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел вычитанием.
Этот алгоритм, видимо, не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин.
1. Из большего числа вычитается меньшее.
2. Если получается 0, то числа равны друг другу и являются наибольшим общим делителем.
3. Если результат вычитания не равен 0, то большее число заменяется на результат вычитания, процесс продолжается до тех пор, пока разность станет равна нулю.
Например: Найти НОД(30; 18).
30 - 18 = 12; 18 - 12 = 6; 12 - 6 = 6; 6 – 6 = 0.

30	12	12	6
18	18	6	6

НОД – это уменьшаемое или вычитаемое.

НОД (30; 18) = 6.
Приведенный метод вычисления не является оптимальным. Например, для нахождения НОД(648; 20) следует выполнить много таких операций.


2 алгоритм: Алгоритм Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел делением.
1. Большее число делится на меньшее
2. Если делится без остатка, то меньшее число и есть наибольший общий делитель.
3. Если есть остаток, то делитель делим на остаток от деления,
продолжаем аналогичное деление до тех пор, пока не получим в остатке нуль. Последний неравный нулю остаток и есть НОД данных чисел.


r_n – НОД(a, b).


Пример1: Найти НОД (273;1014).
Решение.
Выполняем деление с остатком:
1014=273*3+195;
273=195*1+78;
195=78*2+39;
78=39*2
НОД (273;1014) = НОД(195;273) = НОД(195;78) = НОД(78;39)= 39
Пример 2: Найти НОД (661,113)
Решение:
Выполняем деление с остатком: 
661=113*5+96; 113=96*1+17; 96=17*5+11; 17=11*1+6; 11=6*1+5; 6= 5*1+1, 5=1*5. НОД(661, 113)=1, то есть, 661 и 113 – взаимно простые числа.


3 алгоритм: Бинарный алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел.
Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном.
Алгоритм выглядит так:

1. 
   Если a, b чётные, то НОД(a; b) = 2*НОД(a/2; b/2);
   
2. 
   Если a чётное, b нечётное, то НОД(a; b) = НОД(a/2; b);
   
3. 
   Если b чётное, a нечётное, то НОД(a; b) = НОД(a; b/2);
   
4. 
   Если a, b нечётные и b > a, то НОД(a; b) = НОД((b-a)/2; a);
   
5. 
   Если a, b нечётные и b < a, то НОД(a; b) = НОД((a-b)/2; b);
   

Например:
НОД(1978;2666) = 2*НОД(989;1333) = 2*НОД(989;344/2) = 2*НОД(989;172)= =2*НОД(989;86/2) = 2*НОД(989;43) = 2*НОД(946/2;43) = 2*НОД(473;43) = =2*НОД(430/2;43 ) = 2*НОД(215; 43) = 2*НОД(172/2; 43) = 2НОД*(86/2; 43) = =2*НОД(43; 43) = 2*43=86.
НОД(1978; 2666)=86
Бинарный алгоритм Евклида сокращает количество операций при вычислении НОД, но требует знания применяемых формул.
Для алгоритма Евклида существует множество теоретических и практических применений. В частности он широко распространён в электронной коммерции. Также алгоритм используется при решении диофантовых уравнений (Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами). Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения называют диофантовыми, в честь древнегреческого математика Диофанта Александрийского. Алгоритм Евклида также является основным инструментом для доказательства теорем в современной теории чисел.


Пример задачи с диофантовым уравнением.
Для газификации жилого дома требуется проложить газопровод протяженностью 150 м. Имеются трубы 13 м и 9м длиной. Сколько требуется труб, чтобы не приходилось их разрезать при прокладке газопровода.
Для решения составляем уравнение: x*9 + y* 13 = 150.
Ответ. Для прокладывания газопровода потребуется 8 труб длиной по 9м и 6 труб длиной по 13м.


Пример применения алгоритма Евклида вычитанием.
Задача 1.
Лист фанеры имеет прямоугольную форму, его ширина равна 56см, длина – 77см. Какое наибольшее количество квадратов можно получить из этого листа, отрезая постепенно квадраты с наибольшей стороной из оставшейся части прямоугольника, и чему равна сторона меньшего квадрата?
Решение.
Для того, чтобы дать ответ на поставленную задачу мы вычтем из большей стороны меньшую и полученной разностью заменим значение большей стороны, т.е. действуем по алгоритму Евклида.

56	56	35	14	14	7
77	21	21	21	7	7

Получилось 6 квадратов, меньший квадрат со стороной 7см. Заметим, что НОД(56; 77) = 7.
Ответ: 6 квадратов, 7см.
Долгое время алгоритм Евклида был самым эффективным способом отыскания наибольшего общего делителя, однако с появлением электронно-вычислительных машин ситуация изменилась Учет специфических особенностей выполнения арифметических операций компьютером позволил построить более эффективную (для программной реализации) версию алгоритма Евклида.