Mavzu: Yevklid algoritmi

Mavzu: Yevklid algoritmi
Evklid algoritmi, Evklid algoritmi sifatida ham tanilgan, ikkita butun sonning eng katta umumiy bo'luvchisini (GCD) hisoblashning samarali usuli hisoblanadi. Uni birinchi marta Evklid o'zining "Elementlar" asarida (miloddan avvalgi 300 yil) tasvirlab bergan [4]. Algoritm ikkita raqamning GCD kattaroq raqam kichikroq raqam bilan farqiga almashtirilsa, o'zgarmasligi printsipiga asoslanadi
Evklidning elementlari (qadimgi yunoncha:Stoičeῖa Stoikheîa ) 13 kitobdan iborat matematik risolabo'lib, qadimgi yunonmatematigiEvklidga tegishli Iskandariya, Ptolemeydavridagi Misrda mil Miloddan avvalgi 300 yil. Buta'riflar, postulatlar, takliflar (teoremalar va konstruktsiyalar) va takliflarning matematikdalillari to'plamidir . Kitoblarda tekislik va qattiq Evklidgeometriyasi , elementar sonlarnazariyasi va tengsiz chiziqlar. Elementlar matematikaning eng qadimgi keng ko'lamli deduktiv muolajasidir . U mantiq va zamonaviy ilm-fanning rivojlanishida muhim rol o'ynadi va uning mantiqiy qat'iyligi 19-asrgacha oshmadi.
Evklidning elementlari hozirgacha yozilgan eng muvaffaqiyatli va ta'sirli darslik deb nomlanadi.Bumatbaaixtirosidan keyin chop etilgan eng dastlabki matematik asarlardan biri bo'lib , 1482 yilda birinchi bosmadan beri chop etilgan nashrlar soni bo'yicha Injildan keyin ikkinchi o'rinda turadi mingdan ortiq. Asrlar davomida, kvadrivium barcha universitet talabalari o'quv dasturiga kiritilganida, Evklid elementlarining kamida bir qismini bilishbarcha talabalardan talab qilingan. Faqat 20-asrgacha, uning mazmuni boshqa maktab darsliklari orqali universal tarzda o'rgatildi, u barcha ma'lumotli odamlar o'qigan narsa deb hisoblanmaydi.
Evklid algoritmi ketma-ket bosqichlarda davom etadi, har bir qadamning natijasi keyingi bosqich uchun kirish sifatida ishlatiladi. Butun son hisoblagich yordamida qadamlarni kuzatib boring k , shuning uchun boshlang'ich qadam k = 0 ga, keyingi qadam k = 1 ga to'g'ri keladi va hokazo.
Har bir qadam r _k -2 > r _k -1 bo'lgan ikkita manfiy bo'lmagan qoldiqlar r _k -2 va r _k -1 bilan boshlanadi . K -bosqichda q _k qism va r _k qoldiqni topish uchun qoldiqga bo'lish amalga oshiriladi , shunday qilib:
��−2=����−1+�� bilan ��−1>��≥0.
Ya'ni, kichik r _{k -1 sonining ko'paytmalari katta} r _{k -2 sondan} r _k qoldiq r _k -1 dan kichik bo'lguncha ayiriladi . Keyin algoritm r _k -1 va r _k dan boshlanadigan ( k +1)-bosqichga o'tadi .
Dastlabki bosqichda k = 0, qoldiqlar r _-2 = a va r _-1 = b ga o'rnatiladi , ular uchun GCD qidiriladi. Keyingi bosqichda k = 1, qoldiqlar r _-1 = b va qolgan r ₀ boshlang'ich qadam va hokazo. Algoritm tenglamalar ketma-ketligida davom etadi
�=�0�+�0�=�1�0+�1�0=�2�1+�2�1=�3�2+�3⋮
Agar a < b bo'lsa, algoritmni o'zgartirish shart emas : u holda, boshlang'ich qism q ₀ = 0, birinchi qoldiq r ₀ = a , bundan buyon barcha k ≥ 1 uchun r _k -2 > r _k -1 .
Qolganlar har qadamda kamayib boruvchi manfiy bo'lmagan butun sonlar bo'lgani uchun ketma-ketlik�−1>�0>�1>�2>⋯≥0  cheksiz bo'lishi mumkin emas , shuning uchun algoritm oxir-oqibat keyingi bosqichni ishlab chiqara olmaydi; lekin boʻlinish algoritmi har doim taqdim etilgan ( N +1)-chi bosqichga oʻtishi mumkin r _N > 0. Shunday qilib, algoritm oxir-oqibat r _N = 0 nol qoldiqni hosil qilishi kerak ^{. [13]} Yakuniy nolga teng boʻlmagan qoldiq aning eng katta umumiy boʻluvchisidir. va b :