Malumotlar tuzilmasi va algoritmlash” fanidan Mustaqil Ish Bajardi: Baxodirjonov Otabek Toshkent 2022

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL – XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
“Malumotlar tuzilmasi va algoritmlash” fanidan
Mustaqil Ish


Bajardi: Baxodirjonov Otabek
Toshkent 2022

Reja:

1. 
   Rekursiyaning mohiyati
   
2. 
   Rekursiya yordamida sikl ishini simulyatsiya
   
3. 
   Takroriy munosabatlar. Rekursiya va iteratsiya
   
   
   

Rekursiya - bu pastki dastur o'zini chaqirganda. Bunday algoritmik konstruktsiyaga birinchi marta duch kelganda, ko'pchilik ma'lum qiyinchiliklarni boshdan kechiradi, biroq ozgina mashq qilsak, rekursiya dasturlash arsenalida tushunarli va juda foydali vositaga aylanadi. 1. Rekursiyaning mohiyati Protsedura yoki funksiya boshqa protsedura yoki funksiyalarga qo'ng'iroqlarni o'z ichiga olishi mumkin. Jumladan, protsedura o'zini chaqirishi mumkin. Bu erda hech qanday paradoks yo'q - kompyuter faqat dasturda duch kelgan buyruqlarni ketma-ket bajaradi va agar protsedura chaqiruviga duch kelsa, u shunchaki ushbu protsedurani bajarishni boshlaydi. Buni amalga oshirish uchun qanday buyruq berilganligi muhim emas. Rekursiv protseduraga misol: Procedure Rec(a: integer); a> bo'lsa boshlang Keling, asosiy dasturga, masalan, Rec(3) ko'rinishdagi qo'ng'iroqni qo'ysak nima bo'lishini ko'rib chiqamiz. Quyida bayonotlar bajarilish ketma-ketligini ko'rsatadigan oqim diagrammasi keltirilgan. Guruch. 1. Rekursiv protseduraning blok diagrammasi. Rec protsedurasi a = 3 parametri bilan chaqiriladi. Unda a = 2 parametrli Rec protsedurasiga qo'ng'iroq mavjud. Oldingi qo'ng'iroq hali tugallanmagan, shuning uchun siz boshqa protsedura yaratilayotganini tasavvur qilishingiz mumkin va birinchisi amalga oshiriladi. ishi tugaguniga qadar ishini tugatmaslik. Qo'ng'iroq jarayoni parametr a = 0 bo'lganda tugaydi. Hozirgi vaqtda protseduraning 4 ta nusxasi bir vaqtning o'zida bajarilmoqda. Bir vaqtning o'zida bajariladigan protseduralar soni chaqiriladi rekursiya chuqurligi.

Biroz murakkabroq sxema bo'lishi mumkin: A funktsiyasi B funktsiyasini chaqiradi, bu esa o'z navbatida A ni chaqiradi. Bu deyiladi murakkab rekursiya. Ma'lum bo'lishicha, birinchi bo'lib tasvirlangan protsedura hali tasvirlanmaganini chaqirishi kerak. Buning mumkin bo'lishi uchun siz dan foydalanishingiz kerak. Protsedura A(n: butun son); (Birinchi protseduraning oldinga tavsifi (sarlavhasi)) B protsedurasi (n: butun son); (Ikkinchi protseduraning oldinga tavsifi) protsedura A(n: butun son); (To'liq protsedura tavsifi A) begin writeln(n); B(n-1); oxiri; B protsedurasi (n: butun son); (B protsedurasining to'liq tavsifi) begin writeln(n); ifn B protsedurasining oldinga e'lon qilinishi uni A protsedurasidan chaqirish imkonini beradi. A protsedurasining oldinga e'lon qilinishi bu misolda talab qilinmaydi va estetik sabablarga ko'ra qo'shilgan. Agar oddiy rekursiyani uroborosga qiyoslash mumkin bo‘lsa unda “Bo‘rilar qo‘rqib bir-birini yeb qo‘ygan” nomli mashhur bolalar she’ridan murakkab rekursiya tasvirini olish mumkin. Ikki bo'ri bir-birini yeyayotganini tasavvur qiling va siz murakkab rekursiyani tushunasiz

