DSA Evklid algoritmi

Evklid algoritmi

Evklid algoritmi ikki son \(a\) va \(b\) ning eng katta umumiy bo‘luvchisini (EKUB) topadi.

Eng katta umumiy bo‘luvchi — \(a\) ni ham, \(b\) ni ham qoldiqsiz bo‘ladigan eng katta son.

Algoritm qoldiqli bo‘lishdan foydalanadi. U keyingi qadamdagi hisoblashni tuzish uchun oldingi qadamdagi qoldiqni oladi.

Evklid algoritmini qo‘lda va dasturlash orqali qanday bajarish mumkinligini ko‘rish hamda algoritm aslida qanday va nima uchun ishlashini tushunish uchun o‘qishda davom eting.

Matematik atamalar

Quyida Evklid algoritmini tavsiflashda ishlatiladigan so‘zlar keltirilgan — bu sahifadagi tushuntirishlarni tushunish uchun ularni bilishingiz kerak.

Bo‘luvchi: Biror sonni qoldiqsiz bo‘lish mumkin bo‘lgan son. 3 soni 6 ning bo‘luvchisi deymiz, chunki \(6/3=2\) bo‘lib, qoldiq qolmaydi (qoldiq 0 ga teng).

Qoldiq: Bir sonni boshqa songa bo‘lgandan keyin qoladigan qism. 7 ni 3 ga bo‘lsak, 2 chiqadi va 1 qoldiq qoladi. (Demak, 3 soni 7 ning bo‘luvchisi emas.)

Umumiy bo‘luvchi: \(a\) va \(b\) sonlari uchun umumiy bo‘luvchi — \(a\) ni ham, \(b\) ni ham qoldiqsiz bo‘la oladigan son. 18 va 12 ning umumiy bo‘luvchilari 2, 3 va 6, chunki 18 ni ham, 12 ni ham 2, 3 va 6 ga qoldiqsiz bo‘lish mumkin.

Eng katta umumiy bo‘luvchi: Umumiy bo‘luvchilarning eng kattasi. 18 va 12 ning eng katta umumiy bo‘luvchisi 6 ga teng, chunki u 2, 3 va 6 umumiy bo‘luvchilarining eng kattasi.

Eng katta umumiy bo‘luvchi matematikaning sonlar nazariyasi sohasida hamda xabarlarni shifrlash uchun kriptografiyada qo‘llaniladi.

Qo‘lda bajarib ko‘rish

Evklid algoritmi qanday ishlashini tushunish va uning kodini yozish uchun avval uni \(120\) va \(25\) ning eng katta umumiy bo‘luvchisini topish uchun qo‘lda bajarib ko‘raylik.

Buning uchun qoldiqli bo‘lishdan foydalanamiz.

1-qadam: \(120\) ni \(25\) ga bo‘lishdan boshlaymiz:

\[ \begin{equation} \begin{aligned} 120 & = 4 \cdot 25 + 20 \end{aligned} \end{equation} \]

\(120\) ichiga \(25\) necha marta sig‘adi? \(4\) marta, to‘g‘rimi? \(4 \cdot 25\) \(100\) ga teng. \(120\) dan \(100\) ni ayirib, \(20\) qoldiqni olamiz.

2-qadam: Keyingi qadamda \(25\) ni bo‘lish uchun oldingi qoldiq \(20\) dan foydalanamiz:

\[ \begin{equation} \begin{aligned} 25 & = 1 \cdot 20 + 5 \end{aligned} \end{equation} \]

\(25\) ichiga \(20\) bir marta sig‘adi. \(25\) dan \(20\) ni ayirib, \(5\) qoldiqni olamiz.

3-qadam: Keyingi hisoblashda \(20\) ni oldingi qoldiq \(5\) ga bo‘lamiz:

\[ \begin{equation} \begin{aligned} 20 & = 4 \cdot 5 + 0 \end{aligned} \end{equation} \]

Qoldiq sifatida \(0\) ni olamiz, bu esa hisob-kitoblar tugaganini bildiradi.

\(120\) va \(25\) ning eng katta umumiy bo‘luvchisi \(5\) ga teng.

Evklid algoritmini amalga oshirish

Eng katta umumiy bo‘luvchini bo‘lish yordamida topish uchun hisoblangan qoldiq \(0\) bo‘lguncha algoritmni ishlatishda davom etamiz.

