Обчислення нсд методом послідовного перебору
Цей метод полягає на підборі найбільшого цілого числа – такого, щоб числа m та n ділилися на нього без залишку. Цілком очевидно, що такий спільний дільник не може бути більший за найменше із даної пари число, яке запишемо як t = min{m, n}. Тому виконання алгоритму можна почати з перевірки того, чи не діляться обидва числа m та n на t без залишку. Якщо це так, то число t є відповіддю, якщо ні – зменшуємо значення t на 1 та знову виконати перевірку. Наприклад, для пари чисел (30, 21) процес буде продовжуватись до тих пір, поки t не стане дорівнювати 3, тобто gcd(30, 21)=3(t=21, 20, 19, 18, …, 3).
Для виконання цієї задачі необхідним є початкова умова: ні одне з заданої пари чисел не повинно дорівнювати нулю. Цей приклад дозволяє показати, наскільки важливо визначати діапазон допустимих значень вхідних параметрів алгоритму.
Обчислення нсд методом розкладу пари чисел на прості множники
Цей метод відомий Вам із курсу математики, що викладався в середній школі. Він полягає в тому, що для пари чисел (m,n) знаходять спільні множники, добуток яких і дасть нам НСД. Для цього спочатку розкладають на прості множники число m, потім число n. Для знайдених простих множників чисел m та n виділяють їх спільні дільники, потім знаходять їх добуток, який і є НСД. Наприклад, знайдемо gcd(30, 21) описаним вище способом:
30 = 2*3*5
21 = 3*7
gcd(30, 21) = 3.
Недолік цього алгоритму – деяка складність в реалізації. Етапи розкладу на прості множники не визначені однозначно. Для їх виконання необхідно мати список простих чисел. Також необхідно виділити спільні елементи із двох списків.
Алгоритм Евкліда пошуку найбільшого спільного дільника (НСД)
Цей алгоритм описаний в книзі древньогрецького математика із Олександрії Евкліда «Начала» біля 300 р. до н.е., хоча не виключено, що він був відомий і раніше.
Алгоритм Евкліда полягає в рекурентному обчисленні наступного рівняння:
gcd(m,n) =gcd(n,mmodn).
Вираз (mmodn) є залишком від діленняmнаn. Виконання алгоритму закінчується, коли вираз (mmodn) дорівнює нулю. Так якgcd(n,о)=n, останнє отримане значенняnбуде НСД заданих вхідних чиселm та n.
Для прикладу знайдемо НСД(30,21):
gcd(30,21) =gcd(21,9) =gcd(9,3) =gcd(3,0) =3 – процедура визиває себе тричі.
Для вхідних даних mтаnповинні виконуватись нерівностіm>n>=0 (приn>m>=0 процедураgcd(m,n) визиватиме себе, переставивши аргументи місцями, а приm=n>0 робота процедури завершиться після першого ж її визивання, оскільки (mmodm) = 0). При всіх рекурсивних визиваннях процедури перший аргумент буде строго більший другого (залишок менше дільника).
Способи запису алгоритмів:
Природна мова - словесний запис, тобто в вільній формі у вигляді послідовності виконуваних дій. Недолік – невизначеність та неоднозначність.
якщо умова то дія1 інакше дія2
Запишемо алгоритм Евкліда за допомогою природної мови.
Крок 1. Якщо n = 0, повернути m в якості відповіді та закінчити роботу; інакше перейти до кроку 2.
Крок 2. Поділити націло m на n і присвоїти значення залишку змінній r.
Крок 3. Присвоїти значення n змінній m, а значення r – змінній n. Перейти до кроку 1.
Псевдокод – мова проектування, що містить основні оператори, що близькі до алгоритмічної мови, а текст речень – на природній мові. Опис алгоритму на псевдокоді є більш компактним та точним в порівнянні з природною мовою. Недолік – відсутність єдиного стандарту. В сучасній літературі використовується досить часто.
Запишемо алгоритм Евкліда у вигляді псевдокоду.
//Алгоритм Евкліда обчислює значення функції gcd(m,n)
//Вхідні дані: два невід’ємні цілі числа m та n, які не можуть одночасно
// дорівнювати нулю
//Вихідні дані: найбільший спільний дільник чисел m та n
while n<>0 do
r←m mod n
m←n
n←r
return m
Операторна мова – аналітична форма запису алгоритму за допомогою формальних операторів, що представлені деякими символами та описують деякі кроки обчислювального процесу.
А – обчислювальний процес, С – умова, В – введення, Р – друк, К – зупинка процесу, Н – початок.
Кожний оператор логічної схеми має порядковий номер у вигляді індексу. Вони виконуються в звичайному порядку – зліва направо. Якщо від оператора ліворуч немає передачі керування оператору праворуч, то між ними ставиться «;». При виконанні умови логічного оператора, наступним є оператор справа, якщо інакше – ставиться стрілка.
Н
В1 А2 С3 (n<>0)
A4
А5 А6 ; Р7 К
Структурограми