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

Misol: 38 va 16 sonlarining EKUBini Evklid 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.

Evklid algoritmining g'oyasi

Bu algoritmning g‘oyasi agar M> N bo‘lsa, degan xususiyatga asoslangan (ikkita natural sonning eng katta umumiy bo'luvchisi GCD)
GCD (M, N) = GCD (M - N, N).
Boshqacha qilib aytganda, ikkita natural sonning GCD si ularning musbat farqi (ularning farq moduli) va undan kichikroq sonning GCD ga teng.
Bu xususiyatni isbotlash oson. K umumiy bo‘luvchi M u N (M> N) bo‘lsin. Bu shuni anglatadiki, M = mK, N = nK, bu erda m, n natural sonlar va m> n. U holda M - N = K (m - n), bundan kelib chiqadiki, K - M - N sonining bo'luvchisi. Demak, M va N sonlarning barcha umumiy bo'luvchilari ularning M - N farqining bo'luvchilari, shu jumladan eng kattasi ham. umumiy bo'luvchi.
Ikkinchi aniq xususiyat:
GCD (M, M) = M.
"Qo'lda" hisoblash uchun Evklidning algoritmi quyidagicha ko'rinadi:
1) agar raqamlar teng bo'lsa, ulardan birortasini javob sifatida qabul qiling, aks holda algoritmni davom ettiring;
2) kattaroq sonni katta va kichik sonlar orasidagi farq bilan almashtiring;
3) 1-bosqichga qayting.
M = 32, N = 24 misolidan foydalanib, ushbu algoritmni ko'rib chiqing:
Algoritmning tuzilishi ichki tarmoqqa ega bo'lgan halqadir. M va N qiymatlari bir-biriga teng bo'lmaguncha tsikl takrorlanadi. Forking, ikkita qiymatdan kattasi ularning farqi bilan almashtiriladi.
Endi M = 32, N = 24 asl qiymatlari uchun algoritmning kuzatuv jadvaliga qarang.

Qadam	Operatsiya	M	N	Vaziyat
1	kiritish M	32
2	N kiritish		24
3	M ¹ N			32 ¹ 24, ha
4	M> N			32> 24, ha
5	M: = M-N	8
6	M ¹ N			8 ¹ 24, ha
7	M> N			8> 24, yo'q
8	N: = N-M		16
9	M ¹ N			8 ¹ 16, ha
10	M> N			8> 16, yo'q
11	N: = N-M		8
12	M ¹ N			8 ¹ 8, yo'q
13	pin M	8
14	yakun

Yakunda biz kerakli natijaga erishdik.

AY va Paskal tillarida dastur

Algoritmni AY, dasturni Paskalda yozamiz.
Savol va topshiriqlar
1. Kompyuteringizda Evklid dasturini ishga tushiring. Uni M = 32, N = 24 qiymatlari bo'yicha sinab ko'ring; M = 696, N = 234.
2. Quyidagi formuladan foydalanib, uchta sonning eng katta umumiy bo‘luvchisini topish dasturini tuzing:
GCD (A, B, C) = GCD (GCD (A, B), C).
3. Ikki sonning eng kichik umumiy karralini (LCM) formuladan foydalanib topish dasturini tuzing:
A × B = GCD (A, B) × LCM (A, B).
GCD ni ikkita asosiy usulda topishning ikkita asosiy usulini ko'rib chiqing: Evklid algoritmidan foydalanish va asosiy omillarga ajratish. Keling, ikkita, uch yoki undan ko'p sonlar uchun ikkala usulni ham qo'llaymiz.