Rekursiya yordamida sikl ishini simulyatsiya qiling Agar protsedura o'zini o'zi chaqirsa, unda, aslida, bu uning tarkibidagi ko'rsatmalarning takroriy bajarilishiga olib keladi, bu tsiklning ishlashiga o'xshaydi. Ba'zi dasturlash tillarida aylanma konstruktsiyalar umuman mavjud emas, bu esa dasturchilarni rekursiyadan foydalangan holda takrorlashni tashkil qilishni qoldiradi (masalan, Prolog, bu erda rekursiya asosiy dasturlash texnikasi). Masalan, for siklining ishini simulyatsiya qilaylik. Buning uchun bizga, masalan, protsedura parametri sifatida amalga oshirilishi mumkin bo'lgan qadam hisoblagichi o'zgaruvchisi kerak.

Takroriy munosabatlar. Rekursiya va iteratsiya Aytishlaricha, vektorlar ketma-ketligi, agar boshlang'ich vektor va keyingi vektorning oldingisiga funktsional bog'liqligi berilsa, takrorlanish munosabati bilan beriladi. Qaytalanish munosabatlari yordamida hisoblangan miqdorning oddiy misoli faktorialdir Keyingi faktorialni avvalgisidan quyidagicha hisoblash mumkin: Belgini kiritish orqali biz quyidagi munosabatni olamiz: Formula (1) vektorlari o'zgaruvchan qiymatlar to'plami sifatida talqin qilinishi mumkin. Keyin ketma-ketlikning kerakli elementini hisoblash ularning qiymatlarini qayta-qayta yangilashdan iborat bo'ladi. Xususan, faktorial uchun: X:= 1; i:= 2 uchun n do x:= x * i; writeln(x); Har bir bunday yangilanish (x:= x * i) chaqiriladi iteratsiya, va takroriy takrorlash jarayoni iteratsiya. Biroq, e'tibor bering, (1) munosabat ketma-ketlikning sof rekursiv ta'rifi va n-elementni hisoblash aslida f funktsiyasini o'zidan takroriy olishdir: Xususan, faktorial uchun quyidagilarni yozish mumkin: Function Factorial(n: integer): integer; start agar n > 1 bo'lsa, unda Faktorial:= n * Faktorial(n-1) else Faktorial:= 1; oxiri; Shuni tushunish kerakki, funktsiya chaqiruvlari qo'shimcha xarajatlarni talab qiladi, shuning uchun faktorialni hisoblashning birinchi varianti biroz tezroq bo'ladi.

Umuman olganda, iterativ echimlar rekursivlarga qaraganda tezroq ishlaydi. Rekursiya foydali bo'lgan holatlarga o'tishdan oldin, uni ishlatmaslik kerak bo'lgan yana bir misolni ko'rib chiqaylik. Ketma-ketlikdagi keyingi qiymat bitta emas, balki bir vaqtning o'zida bir nechta oldingi qiymatlarga bog'liq bo'lganda, takrorlanish munosabatlarining alohida holatini ko'rib chiqing.

Misol sifatida taniqli Fibonachchi ketma-ketligi bo'lib, unda har bir keyingi element oldingi ikkita elementning yig'indisidir: "Frontal" yondashuv bilan siz quyidagilarni yozishingiz mumkin: Fib(n: integer): integer; boshlang, agar n > 1 bo'lsa, Fib:= Fib(n-1) + Fib(n-2) boshqa Fib:= 1; oxiri; Fibga har bir qo'ng'iroq bir vaqtning o'zida ikkita nusxasini yaratadi, nusxalarning har biri yana ikkitasini yaratadi va hokazo. Operatsiyalar soni ko'payib boradi n eksponensial ravishda, garchi iterativ yechim uchun, chiziqli n operatsiyalar soni.

