Ikki sonning EKUBini topish. Yevkilid algoritmi
Algorithms Uzbekistan
"Mathematics is the queen of the sciences and number theory is the queen of mathematics." - Carl Friedrich Gauss
II qism. 1-dars:
Ikkinchi qism, Sonlar nazariyasi bo'limining birinchi darsida sizlar bilan ikki sonning EKUBini topishni ko'rib o'tamiz.
- Berilgan ikki son ega bo’lgan eng katta umumiy bo’luvchi EKUB deb ataladi.
EKUB ni topishning eng oddiy usulini maktab darsliklarida ko'rsatib o'tilgan, bunda ikkala sonni tub bo’luvchilarga ajratiladi va ulardan umumiylarini ko’paytirib chiqiladi
Masalan: 16 = 2*2*2*2
76 = 2*2*19
EKUB = 2*2 = 4
Lekin, dasturlashda bu usuldan foydalanish noqulay va nisbatan sekin. Chunki, avval, har bir sonni tub ko'paytuvchilarga ajratish kerak. Keyin har biridan umumiylarini topib chiqish kerak.
Shuning uchun dasturlashda boshqa samaraliroq va tezroq usul bo'lgan Yevklid algoritmidan foydalaniladi.
Yevklid algoritmi.
Yevklid algoritmi ikkita qoidaga asoslanadi:
- Ikkita sondan kattasidan kichigi ayrilganda ularning EKUBi o’zgarmaydi
Yuqoridagi misoldagi 76 va 16 ning shu tarzda EKUBini topib ko'raylik. Bunda 76 dan 16 ayirma 16 dan kichik bo'lib qolguncha ayrib boriladi. Ayirma 16 dan kichik bo'lib qolgan payt ularning o'rni almashtiriladi
76 - 16 = 60
60 - 16 = 44
44 - 16 = 28
28-16 = 12
16 - 12 = 4
Shu tarzda yakunda biz EKUBga ega bo'lamiz.
Muammo: Agar sonlar 1 000 000 va 2 bo’lsachi? Unda algoritm 500 000 dan ortiq amal bajarishiga to'g'ri keladi. Ikki son orasidagi farq oshgani sari algoritm bajaradigan ish ham keskin ortib ketadi.
2. Qadamlar sonini kamaytirish uchun ayrish o’rniga qoldiqli bo’lishdan foydalanish mumkin. Bunda 1 000 000 va 2 sonlarining EKUBi atiga bir-ikkita amal bilan topiladi.
Yevklid algoritmi qadamlari:
- Ikkita sondan kattasini kichigiga bo’lib qoldiq olamiz.
- Ularni o’rnini almashtiramiz
- 1- va 2-qadamlarni sonlardan biri nol bo’lib qolguncha davom ettiramiz
- Qolgan son shu ikki son uchun EKUB bo’ladi.
Algoritm implementatsiyasi videosiga o'tishdan oldin. Uning dasturini o'zingiz mustaqil yozib ko'rishni maslahat beramiz.
Yevklid algoritmi qay tarzda ishlaydi. (Geometrik tushuntirish)
Bilamizki, Yevklid geometriya fani olimi bo'lgan shuning uchun u yaratgan algoritmni geometriya orqali tushuntirib berishga harakat qilamiz.
Misol: 38 va 16 sonlarining EKUBini Yevklid algoritmi yordamida toping.
Keling tomonlari 38 va 16 bo'lgan to'g'ri to'rtburchak chizib olamiz.
Endi bu to'rtburchakdan tomoni 16 ga teng bo'lgan kvadratlarni ajratib olamiz.
Bu narsa bizga 38 ni 16 ga bo'lgandagi butun va qoldiq qismni vizual ko'rsatib beradi. Ya'ni:
O'ng tarafdagi bo'yalmagan qism bizdagi qoldiqni (6) ifodalaydi. Endi yuqoridagi ishni o'sha 16 ga 6 tomonli to'g'ri to'rtburchak uchun davom ettiramiz.
Huddi yuqoridagidek:
Shu tarzda qoldiq nolga tenglashguncha davom etamiz.
Shu joyda algoritm o'z ishini yakunlaydi va eng kichik kvadrat tomoni (2) bizga 38 va 16 uchun EKUBni beradi.
Bu holatda tomoni to'g'ri to'rtburchak tomonlari EKUBiga teng bo'lgan kvadrat shu to'g'ri to'rtburchakning barcha sohasini to'ldirib chiqa oladigan eng katta tomonli kvadrat.
Shu bilan bugungi darsimizni yakunlaymiz va keyingi darsimizda Yevklid algoritmini realizatsiyani ko'rib chiqamiz.
Maqolani foydali deb hisoblasangiz uni do'stlaringizga ham ulashing.
Manba: @AlgorithmUz telegram kanali
YouTube kanalimiz: Algorithms Uzbekistan
"Eng yaxshi reklama - bu mamnun mijoz tomonidan qilingan reklama" - Philip Kotler