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.