Aslida, yuqoridagi misol bizga buni o'rgatmaydi QACHON rekursiya ishlatilmasligi kerak va QANDAY undan foydalanmaslik kerak. Axir, agar tez iterativ (loop-asosli) yechim mavjud bo'lsa, u holda bir xil tsiklni rekursiv protsedura yoki funksiya yordamida amalga oshirish mumkin. Masalan: // x1, x2 – boshlang‘ich shartlar (1, 1) // n – kerakli Fibonachchi soni funksiyasining soni Fib(x1, x2, n: integer): butun son; varx3: butun son; boshlang, agar n > 1 bo'lsa, unda x3 boshlanadi:= x2 + x1; x1:=x2; x2:=x3; Fib:= Fib(x1, x2, n-1); end else Fib:= x2; oxiri; Shunga qaramay, iterativ echimlarga afzallik beriladi. Savol shundaki, qachon rekursiyadan foydalanish kerak? O'zlariga faqat bitta rekursiv qo'ng'iroqni o'z ichiga olgan har qanday rekursiv protseduralar va funktsiyalar iterativ tsikllar bilan osongina almashtiriladi. Oddiy rekursiv bo'lmagan hamkasbi bo'lmagan narsani olish uchun o'zlarini ikki yoki undan ortiq marta chaqiradigan protseduralar va funktsiyalarga murojaat qilish kerak. Bunday holda, chaqirilgan protseduralar to'plami endi rasmdagi kabi zanjir hosil qilmaydi. 1, lekin butun daraxt. Hisoblash jarayoni shu tarzda tashkil etilishi kerak bo'lgan muammolarning keng sinflari mavjud. Faqat ular uchun rekursiya hal qilishning eng oddiy va eng tabiiy usuli bo'ladi.

Daraxtlar O'zini bir necha marta chaqiradigan rekursiv funktsiyalarning nazariy asosi bo'limdir diskret matematika daraxtlarni o'rganish. 5.1. Asosiy ta'riflar. Daraxtlarni tasvirlash usullari Ta'rif: biz chekli to'plamni chaqiramiz T, bir yoki bir nechta tugunlardan iborat bo'lib, shunday qilib: a) Bu daraxtning ildizi deb ataladigan bitta maxsus tugun mavjud. b) Qolgan tugunlar (ildizdan tashqari) har biri o'z navbatida daraxt bo'lgan juft-juft ajratilgan kichik to'plamlarda joylashgan. Daraxtlar deyiladi pastki daraxtlar bu daraxtdan. Ushbu ta'rif rekursivdir. Xulosa qilib aytganda, daraxt - bu ildiz va unga biriktirilgan pastki daraxtlardan tashkil topgan to'plam bo'lib, ular ham daraxtlardir. Daraxt o'zi orqali aniqlanadi. Biroq bu ta'rif mantiqiy, chunki rekursiya cheklangan. Har bir pastki daraxt o'z ichiga olgan daraxtga qaraganda kamroq tugunlarni o'z ichiga oladi. Oxir-oqibat, biz faqat bitta tugunni o'z ichiga olgan pastki daraxtlarga kelamiz va bu nima ekanligi allaqachon aniq.

Shaklda. 3-rasmda etti tugunli daraxt ko'rsatilgan. Oddiy daraxtlar pastdan yuqoriga o'sgan bo'lsa-da, ularni boshqa tomonga chizish odatiy holdir. Diagrammani qo'lda chizishda, bu usul yanada qulayroq ekanligi aniq. Ushbu nomuvofiqlik tufayli, ba'zida tugunlardan biri boshqasidan yuqori yoki pastroq deb aytilganda chalkashlik paydo bo'ladi. Shu sababli, shajarani tavsiflashda, tugunlarni ildiz ajdodlariga yaqinroq va uzoqroq avlodlarni chaqirishda ishlatiladigan atamalardan foydalanish qulayroqdir. Grafik jihatdan, daraxtni boshqa yo'llar bilan tasvirlash mumkin. Ulardan ba'zilari rasmda ko'rsatilgan. 4. Ta'rifga ko'ra, daraxt ichki to'plamlar tizimi bo'lib, bu to'plamlar kesishmaydi yoki bir-birining ichida butunlay joylashadi. Bunday to'plamlarni tekislikdagi hududlar sifatida tasvirlash mumkin (4a-rasm). Shaklda. 4b, ichki o'rnatilgan to'plamlar tekislikda joylashgan emas, balki bitta chiziqda cho'zilgan. Guruch. 4b ni ichki qavslarni o'z ichiga olgan ba'zi algebraik formulalarning diagrammasi sifatida ham ko'rish mumkin. Guruch. 4c daftar ro'yxati sifatida daraxt tuzilishini ko'rsatishning yana bir mashhur usulini beradi.



