Příklady různých způsobů výpočtu GCD dvou celých čísel (pro kladná i záporná celá čísla) pomocí smyček a rozhodnutí.
Abychom pochopili tento příklad, měli byste mít znalosti o následujících programovacích tématech jazyka C:
- Programovací operátoři C.
- C pro smyčku
- C pokud … jiné prohlášení
- C zatímco a dělat … zatímco Loop
HCF nebo GCD dvou celých čísel je největší celé číslo, které dokáže přesně rozdělit obě čísla (bez zbytku).
Existuje mnoho způsobů, jak najít největšího společného dělitele v programování C.
Příklad č. 1: GCD Použití příkazu for loop a 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; )
V tomto programu jsou dvě celá čísla zadaná uživatelem uložena v proměnných forn1 a n2. Poté je smyčka iterována, dokud není i menší než n1 a n2.
Pokud jsou v každé iteraci n1 a n2 přesně dělitelné i, je hodnota i přiřazena gcd.
Když je forsmyčka dokončena, největší společný dělitel dvou čísel je uložen v proměnné gcd.
Příklad č. 2: GCD Použití smyčky while a 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; )
Výstup
Zadejte dvě kladná celá čísla: 81 153 GCD = 9
Toto je lepší způsob, jak najít GCD. V této metodě se menší celé číslo odečte od většího celého čísla a výsledek se přiřadí proměnné obsahující větší celé číslo. Tento proces pokračuje, dokud n1 a n2 nejsou stejné.
Výše uvedené dva programy fungují, jak bylo zamýšleno, pouze pokud uživatel zadá kladná celá čísla. Zde je malá úprava druhého příkladu, jak najít GCD pro pozitivní i negativní celá čísla.
Příklad č. 3: GCD pro kladná i záporná čísla
#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; )
Výstup
Zadejte dvě celá čísla: 81 -153 GCD = 9
K vyhledání GCD můžete také použít rekurzi.
