Algoritmlarning xossalari Algoritmning asosiy xossalari. Algoritmning 5-ta asosiy xossasi bor: Diskretlilik Cheklilik

Foydalanilgan adabiyotlar:
V.A. Evstigneev, V.N. Kasyanov. Kompyuter fanida grafikalar lug'ati. - Novosibirsk. - (Dasturni qurish va optimallashtirish). - ISBN 978-591124-036-3.
Fodry, Ralf; Flandrin, Evelin va Ryachecek, Zdeněk (1997), tirnoqsiz grafikalar - sharh, diskret matematika T. 164 (1-3): 87-147, DOI 10.1016 / S0012-365X (96) 00045-3.
Gottlieb J.; Julstrom, B. A .; Rotlauf, F. va Raidl, G.R. (2001), afzal raqamlar: evolyutsiyani qidirish uchun daraxtlarning kam vakili, Proc. Genetik va evolyutsion hisoblash bo'yicha konferentsiya, Morgan Kaufmann, p. 343-350,
4-Mavzu: Rekursiv algoritmlar va ularning vazifalari
Rekursiya - bu subroutine o'zini o'zi chaqiradi. Bunday algoritmik tuzilishga birinchi marta duch kelganda, ko'pchilik muayyan qiyinchiliklarni boshdan kechirmoqda, ammo ozgina mashq qilish va rekursiya sizning dasturlash arsenalingizda tushunarli va juda foydali vosita bo'lib qoladi.
1. Rekursiya mohiyati
Protsedura yoki funktsiya boshqa protsedura yoki funktsiyalarga qo'ng'iroqlarni o'z ichiga olishi mumkin. Shu jumladan protsedura o'zi qo'ng'iroq qilishi mumkin. Bu erda paradoks mavjud emas - kompyuter dasturda uchraydigan buyruqlarni faqat ketma-ket bajaradi va agar protsedura chaqirig'iga duch kelsa, shunchaki ushbu protsedurani bajarishni boshlaydi. Qaysi protsedura buyruq bergani muhim emas.
Rekursiv protseduraga misol:
Rec protsedurasi (a: integer); agar\u003e bo'lsa, boshlang
Agar siz asosiy dasturga qo'ng'iroq qilsangiz nima bo'lishini ko'rib chiqing, masalan, Rec (3) shaklida. Quyida bayonotlarni bajarish ketma-ketligini aks ettiruvchi blok-diagramma keltirilgan.
Shakl: 1. Rekursiv protseduraning blok diagrammasi.
Rec protsedurasi a \u003d 3 parametri bilan chaqiriladi, unda a \u003d 2 parametri bilan Rec chaqiruvi mavjud, oldingi qo'ng'iroq hali tugamagan, shuning uchun siz boshqa protsedura yaratilayotganini va birinchisi tugamaganligini tasavvur qilishingiz mumkin. ishini tugatguncha ishlash. Qo'ng'iroq jarayoni a \u003d 0 parametri bilan tugaydi. Ayni paytda protseduraning 4 ta nusxasi bir vaqtning o'zida bajariladi. Bir vaqtning o'zida bajarilgan protseduralar soni deyiladi rekursiya chuqurligi.
To'rtinchi protsedura (Rec (0)) 0 raqamini chiqaradi va o'z ishini tugatadi. Shundan so'ng, boshqaruv uni chaqirgan protseduraga qaytadi (Rec (1)) va 1 raqami bosiladi va shuning uchun barcha protseduralar tugamaguncha. Dastlabki qo'ng'iroqda to'rtta raqam chop etiladi: 0, 1, 2, 3.
Nima bo'layotganining yana bir vizual tasviri shakl. 2018-04-02 121 2.

Shakl: 2. Rec protsedurasini 3-parametr bilan bajarish Rec protsedurasini 2-parametr bilan bajarish va 3-sonni bosib chiqarishdan iborat. O'z navbatida Rec 2 protsedurasini 2-parametr bilan bajarish Rec protsedurasini 1-parametr bilan bajarish va 2-sonni bosib chiqarishdan iborat. va hokazo.
O'zingizning mashqingiz sifatida Rec (4) ga qo'ng'iroq qilganingizda nimani olganingizni o'ylab ko'ring. Bundan tashqari, quyida tavsiflangan Rec2 (4) protsedurasini chaqirganingizda nima sodir bo'lishini ko'rib chiqing, bu erda bayonotlar teskari yo'naltiriladi.
Rec2 protsedurasi (a: integer); begin Writeln (a); a\u003e 0 bo'lsa, Rec2 (a-1); oxiri;
E'tibor bering, yuqoridagi misollarda rekursiv chaqiruv shartli gap ichida joylashgan. Bu rekursiyaning qachondir tugashi uchun zaruriy shartdir. Shuni ham unutmangki, protsedura o'zini o'zi chaqirilgan parametrdan farqli parametr bilan chaqiradi. Agar protsedurada global o'zgaruvchilar qo'llanilmasa, unda bu rekursiya abadiy davom etmasligi uchun ham zarurdir.
Biroz murakkabroq sxema mumkin: A funktsiyasi B funktsiyasini chaqiradi va bu o'z navbatida A ni chaqiradi kompleks rekursiya... Ma'lum bo'lishicha, birinchi tavsiflangan protsedura hali tasvirlanmaganini chaqirishi kerak. Buning imkoni bo'lishi uchun uni ishlatish kerak
A protsedura (n: tamsayı); (Birinchi protsedura tavsifi (sarlavhasi)) B protsedurasi (n: tamsayı); (Ikkinchi protseduraning kengaytirilgan tavsifi) protsedura A (n: tamsayı); (A protsedurasining to'liq tavsifi) Writeln (n) ni boshlash; B (n-1); oxiri; protsedura B (n: tamsayı); (B protsedurasining to'liq tavsifi) Writeln (n) ni boshlash; agar n
B protsedurasini to'g'ridan-to'g'ri tavsifi uni A protsedurasidan chaqirishga imkon beradi. Ushbu protsedurada A protsedurasini oldinga tavsifi talab qilinmaydi va estetik sabablarga ko'ra qo'shiladi.
Agar oddiy rekursiyani usuroborosga taqqoslash mumkin bo'lsa (3-rasm), unda murakkab rekursiya obrazini bolalarga ma'lum bo'lgan "Bo'rilar qo'rquvdan bir-birini yeb qo'ygan" she'ridan olish mumkin. Ikki bo'ri bir-birini yeyayotganini tasavvur qiling va siz murakkab rekursiyani tushunasiz.
Shakl: 3. Ouroboros - bu o'z dumini yutib yuboradigan ilon. Teodor Pelekanos (1478) tomonidan yozilgan "Sinosius" alkimyoviy traktatidan olingan.

3. Rekursiya yordamida tsiklni simulyatsiya qilish
Agar protsedura o'zini o'zi chaqirsa, demak, bu uning ichida joylashgan ko'rsatmalarning takroriy bajarilishiga olib keladi, bu esa tsikl ishiga o'xshaydi. Ba'zi dasturlash tillarida aylanma konstruktsiyalar umuman mavjud emas, shuning uchun dasturchilar rekursiya yordamida takrorlashni tashkil qilishlari mumkin (masalan, Prolog, bu erda rekursiya dasturlashning asosiy texnikasi hisoblanadi).
Masalan for for loop ishini simulyatsiya qilaylik. Buning uchun biz, masalan, protsedura parametri sifatida amalga oshiriladigan qadam hisoblagich o'zgaruvchiga muhtojmiz.