Daraxt tuzilmalarini ifodalashning boshqa usullari: (a) ichki to'plamlar; (b) ichki qavslar; (c) berilgan ro'yxat. Led ro'yxati kodni formatlash usuliga aniq o'xshaydi. Darhaqiqat, tuzilgan dasturlash paradigmasi doirasida yozilgan dastur ichki o'rnatilgan tuzilmalardan iborat daraxt sifatida ifodalanishi mumkin. Shuningdek, siz kitoblar ro'yxati va mundarijalarning ko'rinishi o'rtasida o'xshashlikni chizishingiz mumkin, bu erda bo'limlar kichik bo'limlarni o'z ichiga oladi, ular o'z navbatida kichik bo'limlarni o'z ichiga oladi va hokazo. Bunday bo'limlarni raqamlashning an'anaviy usuli (1-bo'lim, 1.1 va 1.2-kichik bo'limlar, 1.1.2-kichik bo'limlar va boshqalar) Dewey o'nlik tizimi deb ataladi. Shakldagi daraxtga qo'llanganidek. 3 va 4 ushbu tizim quyidagilarni beradi: 1.A; 1,1B; 1,2C; 1.2.1D; 1.2.2E; 1.2.3F; 1.2.3.1G; 5.2. o'tayotgan daraxtlar Daraxt tuzilmalari bilan bog'liq bo'lgan barcha algoritmlarda bir xil g'oya doimo yuzaga keladi, ya'ni g'oya. o'tish yoki daraxtning o'tishi. Bu har bir tugun bir martadan o'tgan daraxt tugunlariga tashrif buyurishning bir usuli. Bu daraxt tugunlarining chiziqli joylashishiga olib keladi. Xususan, uchta usul mavjud: tugunlarni oldinga, orqaga va orqaga qarab o'tkazishingiz mumkin.

Kompyuter xotirasida daraxt tasviri Agar ba'zi ma'lumotlar daraxtning tugunlarida joylashgan bo'lsa, uni saqlash uchun tegishli dinamik ma'lumotlar strukturasidan foydalanish mumkin. Paskalda bu bir xil turdagi pastki daraxtlarga ko'rsatgichlarni o'z ichiga olgan yozuv tipidagi o'zgaruvchi bilan amalga oshiriladi. Masalan, har bir tugunda butun son bo'lgan ikkilik daraxt quyida tavsiflangan PTree tipidagi o'zgaruvchi yordamida saqlanishi mumkin: PTree = ^TTree turi; TTree = rekord Inf: butun son; LeftSubTree, RightSubTree: PTree; oxiri; Har bir tugun PTree turiga ega. Bu ko'rsatgich, ya'ni har bir tugun undagi New protsedurasini chaqirish orqali yaratilishi kerak. Agar tugun barg tugun bo'lsa, uning LeftSubTree va RightSubTree maydonlari quyidagicha o'rnatiladi. nol. Aks holda, LeftSubTree va RightSubTree tugunlari ham Yangi protsedura yordamida yaratiladi. Sxematik tarzda, bunday yozuvlardan biri rasmda ko'rsatilgan. 5.

Guruch. 5. TTree yozuvining sxematik tasviri. Yozuv uchta maydonga ega: Inf - ba'zi raqamlar, LeftSubTree va RightSubTree - bir xil TTree tipidagi yozuvlarga ko'rsatgichlar. Bunday yozuvlardan tuzilgan daraxt misoli 6-rasmda keltirilgan.

