Mustaqil ishi bajardi: Haydarov N. Qabul qildi: Begulov O
Yüklə 158,14 Kb.
|
|
Muhammad al-Xorazmiy nomidagi TATU Qarshi filiali KI fakulteti DI-12-22 guruh talabasi Haydarov Nematjonning Ma’lumotlar tuzilmasi va algoritmlari fanidan tayyorlagan 2-MUSTAQIL ISHI Bajardi: Haydarov N. Qabul qildi: Begulov O. Reja:
Stek - massiv tuzilmasidan farqli ravishda, elementlarni kiritish yoki chiqarib tashlashga imkon beradigan o’zgaruvchan o’lchamning chiziqli tuzilmasidir, ya’ni stekda ma’lumotlar hajmi dasturning bajarilishi vaqtida uyg’un ravishda oshishi va kamayishi mumkin. Stekli tuzilmaning xususiyati shundan iboratki, elementlardan erkin foydalanish, elementlarni kiritish va chiqarib tashlash faqat tuzilmaning bir tomonidan - stek cho’qqisidan mumkin bo’ladi. SHuning uchun stekka oxirida kiritilgan element birinchi bo’lib o’qiladi yoki tanlanadi. Bunday tuzilmada axborot «oxirida keldi, birinchi ketdi» tamoyili bo’yicha qayta ishlanadi. Stekning tuzilmasini ba’zan LIFO (inglizcha Last In, First Out) tipidagi tuzilma deyiladi, bu qachonki faqat yuqoridagi likobchani olish mumkin bo’lgan likobchalar to’plami misolida yaxshi tushuniladi. Avval yuqoridagi likobchani, so’ngra keyingisini olish mumkin. Likobchalar to’plamning yuqori qismiga bittadan qo’shiladi. Stekning tuzilmasi erkin foydalanish cheklangan ma’lumotlar tuzilmasi hisoblanadi, chunki faqat stekning cho’qqisida joylashgan elementdan erkin foydalanish mumkin bo’ladi. Bu element joriy element deb ataladi. Joriy elementning joyi to’g’risidagi axborot odatda stekning bosh uyasida joylashadigan stek cho’qqisining ko’rsatkichi (SCHK)da saqlanadi. Steklarni saqlash uchun ma’lumotlarni ham ketma-ket, ham bog’langan taqdim etishidan foydalanish mumkin. Ketma-ket taqdim etishdan foydalanganda stekning eng oxirgi o’lchamini bilish zarur. Ko’zda tutiladigan ushbu eng chekka o’lcham uchun moslab xotira zahiraga olinadi va uning ichida stek oshadi va qisqaradi. Blokning birinchi uyasi stek cho’qqisining ko’rsatkichini o’z ichiga oladi. Stek bo’sh bo’lganida ko’rsatkich o’zini-o’zi ko’rsatadi. Har bir yangi elementning kiritilganida cho’qqi ko’rsatkichi bir birlikka ko’payadi. Ketma-ket taqdim etishning kamchiligi shundan iboratki, stekning to’lib ketishi xavfi hamisha bo’ladi; aks holda zahiraga olingan xotiraning bir qismi ishlatilmay qoladi. Ma’lumotlarni bog’langan taqdim etishdan foydalanganda stek uchun moslab xotirani oldindan zahiraga olishning zarurati bo’lmaydi. Stekning barcha elementlari xotira bo’yicha yoyib tashlanadi va o’zaro ko’rsatkichlar bilan bog’lanadi. SCHK stekning eng yuqoridagi elementi joylashgan uyaga ko’rsatadi. Elementlar kiritilganida yoki chiqarib tashlanganida cho’qqi ko’rsatkichining qiymati o’zgaradi. Yangidan kiritilayotgan element xotiraning ixtiyoriy bo’sh uyasiga joylashtiriladi va u mos ravishda bog’langan ro’yxat ko’rsatkichlarini o’zgartirish yo’li bilan stekka qo’shiladi. Ma’lumotlarni bog’langan taqdim etishda stek cheksiz oshishi mumkin. Asosiy ro’yxatdan o’chirilgan ixtiyoriy uya bo’sh xotira stekining cho’qqisiga qo’shiladi. Bo’sh xotira stekiga kiritilgan so’nggi uya asosiy ro’yxatning yangi yozuvini joylashtirish uchun birinchi bo’lib ishlatiladi. Bo’shagan uyalarni bo’sh xotira stekiga kiritilishini boshqaradigan algoritm ko’pincha «axlat yig’uvchi» deb ataladi. Stekli tuzilmalar ichiga qo’yilgan kichik dasturlar va ko’p pog’onali uzilishlarni amalga oshirishda translyatorlarda, shuningdek algoritmlari rekursiv usul bilan eng yaxshi ta’riflanadigan vazifalarni echishda keng qo’llaniladi. Navbat bu o’zgaruvchan o’lchamdagi chiziqli tuzilmadir. Elementlarni navbatdan chiqarib tashlashga bir tomondan - navbatning boshidan ruxsat beriladi. Elementlarni kiritish faqat teskari tomonga - navbatning oxiriga bo’lishi mumkin. Bunday tuzilmadagi ma’lumotlar ular kelib tushishiga qarab «birinchi keldi, birinchi ketdi» tamoyili bo’yicha qayta ishlanadi. Adabiyotda navbat tuzilmasini FIFO (inglizcha First In, First Out) tipidagi tuzilma deyiladi. Svetoforning ochilishini kutayotgan avtomobillar navbati an’anviy misol hisoblanadi. Svetoforga birinchi bo’lib kelgan avtomobil chorrahadan birinchi bo’lib o’tib ketadi, ya’ni navbatdan chiqariladi. Oxirida kelgan va navbatning oxirida o’tib ketishni kutayotgan avtomobilb chorrahadan oxirgi bo’lib o’tadi. Navbat elementlaridan erkin foydalanish boshlanish va tugash ko’rsatkichi bo’yicha amalga oshiriladi. Boshlanish ko’rsatkichi birinchi bo’lib chiqarib tashlanadigan yoki o’qiladigan navbat elementini ko’rsatadi. Tugash ko’rsatkichi navbatdagi so’nggi yozuvdan keyin keladigan xotiraning bo’sh uyasiga o’rnatiladi. Yangi kelgan yozuv, ya’ni navbatning yangi elementi aynan shu uyaga joylashadi. Navbat tuzilmasini amalga oshirish uchun KOMPYUTER xotirasida ma’lumotlarni ham ketma-ket, ham bog’langan taqdim etishdan foydalaniladi. Navbatga ketma-ket taqdim etishda stekdagi kabi xotira bloki z ahiraga olinadi, uning ichida navbat oshishi va kamayishi mumkin. Har bir yangi element kiritilishi bilan tugash ko’rsatkichi birlikka o’zgaradi. Yangi elementlarni kiritish natijasida navbat tugashi ko’rsatkichi zahiraga olingan xotira blokining oxiriga etsa, u blokning boshiga ko’chiriladi. Navbatni bog’langan taqdim etishda xotirani oldindan zahiraga olish talab etilmaydi. Navbatni shakllantiruvchi yozuvlar ixtiyoriy bo’sh xotira uyalarida joylashadi va o’zaro ko’rsatkichlar bilan bog’lanadi. Bunday navbat cheksiz oshishi mumkin. Elementlarni kiritish va chiqarib tashlashda faqat boshlanish va tugash ko’rsatkichlarining qiymati va aloqa ko’rsatkichlarining qiymati (AS) o’zgaradi, xolos. Navbat tuzilmasi ma’lumotlarni qayta ishlashning turli vazifalarini echishda ishlatiladi. Masalan, vaqtni taqsimlash bilan hisoblash tizimini modellash navbat tuzilmasi ishlatiladigan an’anviy vazifalardan biri hisoblanadi. Bunday tizimda ko’pchilik foydalanuvchilar bir vaqtning o’zida bitta asosiy xotiradan foydalanib yagona markaziy protsessor bilan ishlaydi. Ma’lumotlarning nochiziqiy tuzilmasi. Ma’lumotlari AATda qayta ishlanadigan obyektlar o’rtasidagi munosabatlar ko’pincha nochiziqiy xarakterga ega bo’ladi. Bular mantiqiy shartlar bilan aniqlanadigan munosabatlar, «birning ko’pga» tipidagi munosabatlar yoki «ko’pning ko’pga» tipidagi munosabatlar bo’lishi mumkin. «Birning ko’pga» tipidagi munosabatlar ierarik xarakterga ega va daraxtsimon tuzilma bilan aks ettiriladi. Masalan, oliy o’quv yurti o’quv bo’linmalarining tuzilmasi, shuningdek kutubxonalarda qabul qilingan Universal o’nlik tasniflash (UO’T) ierarxiya ko’rinishida berilishi mumkin. Kitob mundarijasi daraxtsimon tuzilma ko’rinishida taqdim etilishi mumkin. Daraxtsimon tuzilma algebraik ifodalarni echish algoritmlarini qurish uchun, ma’lumotlardan erkin foydalanishni tezlashtiradigan ma’lumotnomalarni yaratish uchun, saralash va izlash uchun qo’llaniladi. Daraxt ba’zi cheklovlarga ega grafdan iborat, ya’ni bu tsikllarga ega bo’lmagan yo’naltirilgan grafdir. Daraxtning cho’qqi (bo’g’im)lari darajalar bo’yicha tashkil qilingan, ya’ni ma’lum ierarxiyaga bo’ysungan. Daraxtning ixtiyoriy bo’g’imi yuqoriroq darajadagi yagona bo’g’im - yaratuvchi bilan hamda quyi darajadagi m bo’g’imlar - yaratilgan bilan bog’langan. Eng yuqori darajada daraxtning boshida ildiz deb ataluvchi yagona bo’g’im mavjud. Daraxt har bir shoxining oxirida joylashgan va yaratilganlarga ega bo’lmagan bo’g’imlar barglar deb ataladi. O’zaro bog’lanmagan daraxtlarning majmui o’rmon hosil qiladi. Daraxtlarda yo’nalish albatta yaratuvchidan yaratilganga qarab bo’ladi, shuning uchun qirralarda strelkalarni ko’rsatmasa ham bo’ladi. Ildizdan qandaydir bo’g’imgacha bo’lgan yo’l uzunligi ushbu bo’g’imning darajasiga teng. XULOSA Ba’zan daraxtlarni tasvirlashda genealogik daraxtlar (shajara)ni tasvirlashda ishlatiladigan alohida atamalarni qo’llash qulaydir. Masalan, yaratuvchi cho’qqini ba’zan ota deb, barcha yaratilganlarni esa - avlodlar yoki o’g’illar deb atashadi. Daraxtlarni grafik tasvirlash usulidan tashqari boshqa usullar ham mavjud. Ularning biri, masalan, kitob mundarijasini tuzishda qo’llaniladi. Ma’lumotlarning daraxtsimon tuzilmasini tarmoq tuzilmalariga qaraganda kompyuter xotirasida amalga oshirish ancha qulaydir. Bundan tashqari, tarmoqlar bilash ishlash uchun daraxtlar bilan ishlashga qaraganda ancha murakkab dasturiy ta’minot talab etiladi. Dinamik turdagi ma’lumotlar tuzilmasi Reja: 1. Dinamik turdagi ma’lumotlar tuzilmasi. 2. Dinamik ma’lumotlar tuzilmasi klassifikatsiyasi. 3. Dinamik ma’lumotlar tuzilmasi - ro’yhatlar. 4 Dinamik ma'lumotlar tuzilmalari tuzilishi. Afzalliklari va kamchiliklari. Kirish Ma'lumotlar tuzilmasi dasturlarda ajratish usuli bo'yicha statik va dinamikaga bo'lingan. Statik ma'lumotlar tuzilmasi - bu kompyuterning xotirasida joylashishi va elementlarning o'zaro aloqalari ular tomonidan amalga oshiriladigan sohada dasturni bajarish paytida o'zgarishsiz qoladigan ma'lumotlardir. Statik strukturaning ma'lumotlariga dasturda e'lon qilingan asosiy va mahalliy, ham global darajadagi o'zgaruvchilar kiradi. Dinamik ma'lumotlar tuzilmasi - bu kompyuterning xotirasiga joylashtirilishi va New va Dispose kabi tizim proseduralari yordamida dasturni bajarishda xotiradan o'chirilishi mumkin bo'lgan ma'lumotlar. Dinamik ma'lumotlar tuzilmalari ikki shaklda bo'ladi: bog'liq bo'lmagan dinamik ma'lumotlar; bog’liq dinamik ma'lumotlar. Bog’liq bo'lmagan dinamik ma'lumotlar tuzilmasi statik bilan bir xil. Dinamik turdagi ma’lumotlar tuzilmasi Statik ma’lumotlar tuzilmasi vaqt o’tishi bilan o’z o’lchamini o’zgartirmaydi. Biz har doim dastur kodidagi statik ma’lumotlar tuzilmasiga qarab ularning o’lchamini bilishimiz mumkin. Bunday ma’lumotlarga teskari ravishda dinamik ma’lumotlar tuzilmasi mavjud bo’lib, bunda dastur bajarilishi davomida dinamik ma’lumotlar tuzilmasi o’lchamini o’zgartirishi mumkin. Dinamik ma’lumotlar tuzilmasi – bu qandaydir bir qonuniyatga asoslanib shakllangan (https://fayllar.org/2-urug-qabila-dinlarining-shakllari.html), lekin elementlari soni, o’zaro joylashuvi va o’zaro aloqasi dastur bajarilishi davomida shu qonuniyat asosida dinamik o’zgaruvchan bo’lgan ma’lumotlar tuzilmasidir. Dinamik ma’lumotlar tuzilmasi 1-rasmdagidek klassifikatsiyalanadi. Dinamik ma’lumotlar tuzilmasi klassifikatsiyasi Dasturlarda dinamik ma’lumotlar tuzilmasidan ko’pincha chiziqli ro’yhatlar, steklar, navbatlar va binar daraxtlar ishlatiladi. Bu tuzilmalar bir-biridan elementlarning bog’lanish usuli va ular ustida bajarilishi mumkin bo’lgan amallari bilan farqlanadi. Dinamik tuzilmalar massiv va yozuvdan farqli ravishda operativ xotirada ketma-ket sohalarda joylashmaydi. Ixtiyoriy dinamik tuzilma elementi 2 ta maydondan tashkil topadi: tuzilma tashkil etilishiga sabab bo’layotgan informatsion maydon va elementlarning o’zaro aloqasini ta’minlovchi ko‘rsatkichli maydon. Dinamik ma’lumotlar tuzilmasi klassifikatsiyasi Ko'pincha jiddiy dasturlarda siz ish paytida hajmi va tuzilishi o'zgarishi kerak bo'lgan ma'lumotlardan foydalanishingiz kerak. Dinamik qatorlar bu erda yordam bermaydi, chunki qancha xotira ajratilishi kerakligini oldindan aytib bo'lmaydi - bu faqat ish paytida aniqlanadi. Masalan, biz matnni tahlil qilishingiz va unda qanday so'zlar va qancha miqdorda mavjudligini aniqlashimiz kerak va bu so'zlarni alifbo tartibida tartibga solish kerak. Hammasi bo'lib, dinamik ma'lumotlar tuzilishining 6 ta asosiy turi mavjud: Stek Navbat Ro’yhat Daraxt Graf Ro‘yxat. Ro'yxatning 3 turi mavjud: Dinamik ma’lumotlar tuzilmasi - ro’yhatlar Chiziqli ro’yhatlarda har bir element o’zidan keyingisi yoki oldingisi bilan ham bog’langan bo’lishi mumkin. Birinchi holatda, ya’ni elementlar o’zidan keyingi element bilan bog’langan bo’lsa, bunday ro’yhatga bir bog‘lamli ro‘yhat deyiladi. Mazkur ko’rinishdagi ro’yhat elementi k’rsatkichining o’ziga xosligi shundan iboratki (https://fayllar.org/kamchiligi-shundan-iboratki-bu-tenglama-populyasiyalarning-jud.html), u faqatgina ro’yhatning navbatdagi elementi adresini ko’rsatadi. Bir tomonlama yo’naltirilgan ro’yhatda eng so’nggi element ko’rsatkichi bo’sh, ya’ni NULL bo’ladi.Agar har bir element o’zidan oldingi va o’zidan keyingi element bilan bog’langan bo’lsa, u holda bunday ro’yhatlarga 2 bog‘lamli ro‘yhatlar deyiladi.Agar oxirgi element birinchi element ko’rsatkichi bilan bog’langan bo’lsa, bunday ro’yhatga halqasimon ro‘yhat deyiladi. Ro’yhatning har bir elementi shu elementni identifikatsiyalash uchun kalitga ega bo’ladi Ro’yhatlar ustida quyidagi amallarni bajarish mumkin: - ro’yhatni shakllantirish (birinchi elementini yaratish); - ro’yhat oxiriga yangi element qo’shish; - berilgan kalitga mos elementni o’qish; - ro’yhatning ko’rsatilgan joyiga element qo’shish (berilgan kalitga mos elementdan oldin yoki keyin) - berilgan kalitga mos elementni o’chirish; - kalit bo’yicha ro’yhat elementlarini tartibga keltirish. Ro’yhatlar bilan ishlashda dasturda boshlang’ich elementni ko’rsatuvchi ko’rsatkich talab etiladi. Dinamik ma'lumotlar tuzilmalari tuzilishi. Afzalliklari va kamchiliklari Dinamik ma’lumotlar tuzilmasining har bir elementi ikki qismdan iborat: Ma'lumotlar joylashtirilgan ma'lumotlar uchun maydonlar, ular uchun struktura yaratiladi. O'z navbatida, axborot maydonlarida ma'lumotlar tuzilmasi ham bo'lishi mumkin. Elementlarni bir-biriga bog'laydigan bir yoki bir nechta havolalarni o'z ichiga olgan xizmat maydonlari. Ushbu tuzilmalarni amaliy topshiriqlarda ishlatishda, faqat ma'lumot maydonlari oxirgi foydalanuvchiga ko'rinadigan qilib qo'yiladi va xizmat ko'rsatish maydonlaridan faqat dasturchi foydalanadi.Dinamik ma’lumotlar tuzilmasining afzalliklari: - Strukturaning o'lchami faqat mavjud RAM miqdori bilan cheklangan, - Ma'lumotlarning tartibini o'zgartirganda ma'lumotlarni ko'chirish emas, balki faqat havolalarni to'g'rilash talab qilinadi. XULOSA Mazkur ko’rinishdagi ro’yhat elementi k’rsatkichining o’ziga xosligi shundan iboratki, u faqatgina ro’yhatning navbatdagi elementi adresini ko’rsatadi. Bir tomonlama yo’naltirilgan ro’yhatda eng so’nggi element ko’rsatkichi bo’sh, ya’ni NULL bo’ladi.Agar har bir element o’zidan oldingi va o’zidan keyingi element bilan bog’langan bo’lsa, u holda bunday ro’yhatlarga 2 bog‘lamli ro‘yhatlar deyiladi. Agar oxirgi element birinchi element ko’rsatkichi bilan bog’langan bo’lsa, bunday ro’yhatga halqasimon ro‘yhat deyiladi. Ro’yhatning har bir elementi shu elementni identifikatsiyalash uchun kalitga ega bo’ladi. Kalit odatda butun son yoki satr ko’rinishida ma’lumotlar maydonining bir qismi sifatida mavjud bo’ladi. REKURSIV ALGORITMLAR VA ULARNING VAZIFALARI Reja:
Rekursiv algoritm f dasturlash tilida yozilgan. Rekursiya va rekursiv algoritmlar. Asosiy ta'riflar. Daraxtlarni tasvirlash usullari Rekursiya - bu subroutin o'zini o'zi chaqiradigan vaziyat. Bunday algoritmik qurilishga birinchi marta duch kelganda, ko'pchilik muayyan qiyinchiliklarga duch keladi, ammo ozgina amaliyot va rekursiya sizning dasturiy arsenalingizda tushunarli va juda foydali vositaga aylanadi. 1. Rekursiya mohiyati Protsedura yoki funktsiya boshqa protseduralar yoki funktsiyalarni chaqirishni o'z ichiga olishi mumkin. Protsedurani o'z ichiga olishi mumkin. Bu erda hech qanday paradoks yo'q - kompyuter faqat dasturda uchragan buyruqlarni ketma-ket bajaradi va agar u protsedura qo'ng'irog'iga duch kelsa, shunchaki ushbu protsedurani bajarishni boshlaydi. Buni qanday buyruq berganligi muhim emas. Rekursiv protseduraga misol: Rec (a: butun) protsedurasi; agar boshlang\u003e a Agar asosiy dasturda, masalan, Rec (3) shaklida qo'ng'iroq qilinsa nima bo'lishini ko'rib chiqing. Quyida bayonlarning ketma-ketligini ko'rsatuvchi jadval. Anjir. 1. Rekursiv protseduraning blok diagrammasi. Rec protsedurasi a \u003d 3. parametri bilan chaqiriladi, unda a \u003d 2 parametrli Rec protsedurasiga qo'ng'iroq bor. Oldingi qo'ng'iroq hali tugallanmagan, shuning uchun siz boshqa protsedura yaratilayotganligini tasavvur qilishingiz mumkin va uning ishi oxiriga qadar u o'zining birinchi ishini tugatmaydi. A \u003d 0 parametridan so'ng qo'ng'iroq jarayoni tugaydi. Ayni paytda protseduraning 4 ta nusxasi bir vaqtning o'zida bajariladi. Bir vaqtning o'zida bajariladigan protseduralar soni chaqiriladi rekursiya chuqurligi. (Rec (0)) deb nomlangan to'rtinchi protsedura 0 raqamini bosib chiqaradi va o'z ishini yakunlaydi. Shundan so'ng, boshqaruv uni (Rec (1)) deb nomlangan protseduraga qaytadi va 1-raqam bosiladi va hokazo, barcha protseduralar tugaguncha. Dastlabki qo'ng'iroq natijasi to'rtta raqamni chop etadi: 0, 1, 2, 3. Nima bo'layotganining yana bir vizual tasviri sek. 2. Anjir. 2. Rec protsedurasini 3-parametr bilan bajarish, 2-parametr bilan Rec protsedurasini bajarish va 3-raqamni bosib chiqarish, o'z navbatida, 2-parametr bilan Rec protsedurasini bajarish, 1-parametr bilan Rec protsedurasini bajarish va 2-raqamni bosib chiqarish va boshqalarni o'z ichiga oladi. Mustaqil mashq sifatida Rec (4) ni chaqirganda nima bo'lishini o'ylang. Shuningdek, quyida tasvirlangan Rec2 (4) protsedurasini chaqirganda nima yuz berishi haqida o'ylang, bu erda operatorlar almashadi. Rec2 protsedurasi (a: butun); writeln (a) boshlash; agar a\u003e 0 bo'lsa, Rec2 (a-1); oxiri; Yuqoridagi misollarda rekursiv chaqiruv shartli gapning ichida ekanligini unutmang. Bu rekursiyani to oxirigacha davom ettirish uchun zarur shartdir. Shuni ham yodda tutingki, protseduraning o'zi boshqa parametr bilan chaqiriladi, lekin u chaqirilgandek emas. Agar protsedura global o'zgaruvchilardan foydalanmasa, unda rekursiya cheksiz davom etmasligi kerak. Bir oz murakkabroq sxema mumkin: A funktsiyasi B funktsiyasini chaqiradi va o'z navbatida A ni chaqiradi murakkab rekursiya. Bunday holda, birinchi bo'lib tasvirlangan protsedura hali tavsiflanmagan bo'lishi kerak. Buni amalga oshirish uchun foydalanish kerak. Jarayon A (n: butun son); (Birinchi protseduraning avans tavsifi (nomi)) B protsedurasi (n: butun son); (Ikkinchi protseduraning avans tavsifi) A (n: butun son) protsedurasi; (Protseduraning to'liq tavsifi A) writeln (n) boshlanadi; B (n-1); oxiri; protsedura B (n: butun son); (B protseduraning to'liq tavsifi) boshlanadi wr (n); agar n B protsedurasining batafsil tavsifi sizga uni A protsedurasidan chaqirishga imkon beradi. Ushbu misolda A protsedurasining batafsil tavsifi talab qilinmaydi va estetik sabablarga ko'ra qo'shiladi. Ba'zi dasturlash tillarida umuman tsiklli konstruktsiyalar mavjud emas, bu esa dasturchilarni takrorlash yordamida takrorlashni tashkil qilish uchun qoldiradi (masalan, Prolog, bu erda rekursiya asosiy dasturlash uslubidir). Masalan, for loopning ishini taqlid qiling. Buning uchun, masalan, protsedura parametri sifatida bajarilishi mumkin bo'lgan o'zgaruvchan qadam hisoblagichiga ehtiyoj bor. 1-misol LoopImitatsiya protsedurasi (i, n: butun son); (Birinchi parametr - qadam hisoblagichi, ikkinchi parametr - bu qadamlarning umumiy soni) writeln boshlanadi ("Salom N", i); // Mana, agar i takrorlansa, ko'rsatmalar mavjud LoopImitatsiya turini (1, 10) chaqirish natijasida, hisoblagichlar 1 dan 10 gacha o'zgargan holda ko'rsatmalarning o'n barobar bajarilishi bo'ladi, bu holda u bosadi: Salom N 1 Salom N 2 … Salom N 10 Umuman olganda, protsedura parametrlari hisoblagich qiymatlarining o'zgarishi chegarasi ekanligini ko'rish qiyin emas. Quyidagi misolda bo'lgani kabi, siz takrorlanadigan qo'ng'iroqni va takrorlanadigan ko'rsatmalarni almashtirishingiz mumkin. 2-misol LoopImitation2 protsedurasi (i, n: butun son); agar i Bunday holda, ko'rsatmalar bajarilishidan oldin, protseduraga rekursiv qo'ng'iroq paydo bo'ladi. Hisoblagichning maksimal qiymatiga erishmagunimizcha protseduraning yangi namunasi, avvalambor, boshqa misolni chaqiradi va hokazo. Shundan keyingina (https://fayllar.org/suniy-intellekt-v5.html), chaqirilgan protseduralarning oxirgisi uning ko'rsatmalarini bajaradi, so'ngra oxirgi, ammo bitta ko'rsatmani bajaradi va hokazo. LoopImitatsiya2 (1, 10) ni chaqirish natijasi tabriklarni teskari tartibda chop etadi: Salom N 10 … Salom N 1 Agar biz rekursiv deb ataladigan protseduralar zanjirini tasavvur qilsak, unda 1-misolda biz bundan oldin chaqirilgan protseduralardan keyingilariga o'tamiz. 2-misolda buning teskarisi keyinroq oldingisiga. Va nihoyat, ikkita ko'rsatma bloklari orasiga rekursiv qo'ng'iroqni qo'yish mumkin. Agarda raqam mavjud bo'lsa, uning ikkilik ko'rinishida uning oxirgi raqami bo'ladi. 2 ga bo'linishdan butun sonni olish: biz bir xil ikkilik tasvirga ega bo'lgan sonni olamiz, ammo oxirgi raqamsiz. Shunday qilib, keyingi bo'linish maydoni 0 ga teng butun sonni olguncha yuqoridagi ikkita operatsiyani takrorlash kifoya qiladi. Repsursiz, u quyidagicha bo'ladi: X\u003e 0 boshlanganda c: \u003d x mod 2; x: \u003d x div 2; yozish (c); oxiri; Bu erda muammo shundaki, ikkilik vakillik raqamlari teskari tartibda (birinchi oxiri) hisoblab chiqiladi. Raqamni oddiy shaklda chop etish uchun siz massiv elementlaridagi barcha raqamlarni eslab, ularni alohida tsiklda ko'rsatishingiz kerak. Rekursiondan foydalanib, natijani ketma-ket va ikkinchi bosqichsiz to'g'ri tartibda olish oson. Bu protsedurani chaqirish tartibida bajariladi) c: \u003d x mod 2; x: \u003d x div 2; (Rekursiv qo'ng'iroq) agar x\u003e 0 bo'lsa, BinaryRepresentation (x); (Ikkinchi blok. Bu teskari tartibda bajariladi) yozish (c); oxiri; Umuman olganda, biz hech qanday foyda olmadik. Ikkilik vakillik raqamlari mahalliy o'zgaruvchilarda saqlanadi, ular rekursiv protseduraning har bir ishlaydigan holati uchun farq qiladi. Shunga qaramay, bunday echim menga juda chiroyli ko'rinadi. 4. Takroriy nisbatlar. Rekursiya va takrorlash Agar boshlang'ich vektor va keyingi vektorning oldingi holatga funktsional bog'liqligi bo'lsa, vektorlar ketma-ketligi takrorlanish munosabati bilan beriladi, deyiladi. Takrorlanish munosabatlari yordamida hisoblangan miqdorning oddiy namunasi - bu faktorial Keyingi omilni avvalgisidan hisoblash mumkin: Keyin ketma-ketlikning kerakli elementini hisoblash ularning qiymatlarini takroriy yangilashdan iborat bo'ladi. Bunga misol sifatida taniqli Fibonachchi ketma-ketligini keltirish mumkin, bunda har bir keyingi element oldingi ikki elementning yig'indisidir: "Frontal" yondashuv bilan siz quyidagilarni yozishingiz mumkin: Fib (n: integer): butun son; agar n\u003e 1 bo'lsa, keyin Fib: \u003d Fib (n-1) + Fib (n-2), boshqa tolalar: \u003d 1; oxiri; Har bir Fib qo'ng'irog'i birdaniga ikkita nusxani yaratadi, ularning har biri yana ikkita nusxani yaratadi va hokazo. Operatsiyalar soni soniga qarab o'sib bormoqda n eksponent sifatida, garchi iterativ eritma etarlicha chiziqli bo'lsa ham n operatsiyalar soni. Aslida, bu misol bizga o'rgatmaydi QACHON rekursiya ishlatilmasligi kerak, lekin AS ishlatilmasligi kerak. Oxir-oqibat, agar tez iterativ (ko'chadan asoslangan) echim bo'lsa, xuddi shu pastadir rezursiv protsedura yoki funktsiyadan foydalanib amalga oshirilishi mumkin. Ammo shuni ta'kidlaymizki, munosabatlar (1) - bu ketma-ketlikning sof rekursiv ta'rifi va n-elementni hisoblash f funktsiyani o'zidan ko'p marta olishdir: Xususan, faktorial uchun siz quyidagilarni yozishingiz mumkin: Factorial funktsiyasi (n: butun son): butun; agar n\u003e 1 bo'lsa, undan keyin boshlang'ich: \u003d n * Fakultativ (n-1) else Faktor: \u003d 1; oxiri; Shuni tushunish kerakki, chaqirish funktsiyalari qo'shimcha qo'shimcha xarajatlarni talab qiladi, shuning uchun omilni hisoblashning birinchi varianti biroz tezroq bo'ladi. Umuman olganda, iterativ echimlar rekursiv echimlarga qaraganda tezroq ishlaydi. Rekursiya foydali bo'lgan holatlarga o'tishdan oldin, keling, uni ishlatmaslik kerak bo'lgan yana bir misolga e'tibor qarataylik. XULOSA Takroriy munosabatlarning alohida holatini ko'rib chiqing, agar ketma-ketlikning keyingi qiymati bir biriga emas, balki darhol bir necha oldingi qiymatlarga bog'liq bo'lsa. Bunga misol sifatida taniqli Fibonachchi ketma-ketligini keltirish mumkin, bunda har bir keyingi element oldingi ikki elementning yig'indisidir: "Frontal" yondashuv bilan siz quyidagilarni yozishingiz mumkin: Fib (n: integer): butun son; agar n\u003e 1 bo'lsa, keyin Fib: \u003d Fib (n-1) + Fib (n-2), boshqa tolalar: \u003d 1; oxiri; Har bir Fib qo'ng'irog'i birdaniga ikkita nusxani yaratadi, ularning har biri yana ikkita nusxani yaratadi va hokazo. Operatsiyalar soni soniga qarab o'sib bormoqda n eksponent sifatida, garchi iterativ eritma etarlicha chiziqli bo'lsa ham n operatsiyalar soni ADABIYOTLAR
Алгоритмы: построение и анализ. 3-е изд. / 3. Т.Х.Кормен.Ч.И.Лейзерсон, Р.Л.Ривест, К.Штайн. – М.: Вильямс, 2013. – 1328 с. 4. Вирт Н. Алгоритмы и структуры данных. //М., ДМК, 2010. – 272 с. Даступа С., Пападимтриу Х., Вазирани У. Алгоритмы. – М.: МЦ-НМО, 2014 -320 с. 5. Кнут Д.Э. Искусство программирования. Том 1. Основные алгоритмы. М.: Вильямс, 2010. – 720 с Yüklə 158,14 Kb. Dostları ilə paylaş:
|