Bu \(b\) \(0\) ga teng bo‘lmagan ekan, algoritmni ishlatishda davom etamiz deyish bilan bir xil. Shuning uchun quyidagi while siklida b != 0 shart sifatida ishlatilgan.

def gcd_division(a, b):
    while b != 0:
        remainder = a % b
        print(f"{a} = {a//b} * {b} + {remainder}")
        a = b
        b = remainder
    return a

a = 120
b = 25
print("The Euclidean algorithm using division:\n")
print(f"The GCD of {a} and {b} is: {gcd_division(a, b)}")

Asl Evklid algoritmi

Yuqorida qilganimizdek bo‘lishdan foydalanish o‘rniga, 2000 yildan ko‘proq vaqt oldin "Negizlar" kitobida tasvirlangan asl Evklid algoritmi ayirishdan foydalanadi.

Bo‘lish o‘rniga ayirishdan foydalanish unchalik tez emas, lekin bo‘lish usuli ham, ayirish usuli ham bir xil matematik tamoyildan foydalanadi:

Buni bir necha qatorda ko‘rsatish mumkin.

\(a\) va \(b\) sonlari \(x\) eng katta umumiy bo‘luvchiga ega.

Bu \(a\) ni ham, \(b\) ni ham quyidagicha ko‘paytuvchilarga ajratish mumkinligini anglatadi:

\[ \begin{equation} \begin{aligned} a & = k \cdot x \\ b & = l \cdot x \end{aligned} \end{equation} \]

Ko‘paytuvchilarga ajratgandan keyin \(a\) dan \(b\) ni ayirish bizga juda qiziq natija beradi:

\[ \begin{equation} \begin{aligned} a-b & = k \cdot x - l \cdot x \\ & = (k-l) \cdot x \end{aligned} \end{equation} \]

Ko‘ramizki, \(a\) va \(b\) ning eng katta umumiy bo‘luvchisi (\(x\)) \(a\) va \(b\) orasidagi ayirmaning ham eng katta umumiy bo‘luvchisidir!

Evklid algoritmi aynan shu tamoyil tufayli ishlaydi — uni amalga oshirishni mumkin qiladigan narsa shu.

Eng katta umumiy bo‘luvchini ayirish yordamida topish

Yuqorida tasvirlangan tamoyildan, ya’ni \(a\) va \(b\) orasidagi ayirma ham xuddi shu eng katta umumiy bo‘luvchiga ega ekanidan foydalanib, Evklidning asl algoritmi kabi eng katta umumiy bo‘luvchini ayirish yordamida topishimiz mumkin.

Keling, ayirish yordamida \(120\) va \(25\) ning eng katta umumiy bo‘luvchisini topaylik.

\[ \begin{equation} \begin{aligned} 120 - 25 & = 95 \end{aligned} \end{equation} \]

Yuqorida tasvirlangan matematik tamoyilga ko‘ra, \(120\), \(25\) va \(95\) sonlarining barchasi bir xil eng katta umumiy bo‘luvchiga ega.

Bu \(95\) dan \(25\) ni ayirib, masalani yanada soddalashtirishimiz mumkinligini anglatadi:

\[ \begin{equation} \begin{aligned} 95 - 25 & = 70 \end{aligned} \end{equation} \]

Shu tarzda, har doim oldingi qadamdagi eng kichik ikki sonni olib, ular orasidagi ayirmani topib davom etsak, quyidagi hisob-kitoblarni olamiz:

\[ \begin{equation} \begin{aligned} 70 - 25 & = 45 \\ 45 - 25 & = 20 \\ 25 - 20 & = 5 \\ 20 - 5 & = 15 \\ 15 - 5 & = 10 \\ 10 - 5 & = \underline{\textbf{5}} \\ 5 - 5 & = 0 \end{aligned} \end{equation} \]

Ayirishga asoslangan Evklid algoritmi ayirma \(0\) bo‘lganda yakunlanadi.

\(120\) va \(25\) ning eng katta umumiy bo‘luvchisini oldingi qadamda topish mumkin, u \(5\) ga teng.

Endi eng katta umumiy bo‘luvchini ayirish yordamida qo‘lda hisoblay olganimizdan so‘ng, uni dasturlash tilida amalga oshirish osonroq.

Evklid algoritmini ayirish yordamida amalga oshirish