Guruch. 6. TTree tipidagi yozuvlardan tuzilgan daraxt.

Har bir yozuv o'z ichiga olishi mumkin bo'lgan raqam va ikkita ko'rsatgichni saqlaydi nol, yoki bir xil turdagi boshqa yozuvlar manzillari. Agar siz ilgari bir xil turdagi yozuvlarga havolalarni o'z ichiga olgan yozuvlardan iborat tuzilmalar bilan ishlamagan bo'lsangiz, unda material bilan tanishib chiqishingizni tavsiya qilamiz. 6. Rekursiv algoritmlarga misollar 6.1. daraxt chizish Shaklda ko'rsatilgan daraxtni chizish algoritmini ko'rib chiqing. 6. Agar har bir chiziq tugun deb hisoblansa, u holda bu rasm oldingi bobda berilgan daraxt ta'rifini to'liq qondiradi.



Rekursiv tartib aniq bir chiziq chizadi (magistraldan birinchi vilkagacha) va keyin ikkita pastki daraxt chizish uchun o'zini chaqiradi. Subdaraxtlar o'z ichiga olgan daraxtdan boshlang'ich nuqtasi koordinatalari, burilish burchagi, magistral uzunligi va ulardagi novdalar soni (bitta kam) bilan farqlanadi. Bu farqlarning barchasi rekursiv protsedura parametrlari bo'lishi kerak.

Afsonaga ko'ra, Benaras shahridagi Buyuk ibodatxonada, dunyoning o'rtasini ko'rsatadigan sobor ostida bronza disk joylashgan bo'lib, unga 3 ta olmos tayoq o'rnatilgan, balandligi bir tirsak va ari kabi qalin. Qadim zamonlarda, eng boshida, bu monastirning rohiblari Brama xudosi oldida aybdor edilar. G'azablangan Brahma uchta baland tayoq o'rnatdi va ulardan biriga 64 ta sof oltin disklarni qo'ydi va har bir kichik disk kattaroqqa yotadi. Barcha 64 ta disk dunyoni yaratishda Xudo Brahma ularni qo'ygan tayoqdan boshqa tayoqqa o'tkazilishi bilanoq, minora ma'bad bilan birga changga aylanadi va dunyo momaqaldiroq ostida halok bo'ladi. Jarayonda kattaroq disk hech qachon kichikroqning ustiga qo'yilmasligi talab qilinadi. Rohiblar qiyinchilikda, siljishlar qanday ketma-ketlikda amalga oshirilishi kerak? Ularni ushbu ketma-ketlikni hisoblash uchun dasturiy ta'minot bilan ta'minlash talab qilinadi. Bramaga qaramasdan, bu jumboq 19-asrning oxirida frantsuz matematigi Eduard Lukas tomonidan taklif qilingan. Sotilgan versiyada odatda 7-8 disk ishlatilgan (7-rasm).

Tahlil qilish vazifasi ifoda qiymatini hisoblash uchun arifmetik ifodani va unga kiritilgan o'zgaruvchilarning ma'lum qiymatlarini o'z ichiga olgan mavjud satrdan foydalanishdir. Arifmetik ifodalarni hisoblash jarayoni ikkilik daraxt sifatida ifodalanishi mumkin. Darhaqiqat, arifmetik operatorlarning har biri (+, -, *, /) ikkita operandni talab qiladi, ular ham arifmetik ifodalar bo'ladi va shunga ko'ra, pastki daraxtlar sifatida ko'rib chiqilishi mumkin. Guruch. 8 ifodaga mos keladigan daraxt misoli ko'rsatilgan

