İki ədədin ƏBOB-u (Həll təhlili)

Ən böyük ortaq bölən (ƏBOB) iki tam ədədin ən böyük natural ədədidir, hansını ki bu ədədlər bölür. Məsələn, ƏBOB(8, 12) = 4.

Məlumdur ki, ƏBOB(0, x) = |x| (ədədin modulu $x$), çünki $|x|$ $0$ və $x$ ədədlərini bölən ən böyük natural ədəddir. Məsələn, ƏBOB(-6, 0) = 6, ƏBOB(0, 5) = 5.

İki ədədin ƏBOB-nu tapmaq üçün təkrarlanan bir alqoritmdən istifadə etmək olar: kiçik ədədi böyükdən çıxarmaq lazımdır. Nəticədə ədədlərdən biri $0$ olduğunda, digəri ƏBOB olacaq. Məsələn: ƏBOB(10, 24) = ƏBOB(10, 14) = ƏBOB(10, 4) = ƏBOB(6, 4) = ƏBOB(2, 4) = ƏBOB(2, 2) = ƏBOB(2, 0) = 2.

Əgər 'çıxartma' əməliyyatı əvəzinə 'modul alma' əməliyyatını istifadə etsək, hesablamalar daha sürətli aparılacaq.

Məsələn, ƏBOB(1, 10^9) tapmaq üçün çıxartma istifadə edildikdə 10^9 əməliyyat lazımdır. Modul alma əməliyyatı istifadə edildikdə bir əməliyyat kifayətdir.

İki ədədin ƏBOB-nu aşağıdakı formul ilə hesablamaq olar:

və ya başqa:

Dövrü reallaşdırma sonuncu rekursiv münasibətdə göstərilən ideyaya əsaslanır:

while (b > 0) :
    hesabla a = a % b;
    dəyişkənlərin a və b-nin məzmununu dəyişir;

Alqoritmin reallaşdırılması

gcd funksiyası iki ədədin ƏBOB-nu hesablayır.

int gcd(int a, int b)
{
  if (a == 0) return b;
  if (b == 0) return a;
  if (a >= b) return gcd(a % b, b);
  return gcd(a, b % a);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d",&a,&b);

İki ədədin ƏBOB-nu hesablayıb ekrana çıxarırıq.

d = gcd(a,b);
printf("%d\n",d);

Alqoritmin reallaşdırılması — sadələşdirilmiş rekursiya

gcd funksiyası iki ədədin ƏBOB-nu hesablayır.

int gcd(int a, int b)
{
  return (!b) ? a : gcd(b,a % b);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d",&a,&b);

İki ədədin ƏBOB-nu hesablayıb ekrana çıxarırıq.

d = gcd(a,b);
printf("%d\n",d);

Alqoritmin reallaşdırılması — dövr

gcd funksiyası iki ədədin ƏBOB-nu hesablayır.

int gcd(int a, int b)
{
  while (b > 0)
  {
    a = a % b;
    int temp = a; a = b; b = temp;
  }
  return a;
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d",&a,&b);

İki ədədin ƏBOB-nu hesablayıb ekrana çıxarırıq.

d = gcd(a,b);
printf("%d\n",d);

Java reallaşdırılması

import java.util.*;

public class Main
{
  static int gcd(int a, int b)
  {
    if (a == 0) return b;
    if (b == 0) return a;
    if (a >= b) return gcd(a % b, b);
    return gcd(a, b % a);
  }
    
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int a = con.nextInt();
    int b = con.nextInt();
    
    int res = gcd(a, b);
    System.out.println(res);
    con.close();
  }
}

Python reallaşdırılması — rekursiya

gcd funksiyası iki ədədin ƏBOB-nu hesablayır.

def gcd(a, b):
  if a == 0: return b
  if b == 0: return a
  if a > b: return gcd(a % b, b)
  return gcd(a, b % a)

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

a, b = map(int, input().split())

İki ədədin ƏBOB-nu hesablayıb ekrana çıxarırıq.

print(gcd(a, b))

Python reallaşdırılması — gcd

İki ədədin ƏBOB-nu hesablamaq üçün Python dilinə inteqrasiya olunmuş gcd funksiyasından istifadə edəcəyik.

import math

Giriş məlumatlarını oxuyuruq.

a, b = map(int, input().split())

İki ədədin ƏBOB-nu hesablayıb ekrana çıxarırıq.

print(math.gcd(a, b))