Redaksiya

Alqoritm Analizi

İki tam ədədin ən böyük ümumi böləni (ƏBÜB) ən böyük təbii ədəd kimi təriflənir ki, hər iki ədədi bölür. Məsələn, ƏBÜB(8, 12) = 4.

Məlumdur ki, ƏBÜB(0, $x$) = $|x|$ ($x$-in mütləq dəyəri), çünki $|x|$ 0 və $x$-i bölən ən böyük təbii ədəddir. Məsələn, ƏBÜB(-6, 0) = 6, ƏBÜB(0, 5) = 5.

İki ədədin ƏBÜB-ni tapmaq üçün iterativ alqoritm istifadə edilə bilər: kiçik ədədi böyükdən çıxarın. Ədədlərdən biri 0 olarkən, digəri ƏBÜB olur. Məsələn: ƏBÜB(10, 24) = ƏBÜB(10, 14) = ƏBÜB(10, 4) = ƏBÜB(6, 4) = ƏBÜB(2, 4) = ƏBÜB(2, 2) = ƏBÜB(2, 0) = 2.

Əgər 'çıxarma' əməliyyatı yerinə modul əməliyyatı istifadə edilsə, hesablama daha sürətli olar.

Məsələn, ƏBÜB(1, $10^9$) tapmaq üçün çıxarma istifadə edilərsə, $10^9$ əməliyyat tələb olunar. Modul əməliyyatı istifadə edilərsə, yalnız bir əməliyyat tələb olunar.

İki ədədin ƏBÜB-ni hesablamaq üçün formula:

Dövrə əsaslanan həyata keçirilmə son təkrarlı əlaqədə təqdim edilən fikrə əsaslanır:

while (b > 0) :
    hesabla a = a % b;
    dəyişənlərin məzmununu dəyişdir;

Alqoritm Həyata Keçirilməsi

Funksiya gcd iki ədədin ƏBÜB-ni 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ı oxuyun.

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

İki ədədin ƏBÜB-ni hesablayın və göstərin.

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

Alqoritm Həyata Keçirilməsi – Sadələşdirilmiş Rekursiya

Funksiya gcd iki ədədin ƏBÜB-ni hesablayır.

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

Alqoritm Həyata Keçirilməsi – Dövr

Funksiya gcd iki ədədin ƏBÜB-ni hesablayır.

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

Java Həyata Keçirilməsi

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 Həyata Keçirilməsi – Rekursiya

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)

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

Python Həyata Keçirilməsi – gcd

İki ədədin ƏBÜB-ni hesablamaq üçün Python-da quraşdırılmış gcd funksiyasından istifadə edəcəyik.

import math

a, b = map(int, input().split())
print(math.gcd(a, b))