Mavzu: Rekursiya va uni dasturlashda ishlatish

MAVZU:Rekursiya va uni dasturlashda ishlatish.
REJA;
Rekursiv algoritmlar, ularning tahlili. Rekursiyaga doir misollar.
Daraxtsimon maʻlumotlar tuzilmalari. Taʻriflar va xususiyatlar.
Daraxtlar klassifikatsiyasi.
Daraxt ko‘ruvi.
Ikkilik daraxtlar va ular ustida amallar. Ikkilik daraxtga element qo‘shish, element o‘chirish va qidiruv algoritmlari Muvozanatlangan ikkilik daraxtlar.
Muvozanatlash algoritmlari: muvozanatlashning umumiy va hususiy algoritmlari.
AVL daraxti Heap tree ko‘rinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar.
Heap tree tuzilmasi tavsifi. Heap tree ustida amal bajarish algoritmlari. Heap treeni tashkil etish usullari va samaradorligi.
Maʻlumotlar tarmoq tuzilmalari.
Graf tushunchasi va uning ko‘rinishlari.

Umumiy kompyuter dasturlash taktika - bu muammoni asl nusxadagi bir xil turdagi pastki muammolarga ajratish, ushbu kichik muammolarni echish va natijalarni birlashtirish. Bunga ko'pincha ajratish va zabt etish usuli; a bilan birikganda qidiruv jadvali sub-muammolarni echish natijalarini saqlaydigan (ularni qayta-qayta hal qilmaslik va qo'shimcha hisoblash vaqtiga yo'l qo'ymaslik uchun) dinamik dasturlash yoki yod olish.
Rekursiv funktsiya ta'rifi bir yoki bir nechtasiga ega asosiy holatlar, funktsiya natijani beradigan kirish (lar) ni anglatadi ahamiyatsiz (takrorlanmasdan), va bitta yoki bir nechtasi rekursiv holatlar, dastur takrorlanadigan kirish (lar) ni anglatadi (o'zini o'zi chaqiradi). Masalan, faktorial funktsiyani tenglamalar bilan rekursiv ravishda aniqlash mumkin 0! = 1 va hamma uchun n > 0, n! = n(n − 1)!. Ikkala tenglama ham o'z-o'zidan to'liq ta'rifni tashkil etmaydi; birinchisi - asosiy, ikkinchisi - rekursiv holat. Asosiy ish rekursiya zanjirini uzganligi sababli, ba'zan uni "tugatuvchi ish" ham deyishadi.

Rekursiv holatlarning ishi murakkab yozuvlarni oddiylariga ajratish sifatida qaralishi mumkin. To'g'ri ishlab chiqilgan rekursiv funktsiyasida, har bir rekursiv chaqiriq bilan, kiritish muammosi shunday soddalashtirilishi kerakki, oxir-oqibat asosiy holatga erishish kerak. (Oddiy sharoitlarda tugatish uchun mo'ljallanmagan funktsiyalar - masalan, ba'zilari tizim va server jarayonlari - bu bundan mustasno.) Asosiy ishni yozishga beparvolik qilish yoki uni noto'g'ri tekshirish, sabab bo'lishi mumkin cheksiz pastadir.
Ba'zi funktsiyalar uchun (masalan, seriyali uchun e = 1/0! + 1/1! + 1/2! + 1/3! + ...) kirish ma'lumotlari nazarda tutilgan aniq bazaviy holat mavjud emas; chunki bu qo'shilishi mumkin parametr (masalan, qator misolida qo'shiladigan atamalar soni kabi) asosiy holatni o'rnatadigan "to'xtash mezonini" ta'minlash uchun. Bunday misol tabiiy ravishda davolanadi kelishuv,[Qanaqasiga? ] bu erda mahsulotning ketma-ket shartlari qisman yig'indilar; buni indeksatsiya parametridan foydalanib, "hisoblash" deyish bilan rekursiyaga o'tkazish mumkin nth muddat (nth qisman sum) ".

Download 0.98 Mb.