Bunday daraxtda barg tugunlari har doim o'zgaruvchan bo'ladi (bu erda x) yoki raqamli doimiylar va barcha ichki tugunlar arifmetik operatorlarni o'z ichiga oladi. Operatorni bajarish uchun avvalo uning operandlarini baholash kerak. Shunday qilib, rasmdagi daraxt oxirgi tartibda o'tishi kerak. Tegishli tugunlar ketma-ketligi chaqirdi teskari jilo belgisi arifmetik ifoda. Sintaksis daraxtini qurishda siz e'tibor berishingiz kerak keyingi xususiyat. Agar, masalan, ifoda mavjud bo'lsa va biz chapdan o'ngga qo'shish va ayirish amallarini o'qiymiz, keyin to'g'ri sintaksis daraxti ortiqcha o'rniga minusni o'z ichiga oladi (9a-rasm). Aslida bu daraxt ifodaga mos keladi.(8) ifodani teskari, o‘ngdan chapga qarab tahlil qilsak, daraxtni tuzishni osonlashtirish mumkin. Bunday holda, shaklda ko'rsatilgan daraxt. 9b, bu 8a daraxtiga teng, ammo belgini almashtirishni talab qilmaydi. Xuddi shunday, o'ngdan chapga ko'paytirish va bo'lish operatorlarini o'z ichiga olgan ifodalarni tahlil qilish kerak.

Guruch. 9. Ifoda uchun sintaksis daraxtlari a – b + c chapdan o'ngga (a) va o'ngdan chapga (b) o'qiyotganda. Ushbu yondashuv rekursiyani butunlay yo'q qilmaydi. Biroq, bu o'zingizni rekursiv protseduraga faqat bitta qo'ng'iroq bilan cheklash imkonini beradi, agar motiv maksimal ishlash uchun tashvish bo'lsa, bu etarli bo'lishi mumkin. 7.3. Daraxt tugunini uning soni bo'yicha aniqlash Ushbu yondashuvning g'oyasi rekursiv qo'ng'iroqlarni oddiy tsikl bilan almashtirishdan iborat bo'lib, u daraxtda rekursiv protseduralar natijasida hosil bo'lgan tugunlar qanchalik ko'p bo'lsa, shuncha marta bajariladi. Har bir qadamda aniq nima qilinishini qadam raqami bilan aniqlash kerak.
Qadam raqami va kerakli harakatlarni taqqoslash ahamiyatsiz ish emas va har bir holatda uni alohida hal qilish kerak bo'ladi. Misol uchun, qilmoqchisiz deylik k o'rnatilgan halqalar yoqilgan n Har bir bosqichda: i1:= 0 dan n-1 gacha i2 uchun bajaring:= 0 dan n-1 gacha i3 uchun bajaring:= 0 dan n-1 gacha bajaring… Agar a k oldindan ma'lum emas, keyin yuqorida ko'rsatilgandek, ularni aniq yozish mumkin emas. 6.5-bo'limda ko'rsatilgan texnikadan foydalanib, siz rekursiv protsedura yordamida kerakli miqdordagi o'rnatilgan halqalarni olishingiz mumkin:

Procedure NestedCycles(Indekslar: integer massivi; n, k, chuqurlik: integer); var i: integer; chuqurlikdan boshlang Rekursiyadan xalos bo'lish va hamma narsani bitta tsiklga qisqartirish uchun, agar biz sanoq sistemasidagi qadamlarni baza bilan raqamlasak, e'tibor bering. n, keyin har bir qadam i1, i2, i3, ... raqamlaridan yoki Indekslar massividagi mos qiymatlardan iborat raqamga ega.

Ya'ni, raqamlar tsikl hisoblagichlarining qiymatlariga mos keladi. Odatiy o'nlik sanoq sistemasidagi qadam raqami: Jami qadamlar bo'ladi nk. O'nlik sanoq sistemasida ularning sonlarini saralab, ularning har birini asosli tizimga aylantirgandan so'ng n, biz indeks qiymatlarini olamiz: M:= round(IntPower(n, k)); uchun i:= 0 dan M-1 gacha boshlanadi Raqam:= i; for p:= 0 to k-1 do start Indexes := Number mod n; Raqam:= Raqam div n; oxiri; DoSomething (indekslar); oxiri; Yana bir bor ta'kidlaymizki, usul universal emas va har bir vazifa uchun siz o'zingizning biror narsangizni topishingiz kerak bo'ladi.