Алгоритм Евкліда
Коли кажуть "число ділитися", то мають на увазі, що воно ділиться без залишку. Так A ділитися на B, лише тому випадку, якщо залишок від своїх поділу дорівнює нулю. У цьому властивості грунтується поняття найбільшого загального дільника (НОД). НОД двох чисел — це найбільший із усіх їхніх спільних дільників.
Алгоритм Евкліда відніманням.
Знайти НОД двох цілих чисел трохи простіше використовуючи операцію віднімання. Для цього потрібно слідувати такій умові: якщо A = B, то НОД знайдено і він дорівнює одному з чисел, інакше необхідно більше двох чисел замінити різницею його і меншого.
Блок-схема Алгоритма Евкліда відніманням:
Оперуючи даною блок-схемою - складаючи за нею програмний код, цілком доцільно включити до нього оператор циклу з вкладеним умовним оператором розгалуження, що має дві гілки.
Код програми на C++ (віднімання):
Код програми на Pascal (віднімання):
Алгоритм Евкліда поділом.
Другий спосіб відрізняється від першого тим, що в основній частині програми операція віднімання замінюється на операцію поділу, а точніше взяття залишку від поділу великого числа на менше. Цей спосіб кращий за попередній, оскільки він у більшості випадків ефективніший, вимагає менше часу. На конкретних прикладах продемонструємо роботу кожного із видів реалізації алгоритму.
Почнемо з того, в основі якого лежить операція взяття залишку від поділу. Маємо два числа: 112 і 32. Перше більше за друге – замінимо його залишком від поділу 112 на 32. Нова пара чисел включає 16 і 32. Друге більше, тому також замінимо його залишком від поділу 32 на 16, тобто нулем. В результаті отримуємо НОД = 16. Таблично це виглядає так:
А тепер складемо з тими самими числамитаблицю для алгоритму віднімання.
Наведений приклад продемонстрував, як в окремому випадку, віддавши перевагу поділу (взяття залишку від поділу) віднімання, можна виграти в швидкодії. Перевага розподілу стає видно найвиразніше після наступних міркувань. Припустимо, що A менше B, а так як НОД двох цілих чисел менше або дорівнює найменшому з них, то і тут він менше або дорівнює A; тому оптимальним буде вже за першої операції замінити B числом меншим чи рівним A.
Далі відомо, що в одному випадку більше число замінюється різницею його і меншого числа, а в іншому залишком від поділу. При розподілі B на A (більше на менше), залишок не може перевищувати число, що стоїть у знаменнику (тобто A), отже взяття залишку від розподілу гарантує оптимальний результат. Але те саме не можна сказати щодо операції віднімання, оскільки зовсім необов'язково, що відразу після виконання першого віднімання, B стане менше або дорівнює A. Наприклад, нехай A дорівнюватиме 150, а B - 1100. Так, використовуючи віднімання, ми в першій дії отримаємо B рівну 950, тоді як метод розподілу дасть 50.
Блок-схема алгоритму Евкліда поділом:
За винятком умови виходу з циклу та операцій у виразах, ця блок-схема аналогічна до попередньої. Досить те умова, у якому тіло циклу виконуватиметься до того часу, поки обидві змінних мають значення відмінні від нуля, оскільки, коли умова перестане бути істинним, то буде, що з теперішніх значень є шуканим найбільшим спільним дільником. Та й потім ніяк не можна допустити наступної ітерації, в якій буде зроблено спробу поділу на нуль.