Amaliy mashg‘ulot: funksiyalar va Yevklid algoritmi
Ikki sonning eng katta umumiy bo‘luvchisini (EKUB) tub ko‘paytuvchilarga ajratib topish kompyuter uchun qulay emas; Yevklid algoritmi esa qisqa va tez. Uning g‘oyasi: a ni b ga bo‘lib qoldiq olinadi, so‘ng (a, b) o‘rniga (b, qoldiq) olinadi; bu ish b nolga teng bo‘lguncha takrorlanadi va oxirida a EKUB bo‘ladi. Masalan, (84, 36) → (36, 12) → (12, 0), demak EKUB = 12. Pythonda bu ikki qatorli sikl (kod pastda) – bunda o‘rin almashtirish ham, qoldiq ham bir satrda bajariladi. EKUB topilgach, kasrni qisqartirish (ikkalasini EKUB ga bo‘lish) va EKUK = a * b // EKUB ni topish juda oson. Algoritm har doim to‘xtaydi, chunki qoldiq har gal kamayib boradi va oxiri nolga yetadi.
1while b != 0: 2 a, b = b, a % b
Sinf 48 sm × 72 sm to‘g‘ri to‘rtburchak e’lon taxtasini oraliqsiz bir xil kvadrat rasmlar bilan qoplamoqchi edi. Eng katta mumkin bo‘lgan tomon 48 va 72 ning eng katta umumiy bo‘luvchisi, ya’ni 24 sm, shuning uchun 6 ta rasm kerak bo‘ldi.
Matematiklar, dasturchilar va buxgalterlar kasrlarni soddalashtirib, hisobni qisqa va aniq qiladi.
Ikki sonning (masalan, 36 va 60) eng katta umumiy bo‘luvchisini qog‘ozda ayirish usulida toping. Natija bilan kasrni soddalashtiring.
1def ekub(a, b): 2 while b != 0: 3 a, b = b, a % b 4 return a 5print(ekub(84, 36))
12
1def ekub(a, b): 2 while b != 0: 3 a, b = b, a % b 4 return a 5g = ekub(18, 24) 6print(18 // g, 24 // g) 7 8def ekub(a, b): 9 while b != 0: 10 a, b = b, a % b 11 return a 12print(12 * 18 // ekub(12, 18))
3 4 36
«Qoldiq zanjiri»: juftliklar o‘z ikki sonini tanlab, (a, b) → (b, a % b) zanjirini daftarda yozadi va EKUB ni topadi; so‘ng dasturda tekshiradi.