1-amaliy mashg'ulot. Sonlarni EKUBini hisoblash algoritmlari. Evklid algoritmi.
Reja:
Evklid algoritmi.
Kengaytirilgan evklid algoritmi.
Evklid algoritmi.
a, b a==b EKUB(a, b) = a || b
a, b a!=b a > b a = b*q1 + r1, 0 r1 < b, agar r1=0 bo‘lsa, EKUB(a,b) = b, aks holda r1!=0
b = r1*q2 +r2 0 r2 < r1, agar r2 = 0 bo‘lsa, EKUB(a,b)=r1, aks holda r2!=0
r1 = r2*q3 + r3 0 r3 < r2, r3 = 0, EKUB(a,b)=r2
r3!=0
…… rk = 0 EKUB(a, b) = rk-1
Kengaytirilgan evklid algoritmi.
a, b natural sonlar uchun d = EKUB(a, b)
a + b = d, berilgan sonlarning oldidagi koefitsenti
qadam
a = b*q1 + r1,
b = r1*q2 +r2,
r1 = r2*q3 + r3,
qadam
a = b*q1 + r1, a - b*q1 = r1
b = r1*q2 +r2, b - r1*q2 = r2
r1 = r2*q3 + r3, r1 - r2*q3 = r3
qadam.
r3 = r1 - r2*q3 = r1 – (b - r1*q2) * q3 = r1 – b * q3 + r1*q2*q3 = r1*(1 + q2*q3) – b * q3 = (a – b * q1)*( 1 + q2*q3) – b * q3 = a*(1 + q2*q3)-b*q1-b*q1*q2*q3-b*q3= >
a*(1 + q2*q3)-b*(q1+q1*q2*q3+q3) = d.
1 + q2*q3, q1+q1*q2*q3+q3
1-misol
453, 17 berilgan natural sonlar bo‘lsin. Bu sonlarni ENG KATTA UMUMIY BO ‘LUVCHISI (EKUB)ni topish kerak bo‘lsin, bunda Evklid algoritmidan foydalanamiz.
Qadam.
453 = 17 26 + 11
17 = 11
qoldiq 0 bo‘lganligi sabab Evklid algoritmga ko‘ra EKUB (453, 17) = 1 bo‘lishini ko‘ramiz.
2-misol
453, 17 berilgan natural sonlar bo‘lsin. Bu sonlarni oldidagi koefitsentini toping.
qadam
453 = 17 26 + 11
17 = 11
qadam
453 = 17 26 + 11, 11
17 = 11
Qadam
2-amaliy mashg'ulot. Sonlarni EKUBini Pythonda hisoblashning Evklid algoritmi dasturi
Dostları ilə paylaş: |