Ajrat va hukmronlik qil

10.1 Laboratoriya mashg’uloti
Mavzu: ”Ajrat va hukmronlik qil” prinsipi buyicha ishlaydigan algoritmlarni loyihalash
Ishning maqsadi:

• 
  ”Ajrat va hukmronlik qil” prinsipi buyicha ishlaydigan algoritmlar bilan tanishish
  
• 
  Massivning eng katta elementini shu algoritm bo’yicha toppish
  

Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
"Bo’lish va hukmronlik qilish " tushunchasi kirruvchi ma’lumotlarni bir necha qismlarga bo'ladigan, har bir qism uchun masalani rekursiv ravishda yechadigan va keyin qism masalalarning yechimlarini bitta umumiy yechimga birlashtiradigan algoritmik usullar sinfini anglatadi. Ko'pgina hollarda, bunday yechimlar juda oddiy va samarali bo'ladi.” Bo’lish va hukmronlik qilish” usulida algoritmning ishlash vaqtini tahlil qilish odatda kichik masalalarning ishlash vaqti kontekstida ish vaqtining rekursiv chegarasini belgilaydigan takrorlanish munosabatini hisoblashni o'z ichiga oladi.
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.
Demak, “Bo’lish va hukmronlik qilish” algoritmi g’oyasi quyidagicha bo’ladi:
1. Kiruvchi ma’lumotlarni kichik pastki qismlarga ajrating. Masalani dastlabki masalaning kichik nusxalari bo'lgan bir nechta pastki qismlarga bo'ling.
2. qismmasalalarni rekursiv usul bilan yeching. Qismmasalalarni ularni rekursiv ravishda yechish orqali natijaga erishish. Agar pastki qismlarning o'lchamlari yetarlicha kichik bo'lsa, bunday pastki qismlarni to'g'ridan-to'g'ri yechish mumkin.
3. Dastlabki masalaning yechimi uchun pastki qismlarning yechimlarini birlashtirish. Bitta masalani yechish uchun pastki qismlarning yechimlarini birlashtirish.
#include
#include
#include
#define N 10
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);
return max1 > max2 ? max1 : max2;
}
}
int main()
{
int i, a[N];
srand(time(NULL));
for(i = 0; i < N; i++)
printf("%d ", a[i] = rand() % 100);
puts("\n");
printf("sum = %d\n", Max(a, 0, N - 1));
return 0;
}