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

Amaliy mashg‘ulotlarni bajarish buyicha uslubiy ko’rsatmalar.
Amaliy mashg’ulot.
Mavzu: Algoritmning asosiy xossalari. Evklid algoritmi
Misol. 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 Evklid algoritmidan foydalaniladi.
Evklid algoritmi.
Evklid algoritmi ikkita qoidaga asoslanadi:

1. 
   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.
Evklid algoritmi qadamlari:

1. 
   Ikkita sondan kattasini kichigiga bo’lib qoldiq olamiz.
   
2. 
   Ularni o’rnini almashtiramiz
   
3. 
   1- va 2-qadamlarni sonlardan biri nol bo’lib qolguncha davom ettiramiz
   
4. 
   Qolgan son shu ikki son uchun EKUB bo’ladi.
   

Evklid algoritmi qay tarzda ishlaydi. (Geometrik tushuntirish)
Bilamizki, Evklid geometriya fani olimi bo'lgan shuning uchun u yaratgan algoritmni geometriya orqali tushuntirib berishga harakat qilamiz.