У цьому прикладі ви навчитеся знаходити GCD двох чисел за допомогою двох різних методів: функції та циклів та алгоритму Евкліда
Щоб зрозуміти цей приклад, ви повинні знати наступні теми програмування на Python:
- Функції Python
- Рекурсія Python
- Аргументи функції Python
Найвищий загальний коефіцієнт (HCF) або найбільший спільний дільник (GCD) двох чисел - це найбільше натуральне число, яке ідеально ділить ці два числа. Наприклад, HCF 12 та 14 дорівнює 2.
Вихідний код: Використання циклів
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Вихідні дані
HCF становить 6
Тут дві цілі числа, що зберігаються у змінних num1 та num2, передаються compute_hcf()функції. Функція обчислює HCF ці два числа і повертає їх.
У функції ми спочатку визначаємо менше з двох чисел, оскільки HCF може бути лише меншим чи рівним найменшому числу. Потім ми використовуємо forцикл для переходу від 1 до цього числа.
У кожній ітерації ми перевіряємо, чи наше число ідеально ділить обидва вхідні числа. Якщо так, ми зберігаємо число як HCF. Після завершення циклу ми отримуємо найбільше число, яке ідеально ділить обидва числа.
Вищевказаний метод легко зрозуміти та застосувати, але не ефективний. Набагато більш ефективним методом пошуку HCF є алгоритм Евкліда.
Алгоритм Евкліда
Цей алгоритм заснований на тому, що HCF двох чисел також ділить їх різницю.
У цьому алгоритмі ми ділимо більші на менші і беремо решту. Тепер розділіть менший на цей залишок. Повторюйте, поки залишок не дорівнює 0.
Наприклад, якщо ми хочемо знайти HCF 54 і 24, ми ділимо 54 на 24. Залишок дорівнює 6. Тепер, ми ділимо 24 на 6, а залишок дорівнює 0. Отже, 6 є необхідним HCF
Вихідний код: Використання евклідового алгоритму
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Тут ми цикл, поки y не стане нулем. Оператор x, y = y, x % yзамінює значення в Python. Клацніть тут, щоб дізнатись більше про заміну змінних у Python.
У кожній ітерації ми розміщуємо значення y у x, а залишок - (x % y)у одночасно. Коли y стає нулем, ми маємо HCF в x.
