Qabul qildi: Abdulxamidov A

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI FARG’ONA FILIALI 615-20 GURUH TALABASI
NO’MONJONOV BAXTIYORNING
“ALGORITMLARNI LOYIHALASH” fanidan

19-25 LABARATORIYA ISHI.

Qabul qildi: Abdulxamidov A.

Mavzular nomlari.
“Ajrat va hukmronlik qil” prinsipi bo’yicha ishlaydigan algoritmlarni loyihalash.
Elementlar jamlanmasini biror belgi bo’yicha tartiblashtirish algoritmi.
Bog’langan graflarda marshrutlar, ularni narxi(masofasi) bo’yicha baholash.
Xasis algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo’yicha hajmini baholash.
Kruskal algoritmi. Prima algoritmi. Xoffman algoritmi.
Kesishmaydigan to’plam ostilari va birlashmalarini qidirish algoritmi.
Xulosa .
Foydalanilgan adabiyot va saytlar.
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.
LABORATORIYA ISHI - 20
Элементлар жамланмасини бирор белги бўйича тартиблаштириш алгоритми
Ma‟lumotlarni kompyuterda qayta ishlashda elementning informatsion maydoni va uning mashina xotirasida joylashishini bilish zarur. Shu maqsadda
Ma’lumotlarni saralash amalga oshiriladi. Demak, saralash – bu ma’lumotlarni kalitlari bo’yicha doimiy ko’rinishda mashina xotirasida joylashtirishdan iborat. Bu yerda doimiylik ma’lumotlarni massivda kalitlari bo’yicha o’sishi tartibida berilishi tushuniladi.
Ma’lumotlarga qayta ishlov berilayotganda ma’lumotning informatsion maydonini hamda uning mashinada joylashishini (adresini) bilish zarur.
Saralashning ikkita turi mavjud: ichki va tashqi:
 -ichki saralash - operativ xotiradagi saralash;
- tashqi saralash – tashqi xotirada saralash.
Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma‟nosida) talab qiladi. Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma‟lumot ko’rsatkichlari almashtirilib, massiv o’z joyida qoladi. Bu usul adreslar jadvalini saralash usuli deyiladi. Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir xil kalitlilar boshlang’ich tartibda qanday joylashgan bo„lsa, shu tartibda qoldirilishi maqsadga muvofiq bo’ladi (Bir xil kalitlilar o’zlariga nisbatan). Bunday usulga turg’un saralash deyiladi.
Saralash samaradorligini bir necha mezonlar bo’yicha baholash mumkin:
 saralashga ketgan vaqt;
 saralash uchun talab qilingan operativ xotira;
 dasturni ishlab chiqishga ketgan vaqt.

Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki almashtirishlar sonini hisoblash mumkin.

Faraz qilaylik, N = 0,01n2 + 10n – taqqoslashlar soni. Agar n < 1000 bo’lsa, u holda ikkinchi qo’hiluvchi katta, aks holda ya’ni, n > 1000 bo’lsa, birinchi qo’shiluvchi katta bo’ladi.
Demak, kichkina n larda taqqoslashlar soni n ga teng bo’ladi, katta n larda esa n2 ga teng bo’ladi.
Saralashda taqqoslashlar soni quyidagi oraliqlarda bo’ladi:
dan gacha; – ideal holatda.
Saralashning quyidagicha usullari bor:
 qat‟iy (to’g„ridan-to’g„ri) usullar;
 yaxshilangan usullar.
Qat’iy usullarning afzalliklarini ko’rib chiqaylik:
1. Bilamizki, dasturlarning o„zlari ham xotirada joy egallaydi. To’g„ridan-to’g„ri saralash usullarining dasturlari qisqa bo’lib, ular tushunishga oson.
2. To’g„ridan-to’g„ri saralash usullari orqali saralash tamoyillarining asosiy xususiyatlarini tushuntirish qulay.
3. Murakkablashtirilgan usullarda uncha ko’p amallarni bajarish talab qilinmasada, ushbu amallarning o„zlari ham ancha murakkabdir. Garchi yetarlicha katta n larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar tezroq ishlaydi.
Shu joyni o„zida qat‟iy usullarni ishlash tamoyillariga ko’ra 3 ta toifaga bo’lish mumkin:
1. To’g„ridan-to’g„ri qo„shish usuli (by insertion);
2. To’g„ridan-to„g„ri tanlash usuli (by selection);
3. To’g„ridan-to„g„ri almashtirish usuli (by exchange).
To„g„ridan-to„g„ri qo„shish usuli bilan saralash algoritmi
Bunday usul karta o„yinida keng qo„llaniladi. Elementlar (kartalar) hayolan “tayyor” a(1),...,a(i-1) va boshlang„ich ketma-ketliklarga bo„linadi. Har bir qadamda (i=2 dan boshlanib, har bir qadamda bir birlikka oshirib boriladi) boshlang„ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo„yiladi.
To„g„ridan-to„g„ri qo„shish orqali saralash algoritmi quyidagicha bo„ladi:
for (int i=1;ix=a[i];
x ni a[0]...a[i] oraliqning mos joyiga qo‘shish
}
Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo„ladi. 2-elementdan boshlab har bir elementni qarab chiqamiz, ya‟ni har bir element o„zidan oldin turgan element bilan solishtiriladi. Agar qaralayotgan element kichik bo„lsa, oldinda turgan element bilan o„rin almashadi va yana o„zidan oldinda turgan element bilan solishtiriladi, jarayon shu kabi davom etadi. Bu jarayon quyidagi shartlarning birortasi bajarilganda to„xtatiladi:
1. x elementi oldida uning kalitidan kichik kalitli a(j) elementi chiqqanda.
2. x elementi oldida element qolmaganda.
for (int i=1;iwhile(a[j]int t=a[j-1];
a[j-1]=a[j];
a[j]=t;
j=j-1;
}
}
Algoritm samaradorligi
Faraz qilaylik, taqqoslashlar soni C, o„rinlashtirishlar soni M bo„lsin. Agar massiv elementlari kamayish tartibida bo„lsa, u holda taqqoslashlar soni eng katta bo„lib, u ga teng bo„ladi, ya‟ni . O„rinlashtirishlar soni esa ga teng bo„ladi, ya‟ni . Agar berilgan massiv o„sish tartibida saralangan bo„lsa, u holda taqqoslashlar va o„rinlashtirishlar soni eng kichik bo„ladi, ya‟ni , .
Tanlash orqali saralash algoritmi
Mazkur usul quyidagi tamoyillarga asoslangan:
1. Eng kichik kalitga ega element tanlanadi.
2. Ushbu element birinchi element bilan o„rin almashinadi.
3. Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to bitta eng “katta” element qolguncha davom ettiriladi.
for(int i=0;ifor(int j=i+1;jif (a[i] > a[j]){
int k = a[j];
a[j]= a[i];
a[i]= k;
}
Algoritm samaradorligi: