Amaliy mashg‘ulotlarni bajarish buyicha uslubiy ko’rsatmalar. Amaliy mashg’ulot. Mavzu

GCDni topish uchun Evklid algoritmi

Evklid algoritmi ikkita musbat son uchun eng katta umumiy bo'luvchini hisoblashni osonlashtiradi. Evklid algoritmining formulalari va isbotini “Eng katta umumiy bo‘luvchi: aniqlovchi, misollar” bo‘limida keltirdik.
Algoritmning mohiyati qoldiq bilan bo'linishni ketma-ket bajarishdir, bunda shaklning bir qator tengliklari olinadi:
a = b q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
Biz bo'linishni qachon tugatishimiz mumkin r k + 1 = 0, unda r k = gcd (a, b).
1-misol
64 va 48 .
Yechim
Belgilashni kiritamiz: a = 64, b = 48.
Evklid algoritmiga asoslanib, biz bo'linishni amalga oshiramiz 64 yoqilgan 48 .
Biz 1 ni va qolgan 16 ni olamiz. Ma’lum bo‘lishicha, q 1 = 1, r 1 = 16.
Ikkinchi bosqichda biz ajratamiz 48 16 ga kelib, biz 3 ni olamiz. Ya'ni q 2 = 3, a r 2 = 0. Shunday qilib, 16 raqami shartdagi raqamlar uchun eng katta umumiy bo'luvchidir.
Javob: GCD (64, 48) = 16.
2-misol
Raqamlar GCD nima 111 va 432 ?
Yechim
Bo'lmoq 432 yoqilgan 111 ... Evklid algoritmiga ko'ra, 432 = 111 3 + 99, 111 = 99 1 + 12, 99 = 12 8 + 3, 12 = 3 4 tenglik zanjirini olamiz.
Shunday qilib, raqamlarning eng katta umumiy bo'luvchisi 111 va 432 3.
Javob: GCD (111, 432) = 3.
3-misol
661 va 113 sonlarining eng katta umumiy maxrajini toping.
Yechim
Keling, raqamlarning ketma-ket bo'linishini amalga oshiramiz va gcd ni olamiz (661 , 113) = 1 ... Bu 661 va 113 sonlar koʻproq tub sonlar ekanligini bildiradi. Agar biz tub sonlar jadvaliga qarasak, hisobni boshlashdan oldin buni aniqlab olishimiz mumkin.
Javob: GCD (661, 113) = 1.