Bajaruvchi: Istamov m tekshiruvchi: Axmedov f samarqand-2022 4-mavzu. “Dag‘al kuch” usuli. “Xasis” algoritmlar

1-masala. Manfiy bo’lmagan butun sonlar massividan eng katta elementni toppish dasturini “Bo’lish va hukmronlik qilish” algoritmi yordamida aniqlang.
A[]={4,6,5,2,7,9,6,1}
Max_element= 9
“Bo’lish va hukmronlik qilish” usuli mohiyatiga ko’ra, masalada berilgan kiruvchi ma’lumotlar bir necha mayda qismlarga ajratiladi. Ajratilgan bo’laklar rekursiya yordamida hisoblanib, yana umumlashtiriladi.
Bu masalani yechish uchun biz butun son qaytaruvchi int turidagi int Max(*a, l,r) rekursiv funksiyasini kiritib olamiz. bu yerda l massivning chap tomondagi elementi, r – o’ng tomondagi element.
Agar l==r bo’lsa, max=a[l] bu rekursiv funksiyaning bazaviy holati. Aks holda,
max1 = Max(a, l, (l + r)/2);
max2 = Max(a, (l + r)/2 + 1, r); -






C++ dasturlash tilida int Max(*a, l,r) rekursiv funksiyasi quyidagicha bo’ladi.
int Max(int *a, int l, int r)
{
int max1, max2;
if (l == r)
return a[l]; else
{
max1 = Max(a, l, (l + r)/2);
max2 = Max(a, (l + r)/2 + 1, r);
if (max1 > max2)
return max1;
else
return max2;
}
}
Bu masalaning "Bo’lish va hukmronlik qilish " algoritmida yechsak, algoritm bahosi O(NlogN) ga teng bo’ladi.
Mavzu: Elementlar jamlanmasini biror belgi bo’yicha tartiblashtirish algoritmi
Ishning maqsadi:
Karatsuba algoritmining dasturini ishlab chiqish;
Quick-sort algoritmi uchun dastur tuzish.
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
1-masala.Ikkita X va Y sonlarni hisobga olgan holda, ularning ko'payishini Karatsuba algoritmi yordamida hisoblang.
Kirish: X = "1234", Y = "2345"
Chiqish: x va y ni ko'paytirish 28,93,730 ga teng.
Bu sodda usul - boshlang'ich maktabni ko'paytirish uslubiga rioya qilish, ya'ni ikkinchi sonning har bir raqamini birinchi raqamning har bir raqami bilan ko'paytirish va keyin barcha ko'paytirish natijalarini qo'shishdir.
Karatsuba algoritmasi
Ushbu g'oya n-raqamli sonni ikkiga bo'linib (har birining yarmi yarim raqamga ega) ular sodda usul yordamida ko'paytiriladigan darajada kichik bo'lguncha (1 ta raqamga ega) bo'lib boriladi. Ikkita X va Y sonlarni ko'rib chiqing, ular m asosga ega bo'lib, quyidagi tenglama yordamida ifodalanadi,
X = mceil (n2) ∗ a + b, Y = mceil (n2) ∗ c + d X = mceil (n2) ∗ a + b, Y = mceil (n2) ∗ c + d
Amalni ko'rganingizda, ceil (n / 2) shartlari aniqroq bo'ladi. Shunday qilib, soddaligi uchun siz n ni hozirgiday qabul qilishingiz mumkin.
X va Y ni ko'paytirish quyidagi tenglamalarda amalga oshiriladi,
X ∗ Y = (mceil (n2) ∗ a + b) ∗ (mceil (n2) ∗ c + d) X ∗ Y = (mceil (n2) ∗ a + b) ∗ (mceil (n2) ∗ c + d)
X ∗ Y = m2 ∗ shift (n2) (ad + bc) + bd∴X ∗ Y = m2 ∗ shift (n2) (ad + bc) + bd
Yuqoridagi tenglamada X va Y n ta raqamga ega va a, b, c va d har birida n / 2 ta raqam mavjud. N / 2 o'lchamdagi (raqamlar soni n / 2 ga teng) to'rtta ko'paytma (ac, ad, bc, bd) mavjud. Shunday qilib, asosan, biz n kattalashtirish masalasini n / 2 kattalikdagi to'rtta ko'paytmaga ajratdik. Ammo baribir T (n) = 4T (n2) + O (n) T (n) = 4T (n2) + O (n) hosil bo'lgan takrorlanish munosabatlarining vaqt murakkabligi O (n2) O (n2). Shuning uchun, hiyla yuqoridagi tenglamaning o'rta qismini quyida ko'rsatilgandek ajratishdir,
(ad + bc) = (a + b) (c + d) -ac-bd (ad + bc) = (a + b) (c + d) -ac-bd
Ac va bd ko'paytmalari (1) tenglamada allaqachon hisoblab chiqilganligi sababli biz ad va bc ko'paytmalarni bitta ko'paytma (a + b) ∗ (c + d) (a + b) ∗ (c + d) ga kamaytirdik. Shuning uchun endi n / 2 kattalikdagi uchta ko'paytma mavjud (raqamlar soni n / 2 ga teng) va hosil bo'lgan takrorlanish munosabati T (n) = 3T (n2) + O (n) T (n) = 3T ( n2) + O (n).