Приклади різних способів обчислення GCD двох цілих чисел (як для додатних, так і для негативних цілих чисел) за допомогою циклів та операторів прийняття рішень
Щоб зрозуміти цей приклад, ви повинні знати такі теми програмування на С:
- C Оператори програмування
- C для петлі
- C if… else Заява
- C в той час як і робити … поки Loop
HCF або GCD з двох цілих чисел є найбільшим цілим числом, яке може точно розділити обидва числа (без залишку).
Є багато способів знайти найбільший спільний дільник у програмуванні на С.
Приклад №1: Застосування GCD для циклу for та if
#include int main() ( int n1, n2, i, gcd; printf("Enter two integers: "); scanf("%d %d", &n1, &n2); for(i=1; i <= n1 && i <= n2; ++i) ( // Checks if i is factor of both integers if(n1%i==0 && n2%i==0) gcd = i; ) printf("G.C.D of %d and %d is %d", n1, n2, gcd); return 0; )
У цій програмі два цілі числа, введені користувачем, зберігаються у змінних n1 та n2. Потім forцикл повторюється, поки i не менше n1 та n2.
У кожній ітерації, якщо і n1, і n2 точно діляться на i, значення i присвоюється gcd.
Коли forцикл завершено, найбільший спільний дільник двох чисел зберігається у змінній gcd.
Приклад №2: GCD Використання циклу while та if … else Заява
#include int main() ( int n1, n2; printf("Enter two positive integers: "); scanf("%d %d",&n1,&n2); while(n1!=n2) ( if(n1> n2) n1 -= n2; else n2 -= n1; ) printf("GCD = %d",n1); return 0; )
Вихідні дані
Введіть два натуральних числа: 81 153 GCD = 9
Це кращий спосіб знайти GCD. У цьому методі менше ціле число віднімається від більшого цілого, а результат присвоюється змінній, що містить більше ціле число. Цей процес продовжується до тих пір, поки n1 і n2 не зрівняються.
Зазначені дві програми працюють за призначенням лише в тому випадку, якщо користувач вводить додатні цілі числа. Ось невеличка модифікація другого прикладу, щоб знайти GCD як для позитивних, так і для негативних цілих чисел.
Приклад №3: GCD як для позитивних, так і для негативних чисел
#include int main() ( int n1, n2; printf("Enter two integers: "); scanf("%d %d",&n1,&n2); // if user enters negative number, sign of the number is changed to positive n1 = ( n1> 0) ? n1 : -n1; n2 = ( n2> 0) ? n2 : -n2; while(n1!=n2) ( if(n1> n2) n1 -= n2; else n2 -= n1; ) printf("GCD = %d",n1); return 0; )
Вихідні дані
Введіть два цілих числа: 81 -153 GCD = 9
Ви також можете використовувати рекурсію для пошуку GCD.