Eng katta umumiy bo‘luvchini ayirish yordamida topish uchun, hozirgina ko‘rganimizdek, \(a\) va \(b\) orasidagi ayirma \(0\) bo‘lguncha algoritmni ishlatishda davom etamiz.

Bu \(a\) va \(b\) turli qiymatlar bo‘lib turgan ekan, algoritmni ishlatishda davom etamiz deyish bilan bir xil. Shuning uchun quyidagi while siklida a != b shart sifatida ishlatilgan.

def gcd_subtraction(a, b):
    while a != b:
        if a > b:
            print(f"{a} - {b} = {a-b}")
            a = a - b
        else:
            print(f"{b} - {a} = {b-a}")
            b = b - a
    return a

a = 120
b = 25
print("The Euclidean algorithm using subtraction:\n")
print(f"The GCD of {a} and {b} is: {gcd_subtraction(a, b)}")

Ayirish usulini bo‘lish usuli bilan solishtirish

Eng katta umumiy bo‘luvchini topishda bo‘lish usuli qanchalik samarali bo‘lishi mumkinligini va usullar bir-biriga qanday o‘xshashligini ko‘rish uchun biz:

1. \(120\) va \(25\) ning eng katta umumiy bo‘luvchisini ayirish yordamida topamiz.
2. \(120\) va \(25\) ning eng katta umumiy bo‘luvchisini qoldiqli bo‘lish yordamida topamiz.
3. Ayirish va bo‘lish usullarini solishtiramiz.

1. Ayirish yordamida

\(120\) va \(25\) ning eng katta umumiy bo‘luvchisini ayirish yordamida topish:

\[ \begin{equation} \begin{aligned} 120 - 25 & = 95 \\ 95 - 25 & = 70 \\ 70 - 25 & = 45 \\ 45 - 25 & = 20 \\ 25 - 20 & = 5 \\ 20 - 5 & = 15 \\ 15 - 5 & = 10 \\ 10 - 5 & = \underline{\textbf{5}} \\ 5 - 5 & = 0 \end{aligned} \end{equation} \]

Ayirishdan foydalanilganda algoritm ayirma \(0\) bo‘lganda yakunlanadi.

Oxiridan bitta oldingi hisoblashda \(120\) va \(25\) ning eng katta umumiy bo‘luvchisi \(5\) ekanini ko‘ramiz.

E’tibor bering, EKUB topilguncha \(25\) va \(5\) ko‘p marta ayirilishi kerak.

2. Bo‘lish yordamida

\(120\) va \(25\) ning eng katta umumiy bo‘luvchisini qoldiqli bo‘lish yordamida topish quyidagicha ko‘rinadi:

\[ \begin{equation} \begin{aligned} 120 & = 4 \cdot 25 + 20 \\ 25 & = 1 \cdot 20 + \underline{\textbf{5}} \\ 20 & = 4 \cdot 5 + 0 \end{aligned} \end{equation} \]

Bo‘lishdan foydalanilganda Evklid algoritmi qoldiq \(0\) bo‘lganda yakunlanadi.

Oldingi qoldiq \(5\) — \(120\) va \(25\) ning eng katta umumiy bo‘luvchisi.

3. Solishtirish

Yuqoridagi ayirish va bo‘lish usullariga nazar tashlang.

Bo‘lish hisob-kitoblari aslida ayirish hisob-kitoblari bilan deyarli bir xil ekanini osonroq ko‘rish uchun qoldiqli bo‘lish hisob-kitoblarini quyidagicha yozishimiz mumkin:

\[ \begin{equation} \begin{aligned} 120 - 4 \cdot 25 & = 20 \\ 25 - 1 \cdot 20 & = \underline{\textbf{5}} \\ 20 - 4 \cdot 5 & = 0 \end{aligned} \end{equation} \]

Ayirish usulida \(25\) soni \(120\) dan jami \(4\) marta ayiriladi, bo‘lish usuli esa buni bitta qadamda bajaradi.

Xuddi shunday, ayirish usuli \(5\) ni jami \(4\) marta ayiradi, bo‘lish usuli esa xuddi shu ishni bitta hisoblashda bajaradi.

Ko‘rib turganingizdek, ikkala usul ham bir xil ishni bajaradi, faqat bo‘lish usuli ko‘plab ayirishlarni bitta hisoblashda bajaradi va shu sababli eng katta umumiy bo‘luvchini tezroq topadi.