Ajrat va hukmronlik qil

---

LABORATORIYA ISHI - 19 
Mavzu: 
“Ajrat va hukmronlik qil” prinsipi bo’yicha ishlaydigan algoritmlarni 
loyihalash.
 
Ishdan maqsad. 
“Ajrat va hukmronlik qil” prinsipi bo’yicha ishlaydigan 
algoritmlarni loyihalashni o’rganish. 
Qo’yilgan masala.
“Ajrat va hukmronlik qil” prinsipi bo’yicha ishlaydigan 
algoritmlarni loyihalash. 
Ish tartibi: 

Tajriba ishi nazariy ma’lumotlarini o‘rganish; 

Berilgan topshiriqning algoritmini ishlab chiqish; 

C++ dasturlash muhitida dasturni yaratish; 

Natijalarni tekshirish; 

Hisobotni tayyorlash va topshirish. 
Nazariy qism 
Vazn oralig’ini rejalashtirish: rekursiv jarayonlar 
Rekursiya va stack 
Vazifalarga qaytaylik va ularni batafsilroq ko'rib chiqamiz. 
Bizning birinchi mavzuimiz rekursiya bo'ladi. 
Agar siz dasturlash uchun yangi emas bo'lsangiz, siz allaqachon rekursiya 
bilan tanish bo'lishingiz mumkin va siz ushbu bobni o'tkazib yuborishingiz 
mumkin. 
Rekursiya - bu vazifani tabiiy ravishda bir nechta o'xshash, ammo sodda 
vazifalarga bo'lish mumkin bo'lgan holatlarda foydali bo'lgan dasturlash usuli. 
Yoki biron bir vazifani sodda harakatlarga soddalashtirish mumkin bo'lsa, xuddi 
shu vazifaning oddiy versiyasi. Yoki, yaqinda bilib olamizki, ma'lum bir tuzilmalar 
bilan ishlash uchun. 
Vazifani bajarish jarayonida subkastrlarni bajarish uchun boshqa 
funktsiyalarni funktsiyaning tanasida chaqirish mumkin. Sub-qo'ng'iroqning 
alohida holati bu funktsiya o'zini o'zi chaqirganda. Bu rekursiya deb ataladi. 
Fikrlashning ikki yo'li 
Birinchi misol sifatida, x n kuchini n ga ko'taradigan pow (x, n) funktsiyasini 
yozamiz. Boshqacha aytganda, x ni n marta ko'paytiradi. 
pow(2, 2) = 4 
pow(2, 3) = 8 
pow(2, 4) = 16 
: 
function pow(x, n) { 

---

let result = 1; 
// умножаем result на x n раз в цикле 
for (let i = 0; i < n; i++) { 
result *= x; 
} 
return result; 
} 
alert( pow(2, 3) ); // 8 
: 
function pow(x, n) { 
if (n == 1) { 
return x; 
} else { 
return x * pow(x, n - 1); 
} 
} 
alert( pow(2, 3) ); // 8 
Ichki qo'ng'iroqlarning umumiy soni (birinchi qatorni ham qo'shgan holda) 
rekursiya chuqurligi deb ataladi. Bizning holatda, u aniq n bo'ladi. 
Maksimal 
rekursiya 
chuqurligi 
JavaScript 
mexanizmi 
tomonidan 
cheklangan. Siz 10000 kirgan qo'ng'iroqlarni aniq hisoblashingiz mumkin, ba'zi 
tarjimonlar ko'proq imkoniyat berishadi, ammo ularning ko'plari uchun 100 mingta 
qo'ng'iroqlar imkoniyatlardan tashqarida. Avtomatik optimallashtirish mavjud 
bo'lib, ular qo'ng'iroqlar to'plamini ("quyruq rekursionini optimallashtirish") toshib 
ketishini oldini olishga yordam beradi, ammo ular hali ham hamma joyda qo'llab-
quvvatlanmaydi va faqat oddiy holatlar uchun ishlaydi. 

---

Bu recursiondan foydalanishni cheklaydi, ammo u hali ham keng tarqalgan: 
ko'p sonli muammolarni hal qilish uchun rekursiv hal qilish usuli sodda sodda 
kodni beradi. 
Bajarish konteksti, qoziq 
Endi biz rekursiv qo'ng'iroqlar qanday ishlashini bilib olamiz. Buning uchun 
funktsiyalarning "kaputi ostiga" qarang. 
Ishga tushirilgan funktsiyaning bajarilish jarayoni to'g'risidagi ma'lumotlar 
uning bajarilish kontekstida saqlanadi. 
Bajarish konteksti funktsiyani chaqirish haqida ma'lumotni o'z ichiga olgan 
maxsus ichki ma'lumotlarning tuzilishi. U tarjimon joylashgan kodning o'ziga xos 
joyini, funktsiyaning mahalliy parametrlarini, uning qiymatini (biz ushbu misolda 
ishlatmaymiz) va boshqa qo'shimcha ma'lumotlarni o'z ichiga oladi. 
Bitta funktsiya chaqiruvi aniq bitta bitta bajariladigan kontekstga bog'liq. 
Agar funktsiya o'rnatilgan qo'ng'iroqni amalga oshirsa, quyidagilar sodir 
bo'ladi: 
Joriy funktsiyaning bajarilishi pauza qilingan. 
U bilan bog'liq bo'lgan ijro etilish konteksti maxsus ma'lumotlar 
strukturasida - ijro kontekstlarining to'plamida saqlanadi. 
Ichki qo'ng'iroqlar amalga oshiriladi, ularning har biri uchun ijro etilishning 
boshqa konteksti yaratiladi. 
Ular tugallangandan so'ng eski kontekst stekandan olinadi va tashqi 
funktsiyaning bajarilishi to'xtatilgan joydan boshlanadi. 
Misol sifatida toz (2, 3) funktsiyasidan foydalanib, kontekstlarni batafsil 
ko'rib chiqamiz. 
pow (2, 3) 
Pow (2, 3) chaqirig'ining boshida, ijro konteksti o'zgaruvchilarni saqlaydi: x 
= 2, n = 3, ijro funktsiyaning birinchi qatorida joylashgan. 
Siz sxematik tarzda quyidagicha tasvirlashingiz mumkin: 
Kontekst: {x: 2, n: 3, 1-qator} pow (2, 3) 
Bu faqat funktsiyaning boshlanishi. N == 1 sharti noto'g'ri, shuning uchun 
ijro ikkinchi tarmoqqa o'tadi, agar:: 
function pow(x, n) { 
if (n == 1) { 
return x; 

---

} else { 
return x * pow(x, n - 1); 
} 
} 
alert( pow(2, 3) ); 
Boshqacha aytganda, kompaniyada bo'limlar mavjud. 
Bo'lim bir ator xodimlardan iborat bo'lishi mumkin. Masalan, savdo 
bo'limida 2 nafar xodim ishlaydi: Jon va Elis. 
Yoki bo'limni bo'linmalarga bo'lish mumkin, masalan, rivojlanish bo'limi 
bo'limlardan iborat: saytlar va ichki. Har bir bo'lim o'z xodimlariga ega. 
Bo'linmaning o'sishi bilan u birliklarga (yoki jamoalarga) bo'linishi ham 
mumkin. 
Masalan, kelgusida saytlar bo'linmasini saytA va saytB buyruqlariga bo'lish 
mumkin. Va ehtimol ular hali ham ulashilishi mumkin. Bu rasmda emas, 
shunchaki buni yodda tutishingiz kerak. 
Endi barcha ish haqi miqdorini olish uchun bizga funktsiya kerak deylik. 
Buni qanday qilishimiz mumkin? 
Iterativ yondashuv oddiy emas, chunki struktura ancha murakkab. Birinchi 
g'oya - bu 1-darajali joylashish bo'limlari ustidan kompaniya ob'ekti ustiga pastadir 
uchun tsikl qilish. Ammo keyin biz ikkinchi darajali bo'limlarning, masalan 
saytlarning ishchilari ustidan ishora qilish uchun ko'proq ichki teshiklarni talab 
qilamiz ... Va kelajakda paydo bo'lishi mumkin bo'lgan uchinchi darajali bo'limlar 
uchun yana bir tsikl kerakmi? Agar bitta ob'ektni kesib o'tish uchun kodga 3-4 
teshik joylashtirsak, u juda xunuk bo'ladi. 
Keling, rekursiyani sinab ko'raylik. 
Ko'rib turganimizdek, bizning vazifamiz ish haqi miqdorini hisoblash uchun 
bo'limni olganda, ikkita mumkin bo'lgan holatlar mavjud. 
Yoki u "oddiy" bo'lim bilan massivmi - shunda biz oddiy ish tsiklida ish 
haqini umumlashtirishimiz mumkin. 
Yoki u N bo'linmalari bilan ob'ektmi - keyin biz har bir bo'linma uchun 
yig'indini olish uchun N rekursiv chaqiruvlarni amalga oshiramiz va natijalarni 
birlashtiramiz. 
Masala (1), biz qatorga ega bo'lganimizda, rekursion asos, arzimas holat 

---

Case (2), ob'ektni olgandan so'ng, rekursiya bosqichidir. Qiyin vazifa pastki 
bo'limlarga bo'linadi. Ular, o'z navbatida, yana bo'linmalarga bo'linishi mumkin, 
ammo ertami-kechmi bu bo'linish tugaydi va echim bu ish uchun kamayadi (1) 
Rekursiyadan chiqish 
Rekursiv protseduralarni har qanday Ijrochi uchun yozish mumkin. Masalan, 
Robotni kvadrat bo‘y!ab yurishi uchun rekursiv protsedura yozaylik. 
7.4-masala 
Tomoni 5 ga teng kvadratni chizish rekursiv protsedurasini 
yozing. Javob. 
PROT rekursiv kvadrat 
BOSHLANISH 
oldinga oldinga 
oldinga oldinga 
oldinga o‘ngga 
rekursiv kvadrat TAMOM 
Bu protsedura qanday ishlashini ko‘rib chiqamiz. Demak, rekursiv kvadrat 
protsedurasi chaqirilganda oldinga oidinga 
oldinga oldinga oldinga 
0‘ngga ko‘rsatmalari bajariladi. Bunda Robot kvadratning tomoni bo‘ylab 
yurib 90 gradusga buriladi. Keyin yana rekursiv kvadrat protsedurasi chaqiriladi. 
Robot kvadratning boshqa tomoni 
bo'ylab yurib o'ngga buriladi. Keyin yana rekursiv kvadrat protsedurasi 
chaqiriladi. Yana ikki tomon o'tilgach kvadrat 
bo‘ylab yurish yakunlanadi. Lekin nimadir bo‘ldi? Robot to'xta- masdan 
yana shu kvadrat bo'ylab yurishni davom ettirmoqda. Bu esa cheksiz davom etadi 
— algoritm siklga tushib qoldi. Vaziyat yoqimsiz. Biz doimo siklga tushib 
qolmaslikka harakat qilar edik. Bu holda undan qutulishning chorasi bormikan? 
Taas- sufki, yo‘q. Haqiqatan, rekursiv protseduraning chaqirilishi cheksiz davom 
etmasligi uchun protseduraga chaqirilish yuzaga kelmaydigan shart kiritish kerak. 
Lekin bu Robotda bunday shart yo‘q. Robotning algoritmi uning holatidan qa’tiy 
nazar, 
bir xilda bajarilaveradi. Shu kabi, Dehqon, Suvchi, Chigirtka, Oshiruvchi, 
Zohid kabi Ijrochilarda shart yo‘q. Bu Ijrochiiar uchun rekursiv protseduraning 

---

qo‘lianishi yoki siklga tushib qolinadi yoki keyingi ko'rsatmani bajarish mumkin 
bo'lmay qolib, INKOR yuzaga keladi. Shuning uchun Sharti yo'q Ijrochilar uchun 
rekursiv protseduralarni qo’llamang! 
Bu qo’llanmada ko‘rib chiqilgan Ijrochilardan faqat Kamaytiruvchi va 
Robotda shart bor. Demak, faqat shu ikki Ijrochi uchun rekursiv protseduralami 
yozish ma'noga ega. Bizning mulohazalarimizdan shunday xulosaga kelish 
mumkin; Rekursiv protseduralarni yozganda rekursiv chaqirish yuzaga 
kelmaydigan shart ko‘rsatilishi kerak. 
Bu juda kerakli xulosa! Shuning uchun ham awalgi bo‘limda algoritm 
namunalarini keltirganimizda, rekursiv protsedu- ralarning shunday shartlarini va 
zaruriy amallarining tavsifini yozishdan boshlaganmiz.