Ajrat va hukmronlik qil



Download 22,91 Kb.
Sana15.06.2022
Hajmi22,91 Kb.
#674072
Bog'liq
10.1 lab


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;
}
Download 22,91 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©www.hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish