Rekursiya ma'lumotlar tuzilmasi

Rekursiya - ma'lumotlar tuzilmasi
Funktsiyaning o'zini bevosita yoki bilvosita chaqirishi jarayoni deyiladi
rekursiya va unga mos keladigan funksiya rekursiv funksiya deb ataladi. Foydalanish
Rekursiv algoritmga ko'ra, ba'zi muammolarni juda oson hal qilish mumkin.
Bunday muammolarga Xanoy minoralarini misol qilib keltirish mumkin
(TOH), Inorder/Preorder/Pstorder Tree Transals, DFS of Graph,
va boshqalar.
Matematik talqin:
Keling, dasturchi yig'indisini aniqlashi kerak bo'lgan masalani ko'rib chiqaylik
birinchi n natural son, buni qilishning bir necha yo'li bor, lekin eng oddiy
yondashuv oddiygina 1 dan n gacha bo'lgan raqamlarni qo'shishdir. Shunday qilib, funktsiya
oddiygina o'xshaydi,
yondashuv (1) - oddiygina birma-bir qo'shish
f(n) = 1 + 2 + 3 +……..+ n
Rekursiya - ma'lumotlar tuzilmasi
lekin buni ifodalashning boshqa matematik yondashuvi mavjud,
yondashuv (2) - Rekursiv qo'shish
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
Yondashuv (1) va o'rtasida oddiy farq bor
yondashuv (2) va bu (2) yondashuvda “ f( ) ” funksiyasining o‘zi
funktsiya ichida chaqiriladi, shuning uchun bu hodisa nomlanadi
rekursiya sifatida va rekursiyani o'z ichiga olgan funksiya deyiladi
rekursiv funktsiya, oxirida bu qo'lida ajoyib vosita
dasturchilar ba'zi muammolarni juda oson va samarali kodlash uchun
yo'l.
Rekursiyadagi asosiy holat
Rekursiv dasturda asosiy holatning yechimi taqdim etiladi va
kattaroq muammoning yechimi kichikroq masalalarda ifodalanadi.
Yuqoridagi misolda n < = 1 uchun asosiy registr aniqlangan va ning kattaroq qiymati
sonni asosiy holga yetguncha kichikroqqa aylantirish orqali hal qilish mumkin.
To'g'ridan-to'g'ri va bilvosita rekursiya o'rtasidagi farq
Funktsiya bir xil funktsiyani qiziqarli deb atasa, to'g'ridan-to'g'ri rekursiv deyiladi. A
Fun funksiyasi bilvosita rekursiv deyiladi, agar u boshqa funktsiyani chaqirsa, fun_new deylik
va fun_new to'g'ridan-to'g'ri yoki bilvosita qiziqarli qo'ng'iroqlar. To'g'ridan-to'g'ri va o'rtasidagi farq
bilvosita rekursiya tasvirlangan
Quyruqli va quyruqsiz rekursiya o'rtasidagi farq
Rekursiv qo'ng'iroq oxirgi narsa bo'lsa, rekursiv funktsiya quyruq rekursiv hisoblanadi
funktsiyasi tomonidan bajariladi.
Rekursiyada turli funksiya chaqiruvlariga xotira qanday ajratiladi? Har qanday funktsiya main() dan chaqirilganda unga xotira ajratiladi
stack. Rekursiv funktsiya o'zini chaqiradi, chaqirilgan funksiya uchun xotira
chaqiruv funksiyasiga ajratilgan xotira ustiga ajratilgan va boshqa nusxasi
har bir funktsiya chaqiruvi uchun mahalliy o'zgaruvchilar yaratiladi.
Asosiy holatga erishilganda, funktsiya o'z qiymatini funktsiyaga qaytaradi
kim tomonidan chaqiriladi va xotira ajratiladi va jarayon davom etadi.
Rekursiyaning ishlashini ko'rsatish uchun C++ dasturi
Rekursiyaning ishlashini ko'rsatish uchun C++ dasturi
printFun(3) main() dan chaqirilganda xotira ajratiladi
printFun(3) ga to'g'ri keladi va mahalliy o'zgaruvchi testi 3 ga va 1 ga o'rnatiladi
Quyidagi diagrammada ko'rsatilganidek, 4 ta stack ustiga suriladi.
U birinchi navbatda "3" ni chop etadi. 2-bandda printFun(2) chaqiriladi va xotira
printFun(2) ga ajratiladi va mahalliy o'zgaruvchi testi 2 va ga ishga tushiriladi
1 dan 4 gacha bo'lgan bayonotlar stekga suriladi.
Xuddi shunday, printFun(2) printFun(1) va printFun(1) printFun(0) ni chaqiradi.
). printFun(0) if operatoriga o'tadi va printFun(1) ga qaytadi.
printFun(1) ning qolgan bayonotlari bajariladi va u qaytadi
chop etish uchunFun(2) va hokazo.
Chiqishda 3 dan 1 gacha bo'lgan qiymatlar, keyin esa 1 dan 3 gacha bo'lgan qiymatlar chop etiladi. The
xotira to'plami quyidagi diagrammada ko'rsatilgan.
Xotira to'plami
Topish uchun dastur va takrorlanish munosabati
Fibonachchi qatori n bu yerda n>2 .
Fibonachchi seriyasini amalga oshirish uchun C++ kodi
Fibonachchi seriyasini amalga oshirish uchun C++ kodi
Rekursiv daraxt
Mana 5-kirish uchun rekursiv daraxt, bu qanchalik katta ekanligini aniq ko'rsatadi
muammoni kichikroq qilib hal qilish mumkin.
fib(n) - Fibonachchi funktsiyasi. Berilgan dasturning vaqt murakkabligi mumkin
funktsiya chaqiruviga bog'liq.
Topish uchun dastur va takrorlanish munosabati n ning faktoriali, bunda n>2
Matematik tenglama:
1, agar n == 0 yoki n == 1 bo'lsa; f(n) = n*f(n-1) agar n> 1 bo‘lsa;
Qaytalanish munosabati:
T(n) = 1 uchun n = 0 T(n) = 1 + T(n-1) n > 0 uchun
Rekursiv dastur:
Kirish: n = 5
Chiqish:
5 ning faktoriali: 120
Faktorialni amalga oshirish uchun C++ kodi
Faktorial rekursiya
Rekursiv dasturlashning takroriy dasturlashdan ustun va kamchiliklari
Rekursiv dasturlashning iterativga nisbatan qanday kamchiliklari bor
dasturlash?
E'tibor bering, rekursiv va iterativ dasturlar bir xil
muammoni hal qilish vakolatlari, ya'ni har bir rekursiv dastur yozilishi mumkin
iterativ va aksincha ham to'g'ri. Rekursiv dastur kattaroqdir
iterativ dasturdan ko'ra bo'sh joy talablari, chunki barcha funktsiyalar ichida qoladi
asosiy qutiga yetguncha stack. Bundan tashqari, ko'proq vaqt talablari mavjud
funktsiya chaqiruvlari va qaytariladigan yuklar tufayli.
Rekursiv dasturlashning iterativga nisbatan qanday afzalliklari bor
dasturlash?
Rekursiya kod yozishning toza va oddiy usulini ta'minlaydi. Ba'zi muammolar
Daraxtlarni kesib o'tish, Xanoy minorasi va boshqalar kabi tabiatan rekursiv. Bundaylar uchun
Muammolar uchun rekursiv kod yozish afzalroqdir. Bunday kodlarni ham yozishimiz mumkin
stek ma'lumotlar strukturasi yordamida iterativ tarzda.
Stack ma'lumotlar tuzilmasi
Stack - bu ma'lum bir tartibda bo'lgan chiziqli ma'lumotlar strukturasi
operatsiyalar bajariladi. Buyurtma LIFO (oxirgi kiruvchi birinchi chiqadi) yoki bo'lishi mumkin
FILO (birinchi, oxirgisi). Stackning hayotiy misollari ko'p. Plitalar misolini ko'rib chiqing
oshxonada bir-birining ustiga qo'yilgan.
Yuqorida joylashgan plastinka birinchi bo'lib chiqariladi, ya'ni plastinka
uchun eng pastki holatda qo'yilgan stekda qoladi
eng uzoq vaqt davri.
Stack ma'lumotlar tuzilmasi
Shunday qilib, LIFO (Oxirgi birinchi navbatda) ga amal qilishni oddiygina ko'rish mumkin
Chiqib ketgan)/FILO(First In Last Out) tartibi.
Asosan quyidagi uchta asosiy operatsiya bajariladi
stek:
Push: stekdagi elementni qo'shadi. Agar stack to'lgan bo'lsa, unda aytiladi
toshib ketish holati bo'lishi.
Pop: stekdan elementni olib tashlaydi. Elementlar ochiladi
ular surishning teskari tartibi. Agar to'plam bo'sh bo'lsa,
keyin u Underflow holati deyiladi.
Peek yoki Top: stekning yuqori elementini qaytaradi.
isEmpty: Agar stek bo'sh bo'lsa, true qiymatini qaytaradi, aks holda noto'g'ri.
Stack ma'lumotlar tuzilmasi
Stekni amalda qanday tushunish mumkin?
Stackning hayotiy misollari ko'p.
Oshxonada bir-birining ustiga qo'yilgan plitalarning oddiy misolini ko'rib chiqing.
Yuqorida joylashgan plastinka birinchi bo'lib chiqariladi, ya'ni plastinka
uchun eng pastki holatda qo'yilgan stekda qoladi
eng uzoq vaqt davri.
Shunday qilib, LIFO/FILO tartibiga amal qilishni oddiygina ko'rish mumkin.
Stackdagi operatsiyalarning vaqt murakkabligi:
push(), pop(), isEmpty() va peek() hammasi O(1) vaqtini oladi.
Ushbu operatsiyalarning hech birida biz tsiklni bajarmaymiz.
Stack ilovalari
Belgilarni muvozanatlash
Infix to Postfix/Prefiks konvertatsiyasi
Muharrirlar, fotoshop kabi ko'plab joylarda qayta tiklash-bekor qilish funksiyalari.
Veb-brauzerlarda oldinga va orqaga qaytish funksiyasi
Xanoy minorasi, daraxtlarni kesib o'tish, zaxiralar oralig'i kabi ko'plab algoritmlarda qo'llaniladi
muammo, gistogramma muammosi.
Backtracking algoritmni loyihalash usullaridan biridir. Ba'zi misollar
orqaga qaytish - bu Knight-Tour muammosi, N-Queen muammosi, yo'lingizni toping
bir labirint orqali, va o'yin kabi shaxmat yoki shashka barcha bu muammolar biz
Agar bu usul samarali bo'lmasa, biz avvalgisiga qaytamiz
davlat va boshqa yo'lga o'ting.
Joriy holatdan qaytish uchun oldingi holatni saqlashimiz kerak
maqsad uchun bizga stack kerak.
Stack ilovalari Topologik tartiblash va kuchli bog'liqlik kabi grafik algoritmlarida
Komponentlar Xotirani boshqarishda har qanday zamonaviy kompyuter stek sifatida foydalanadi
ishlaydigan maqsad uchun asosiy boshqaruv.
Kompyuter tizimida ishlaydigan har bir dastur o'z xotirasiga ega
ajratmalar
Stringni teskari aylantirish ham stekning yana bir ilovasidir. Bu erda birma-bir
belgi stekga kiritiladi. Shunday qilib, satrning birinchi belgisi yoqilgan
stekning pastki qismi va satrning oxirgi elementi tepada joylashgan
stack. Stackda pop operatsiyalarini bajarganimizdan so'ng, biz qatorni olamiz
teskari tartib.
Amalga oshirish:
Stackni amalga oshirishning ikki yo'li mavjud:
Massivdan foydalanish
Bog'langan ro'yxatdan foydalanish
Massivlar yordamida stackni amalga oshirish
Massivlar yordamida stackni amalga oshirish
Massivlar yordamida stackni amalga oshirish
Navbatdagi ma'lumotlar tuzilmasi
Navbat - bu ma'lum bir tartibda bo'lgan chiziqli tuzilma
operatsiyalar bajariladi. Buyurtma birinchi kiruvchi birinchi chiqadi (FIFO).
Navbatning yaxshi namunasi - bu resurs uchun iste'molchilarning har qanday navbati
birinchi kelgan iste'molchiga birinchi bo'lib xizmat ko'rsatiladi. Farqi
steklar va navbatlar o'rtasida olib tashlash.
Stackda biz oxirgi qo'shilgan elementni olib tashlaymiz; navbatda, biz
eng yaqinda qo'shilgan elementni olib tashlang.
Navbatdagi ma'lumotlar strukturasining ilovalari
Navbat narsalarni zudlik bilan qayta ishlash kerak bo'lmaganda, lekin mavjud bo'lganda ishlatiladi
Breadth First Search kabi birinchi navbatda birinchi chiqish tartibida qayta ishlanadi. Bu
Queue xususiyati uni quyidagi stsenariylarda ham foydali qiladi
1) Resurs bir nechta iste'molchilar o'rtasida taqsimlanganda. Misollar
CPU rejalashtirishni, Diskni rejalashtirishni o'z ichiga oladi.
2) Ma'lumotlar asinxron ravishda uzatilganda (ma'lumotlar qabul qilinishi shart emas
ikki jarayon o'rtasida yuborilgan tezlik bilan bir xil. Masalan, IO buferlari,
quvurlar, IO fayli va boshqalar.
3) Operatsion tizimlarda:
a) semaforlar
b) FCFS (birinchi kelgan birinchi xizmat) jadvali, misol: FIFO navbati
c) Printerlarda spoullash
d) Klaviatura kabi qurilmalar uchun bufer
Navbatdagi ma'lumotlar strukturasining ilovalari
4) Tarmoqlarda:
a) Routerlar/kommutatorlardagi navbatlar
b) Pochta navbatlari
5) Variatsiyalar: (Deque, Priority Queue, Double End Priority Queue )
Ustuvor navbat
Priority Queue - bu navbatga o'xshash mavhum ma'lumotlar turi, ammo
ustuvor navbatda, har bir element qandaydir ustuvorlikka ega. ning ustuvorligi
ustuvor navbatdagi elementlar elementlarning joylashish tartibini belgilaydi ustuvor navbatdan olib tashlandi. Shuning uchun barcha elementlar bir xil
o'sish yoki kamayish tartibida joylashtirilgan.
Shunday qilib, ustuvor navbat - bu navbatning quyidagi bilan kengayishi
xususiyatlari.
Prioritet navbatning xususiyatlari
Har bir element u bilan bog'liq ustuvorlikka ega.
Yuqori ustunlikka ega element past ustuvorlikdagi elementdan oldin navbatdan chiqariladi.
Agar ikkita element bir xil ustuvorlikka ega bo'lsa, ularga muvofiq xizmat ko'rsatiladi
navbatda buyurtma berish
Oddiy ustuvor navbat quyidagi operatsiyalarni qo'llab-quvvatlaydi:
1) Qo'shish: yangi element ustuvor navbatga kiritilganda, u harakatlanadi
yuqoridan pastga va chapdan o'ngga bo'sh uyaga.
Biroq, agar element to'g'ri joyda bo'lmasa, u taqqoslanadi
ota-ona tugun bilan.
Agar element to'g'ri tartibda bo'lmasa, elementlar almashtiriladi. The
almashtirish jarayoni barcha elementlar to'g'ri joylashtirilguncha davom etadi
Pozitsiya.Ustuvor navbatdagi operatsiyalar
2) O'chirish: Ma'lumki, maksimal to'pda maksimal
element ildiz tugunidir. Va u mavjud bo'lgan elementni olib tashlaydi
birinchi navbatda maksimal ustuvorlik.
Shunday qilib, ildiz tugunini navbatdan olib tashlaysiz. Bu olib tashlash
bo'sh uyani yaratadi, u yanada yangi bilan to'ldiriladi
kiritish.
Keyin u yangi kiritilgan elementni barcha bilan solishtiradi
yig'ma invariantni saqlash uchun navbat ichidagi elementlar.
3) Peek: Bu operatsiya maksimal elementni qaytarishga yordam beradi
Max Heap dan yoki Min Heap dan minimal elementsiz
tugunni ustuvor navbatdan o'chirish.
Ustuvor navbat turlari
1) O'sish tartibi: Nomidan ko'rinib turibdiki, o'sish tartibida ustuvorlikda
navbatda, pastroq ustunlik qiymatiga ega elementga yuqoriroq ustunlik beriladi
ustuvorlik ro'yxati
Misol uchun, agar bizda ustuvor navbatda quyidagi elementlar mavjud bo'lsa
4,6,8,9,10 kabi o'sish tartibi. Bu erda 4 eng kichik raqam, shuning uchun u
ustuvor navbatda eng yuqori ustuvorlikni oladi.
2) Kamayish tartibi: Ildiz tugun maks.dagi maksimal element
to'p, siz bilganingizdek. Bundan tashqari, u eng yuqori bo'lgan elementni olib tashlaydi
birinchi navbatda.
Natijada, ildiz tugunlari navbatdan chiqariladi. Bu o'chirish a qoldiradi
kelajakda yangi qo'shimchalar bilan to'ldiriladigan bo'sh joy. Uyum
yangi kiritilgan elementni hamma bilan solishtirish orqali o'zgarmaslik saqlanib qoladi
navbatdagi boshqa yozuvlar.
Prioritet navbatni qanday amalga oshirish kerak?
Ustuvor navbat quyidagi ma'lumotlar tuzilmalari yordamida amalga oshirilishi mumkin:
Massivlar
Bog'langan ro'yxat
Uyma ma'lumotlar tuzilishi
Ikkilik qidiruv daraxti
Keling, bularning barchasini batafsil muhokama qilaylik. 1) Massivdan foydalanish: oddiy dastur quyidagi massivdan foydalanishdir
tuzilishi.
tuzilish elementi {
int element;
int ustuvorligi;
enqueue(): Bu funksiya navbatga yangi ma'lumotlarni kiritish uchun ishlatiladi.
Priority Queue dasturini amalga oshirish uchun C++ dasturi
dequeue(): Bu funksiya eng yuqori ustunlikka ega elementni olib tashlaydi
navbat.
peek()/top(): Bu funksiya eng yuqori ustuvor elementni olish uchun ishlatiladi
uni navbatdan olib tashlamasdan navbatga qo'ying.
// Priority Queue-ni amalga oshirish uchun C++ dasturi
// massivlar yordamida
#include
std nom maydonidan foydalanish;
// dagi elementlar uchun tuzilma
// ustuvor navbat
tuzilish elementi {
int qiymati;
Priority Queue dasturini amalga oshirish uchun C++ dasturi
int ustuvorligi;
};
// ustuvor navbat elementini saqlash
element pr [100000];
// Oxirgi indeksga ko'rsatgich
int hajmi = -1;
// Yangi element kiritish funksiyasi
// ustuvor navbatga
bekor qatori (int qiymati, int ustuvorligi)
// Hajmini oshiring
hajmi++;
Priority Queue dasturini amalga oshirish uchun C++ dasturi
// Elementni kiriting
pr[size].value = qiymat;
pr[size].priority = ustuvorlik;
// Yuqori elementni tekshirish funksiyasi
int peek()
{
int highPriority = INT_MIN;
int ind = -1;
// Element mavjudligini tekshiring
// eng yuqori ustuvorlik
uchun (int i = 0; i <= o'lcham; i++) {
Priority Queue dasturini amalga oshirish uchun C++ dasturi
// Agar ustuvorlik bir xil bo'lsa, tanlang
// bilan element
// eng yuqori qiymat agar (highestPriority == pr[i].priority && ind > -1
&& pr[ind].value < pr[i].value) {
highPriority = pr[i].priority;
ind = i;
}
else if (eng yuqori ustuvorlik < pr[i].priority) {
highPriority = pr[i].priority;
ind = i;
}
}
Priority Queue dasturini amalga oshirish uchun C++ dasturi
// Elementning o'rnini qaytarish
qaytish ind;
}
// Elementni olib tashlash funksiyasi
// eng yuqori ustuvorlik
bekor qilish()
// Elementning o'rnini toping
// eng yuqori ustuvorlik bilan
int ind = peek();
// Elementni bir indeksdan oldin siljiting
// element pozitsiyasidan
// eng yuqori ustuvorlik topildi
Priority Queue dasturini amalga oshirish uchun C++ dasturi
uchun (int i = ind; i < o'lcham; i++) {
pr[i] = pr[i + 1]
// o'lchamini kamaytiring
// bir qator ustuvor navbat
hajmi --;
/ Haydovchi kodi
int main()

// Elementlarni kiritish uchun funksiya chaqiruvi

Priority Queue dasturini amalga oshirish uchun C++ dasturi
uchun (int i = ind; i < o'lcham; i++) {
pr[i] = pr[i + 1];
// o'lchamini kamaytiring
// bir qator ustuvor navbat
hajmi --;}
// Haydovchi kodi
int main()
// Elementlarni kiritish uchun funksiya chaqiruvi
Priority Queue dasturini amalga oshirish uchun C++ dasturi
// ustuvorlikka ko'ra navbat (10, 2);
navbat (14, 4);
navbat (16, 4);
navbat (12, 3);
// Yuqori elementni saqlaydi
// hozirgi paytda
int ind = peek();
cout << pr[ind].value << endl;
// Yuqori elementni o'chirish
dequeue();
Priority Queue dasturini amalga oshirish uchun C++ dasturi
// Yuqori elementni tekshiring
ind = peek();
cout << pr[ind].value << endl;
// Yuqori elementni o'chirish
dequeue();
// Yuqori elementni tekshiring
ind = peek();
cout << pr[ind].value << endl;
qaytish 0;
Chiqish
16
14
12
Mustaqil ish
Ikkilik qidiruv daraxtlari. Kiritishning vaqt murakkabligi va
qidirmoq
Prioritet navbatlar va to'plangan daraxtlar. Asosiy operatsiyalar
ikkilik yigʻma daraxt.16.8.2021
Yechilgan takrorlanish daraxti usuli haqida qisqacha video
https://www.youtube.com/watch?v=sL
NPd_nPGIc