Ketma-ketliklar, to‘plamlar, daraxtlar, graflarni ifodalash usullari

Ketma-ketliklar, to‘plamlar, daraxtlar, graflarni ifodalash usullari.

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. Agar oddiy rekursiyani bizning oboborosga o'xshatish mumkin bo'lsa (3-rasm), unda murakkab recursion tasvirini “Qo'rquvdan bo'rilar bir-birini eb yuborgan” mashhur bolalar she'ridan yig'ish mumkin. Ikki bo'rining bir-birini eyishini tasavvur qiling, shunda siz murakkab rekursiyani tushunasiz. Anjir. 3. Ouroboros - dumini yutib yuboradigan ilon. Teodor Pelekanosning (1478) "Sinosius" kimyoviy traktatidan olingan rasm. Anjir. 4. Murakkab rekursiya. 3. Rekursion yordamida ko'chadan simulyatsiya qilish Agar protsedura o'zini o'zi chaqirsa, demak, mohiyatan, bu tsiklning ishlashiga o'xshash tarkibiy ko'rsatmalarning takroriy bajarilishiga olib keladi. 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, 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. Misol uchun: LoopImitation3 protsedurasi (i, n: butun son); begin writeln ("Salom N", i); (Birinchi ko'rsatmalar bloki bu erda joylashgan bo'lishi mumkin), agar i Bu erda birinchi navbatda birinchi blokdagi ko'rsatmalar ketma-ket, so'ngra teskari tartibda, ikkinchi blokning ko'rsatmalari bajariladi. LoopImitation3 (1, 10) ni chaqirganda biz quyidagilarga ega bo'lamiz: Salom N 1 … Salom N 10 Salom N 10 … Salom N 1 Buni takrorlashsiz bir xil qilish uchun birdaniga ikki tsikl kerak bo'ladi. Xuddi shu protsedura qismlarining bajarilishi vaqt ichida ajratilganligini ishlatish mumkin. Misol uchun: 3-misol: raqamni ikkilik tizimga tarjima qilish. Ikkilik raqamlarning raqamlarini olish, ma'lum bo'lganingizdek, qolgan son bilan 2-son tizimining bazasida bo'lish orqali sodir bo'ladi. 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. Aynan: BinaryRepresentation protsedurasi (x: butun); var c, x: butun; begin (Birinchi blok. 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. Ya'ni, xotirani saqlab qolishning iloji bo'lmadi. Aksincha, biz ko'plab mahalliy o'zgaruvchilarni saqlash uchun qo'shimcha xotira sarflaymiz. 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: Notation bilan tanishtirib, biz nisbatni olamiz: Formuladan (1) vektorlarni o'zgaruvchan qiymatlar to'plami sifatida talqin qilish mumkin. Keyin ketma-ketlikning kerakli elementini hisoblash ularning qiymatlarini takroriy yangilashdan iborat bo'ladi. Xususan, faktorial uchun: X: \u003d 1; for i: \u003d 2 to n do x: \u003d x * i; writeln (x); Har bir bunday yangilanish (x: \u003d x * i) chaqiriladi iteratsiya, va takrorlashni takrorlash jarayoni iteratsiya. 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. 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. 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. Misol uchun: // x1, x2 - boshlang'ich shartlar (1, 1) // n - Fibonachchi funktsiyasining zarur bo'lgan soni Fib (x1, x2, n: integer): butun son; var x3: butun son; agar n\u003e 1 bo'lsa, keyin x3 ni boshlang: \u003d x2 + x1; x1: \u003d x2; x2: \u003d x3; Fib: \u003d tolasi (x1, x2, n-1); else end Fib: \u003d x2; oxiri; Hali ham iterativ echimlar afzal ko'riladi. Savol shuki, qachon rekursiondan foydalanish kerak? Faqatgina bitta rekursiv chaqiruvni o'z ichiga olgan har qanday rekursiv protseduralar va funktsiyalar osongina iterativ tsikllar bilan almashtiriladi. Oddiy rekursiv bo'lmagan analogga ega bo'lmagan narsani olish uchun siz o'zlarini ikki yoki undan ko'p marta chaqiradigan protseduralar va funktsiyalarga murojaat qilishingiz kerak. Bunday holda, chaqirilgan protseduralar to'plami endi shaklda bo'lgani kabi zanjir hosil qilmaydi. 1 va butun daraxt. Hisoblash jarayoni shu tarzda tashkil etilishi kerak bo'lgan muammolarning keng sinflari mavjud. Faqat ular uchun rekursiya uni hal qilishning eng oson va tabiiy usuli bo'ladi. 5. Daraxtlar O'zlarini bir necha bor chaqiradigan rekursiv funktsiyalarning nazariy asosi daraxtlarni o'rganadigan diskret matematika bo'limi. 5.1. Asosiy ta'riflar. Daraxtlarni tasvirlash usullari Ta'rif: biz cheklangan to'plamni chaqiramiz Tbir yoki bir nechta tugunlardan iborat, masalan: a) Ushbu daraxtning ildizi deb nomlangan bitta maxsus tugun mavjud. b) qolgan tugunlar (ildizni hisobga olmaganda) ikkitadan ajratilgan pastki qatorlarda joylashgan bo'lib, ularning har biri o'z navbatida daraxtdir. Daraxtlar deyiladi pastki daraxtlar bu daraxt. Ushbu ta'rif rekursivdir. Qisqacha aytganda, daraxt - bu ildiz va unga bog'langan kichik daraxtlardan iborat to'plam, ular ham daraxtlardir. Daraxt o'zi orqali aniqlanadi. Ammo, bu ta'rif ma'noga ega, chunki rekursiya cheklangan. Har bir pastki darcha o'z ichiga olgan daraxtga qaraganda kamroq tugunlarga ega. Oxir-oqibat, biz faqat bitta tugunni o'z ichiga olgan pastki daraxtlarga kelamiz va u nima ekanligi aniq bo'ldi. Anjir. 3. Daraxt. Shaklda 3da etti tugunli daraxt ko'rsatilgan. Oddiy daraxtlar pastdan yuqoriga o'ssa-da, ularni chizish aksincha. Diagrammani qo'l bilan chizishda ushbu usul aniqroq qulayroqdir. Ushbu nomuvofiqlik tufayli, ba'zida ular tugunlardan biri ikkinchisidan yuqorida yoki pastda joylashganligini aytganda chalkashlik paydo bo'ladi. Shu sababli, oilaviy daraxtlarni tavsiflashda ishlatiladigan atamalarni, ildiz otalariga yaqinroq tugunlarni va uzoqroq avlodlarni chaqirish qulayroqdir. Grafik jihatdan daraxt boshqa bir necha usullar bilan ifodalanishi mumkin. Ulardan ba'zilari anjir shaklida keltirilgan. 4. Ta'rifga ko'ra, daraxt - bu bir-biri bilan kesishmaydigan yoki to'liq bir-biriga joylashtirilgan ichki o'rnatilgan to'plamlar tizimidir. Bunday to'plamlarni samolyotda mintaqalar sifatida ko'rsatish mumkin (4 a-rasm). Shaklda 4b, ichki to'plamlar samolyotda emas, balki bitta chiziqda cho'zilgan. Anjir. 4b-ni, shuningdek, ichiga o'rnatilgan qavslarni o'z ichiga olgan ba'zi algebraik formulaning diagrammasi sifatida ko'rib chiqish mumkin. Anjir. 4c daraxt tuzilishini ro'yxat sifatida namoyish etishning yana bir mashhur usulini taqdim etadi. Anjir. 4. Daraxt konstruktsiyalarini tasvirlashning boshqa usullari: (a) joylashtirilgan to'plamlar; (b) ichki qavslar; (c) topshiriqlar ro'yxati. Belgilangan ro'yxat kodni formatlash usuliga aniq o'xshashliklarga ega. Darhaqiqat, tizimli dasturlash paradigmasi doirasida yozilgan dasturni inshootlardan tashkil topgan daraxt sifatida ko'rsatish mumkin. Shuningdek, siz topshiriq ro'yxati va kitoblar tarkibidagi jadvalning ko'rinishi o'rtasida taqqoslashingiz mumkin, unda bo'limlar kichik bo'limlarga ega, o'z navbatida ular pastki bo'limlar va boshqalar. Bunday qismlarni raqamlashning an'anaviy usuli (1-bo'lim, 1.1 va 1.2-bo'limlar, 1.1.2-kichik bo'lim va boshqalar) Dewey o'nlik tizimi deb ataladi. Anjir daraxtiga qo'llanilgandek. 3 va 4, ushbu tizim quyidagilarni beradi: 1. A; 1,1 B; 1,2 S; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G; 5.2. Daraxtlarning o'tishi Daraxt konstruktsiyalari bilan bog'liq bo'lgan barcha algoritmlarda bir xil fikr mutlaqo uchraydi, ya'ni g'oya o'tgan yoki daraxt shpallari. Bu daraxtning tugunlariga tashrif buyurishning shunday usuli, unda har bir tugun aniq bir marta o'tadi. Natijada daraxt tugunlari chiziqli joylashadi. Xususan, uchta usul mavjud: siz tugunlarni oldinga, orqaga va tugash tartibiga o'tishingiz mumkin. To'g'ridan-to'g'ri tartibda shpal algoritmi: Ildizga o'ting To'g'ri tartibda chapdan o'ngga barcha pastki qismlardan o'ting. Ushbu algoritm rekursivdir, chunki daraxtni kesib o'tishda pastki kesishgan daraxtlar mavjud va ular, o'z navbatida, xuddi shu algoritm orqali o'tadi. Xususan, sek. 3 va 4-chi to'g'ridan-to'g'ri chorrahalar tugunlarning ketma-ketligini beradi: A, B, C, D, E, F, G. Olingan ketma-ketlik chapdan o'ngga yo'naltirilgan tugunlarning ketma-ket joylashtirilgan ro'yxatiga, Dewey o'nli tizimida joylashtirilgan qavslardan foydalangan holda daraxtni ifodalashda, shuningdek, topshiriqlar ro'yxati shaklida taqdim etilganda yuqoridan pastga qarab. Ushbu algoritmni dasturlash tilida amalga oshirayotganda, ildizga o'tish ba'zi bir amallar yoki funktsiyalarning bajarilishiga va subursiyalarning o'zlarining rekursiv chaqiruvlariga o'tishga to'g'ri keladi. Xususan, ikkilik daraxt uchun (har bir tugundan ikkitadan kam bo'lmagan daraxtlar) tegishli protsedura quyidagicha bo'ladi: // Old buyurtma Traversal - to'g'ridan-to'g'ri buyurtma protsedurasining inglizcha nomi PreorderTraversal ((Argumentlar)); start // DoSomething ((Dalillar)) ildizini o'tkazing; // Chap pastki satrni o'tkazing, agar (chap satr mavjud bo'lsa) va keyin PreorderTransversal ((Argumentlar 2)); // To'g'ri pastki satrni o'tkazing, agar (To'g'ri pastki satr mavjud bo'lsa) va keyin PreorderTransversal ((Argumentlar 3)); oxiri; Ya'ni, dastlab protsedura barcha harakatlarni bajaradi va shundan keyingina barcha rekursiv qo'ng'iroqlar sodir bo'ladi. Algoritmni teskari tartibda aylantiring: Chap pastki qismdan o'ting Ildizga o'ting Chap pastki qismga o'ting. Ildizga o'ting va hokazo eng to'g'ri pastki qator o'tguncha. Ya'ni, barcha pastki daraxtlar chapdan o'ngga o'tkaziladi va ildizga qaytish ushbu o'tish joylari orasida joylashgan. Anjir daraxt uchun. 3 va 4 bu tugunlarning ketma-ketligini beradi: B, A, D, C, E, G, F. Tegishli rekursiv protsedurada harakatlar rekursiv qo'ng'iroqlar orasida joylashgan bo'ladi. Xususan, ikkilik daraxt uchun: // Inorder Traversal - teskari tartib protsedurasining inglizcha nomi InorderTraversal ((Argumentlar)); boshlash // Chap pastki satrni o'tkazing, agar (chap satr mavjud bo'lsa), keyin InorderTraversal ((Argumentlar 2)); // DoSomething ((dalillar)) ildizidan o'tish; // o'ng pastki satrni o'tkazing, agar (o'ng pastki satr mavjud bo'lsa), keyin InorderTraversal ((Argumentlar 3)); oxiri; Tortishish algoritmi Chapdan o'ngga barcha pastki qismlardan o'ting, Ildizga o'ting. Anjir daraxt uchun. 3 va 4 bu tugunlarning ketma-ketligini beradi: B, D, E, G, F, C, A. Tegishli rekursiv protsedurada harakatlar rekursiv chaqiruvlardan keyin joylashadi. Xususan, ikkilik daraxt uchun: // Postorder Traversal - PostorderTraversal tugatish tartibining inglizcha nomi ((Argumentlar)); boshlash // Chap pastki satrni o'tkazing agar (Agar chap pastki satr mavjud bo'lsa) va undan keyin PostorderTraversal ((Argumentlar 2)); // agar o'ng pastki satr bo'lsa, keyin PostorderTraversal ((3-dalillar)) o'ng pastki satrni o'tkazing. // DoSomething ((dalillar)) ildizidan o'tish; oxiri; 5.3. Kompyuter xotirasida daraxtning tasviri Agar ba'zi ma'lumotlar daraxtning tugunlarida joylashgan bo'lsa, unda siz uni saqlash uchun tegishli dinamik ma'lumotlar tuzilishini ishlatishingiz mumkin. Paskalda, bu bir xil turdagi pastki qismlarga ko'rsatgichlarni o'z ichiga olgan o'zgaruvchan yozuv yordamida amalga oshiriladi. Masalan, har bir tugun ichida butun son bo'lgan ikkitomonlama daraxtni quyida tavsiflangan PTree turidagi o'zgaruvchidan foydalanib saqlash mumkin: Turi PTree \u003d ^ TTree; TTree \u003d rekord Inf: butun son; LeftSubTree, RightSubTree: PTree; oxiri; Har bir tugun PTree tipida. Bu ko'rsatgich, ya'ni har bir tugun buning uchun yangi protsedurani chaqirib yaratilishi kerak. Agar tugatish tugun bo'lsa, uning LeftSubTree va RightSubTree maydonlariga qiymat beriladi nol. Aks holda LeftSubTree va RightSubTree tugunlari ham Yangi protsedura yordamida yaratiladi. Sxematik ravishda, bunday yozuvlar sek. beshta. Anjir. 5. TTree tipidagi yozuvning sxematik tasviri. Yozuv uchta maydonga ega: Inf - raqam, LeftSubTree va RightSubTree - bir xil turdagi TTree yozuvlari uchun ko'rsatkichlar. Bunday yozuvlardan tashkil topgan daraxtning namunasi 6-rasmda keltirilgan. Anjir. 6. TTree yozuvlaridan iborat daraxt. Har bir kirishda ikkala raqam va ikkita ko'rsatkich mavjud nolyoki bir xil turdagi boshqa yozuvlarning manzillari. Agar siz ilgari xuddi shu turdagi yozuvlarga havolalarni o'z ichiga olgan yozuvlardan iborat tuzilmalar bilan ishlamagan bo'lsangiz, sizga ushbu material bilan tanishishingizni maslahat beramiz. 6. Rekursiv algoritmlarga misollar 6.1. Daraxt chizish Shaklda ko'rsatilgan daraxtni chizish algoritmini ko'rib chiqing. 6. Agar biz har bir satrni tugun deb hisoblasak, unda bu rasm oldingi bo'limda keltirilgan daraxtning ta'rifini to'liq qondiradi. Anjir. 6. Daraxt. Rekursiv protsedura, shubhasiz, bitta chiziqni (birinchi filial oldidagi magistral) tortishi kerak va keyin ikkita pastki chiziqni chizish uchun o'zini chaqirishi kerak. Pastki daraxtlar ularni o'z ichiga olgan daraxtdan boshlang'ich nuqtaning koordinatalari, burilish burchagi, magistral uzunligi va ularning tarkibidagi novdalar soni bilan farq qiladi (bittadan kamroq). Bu barcha farqlar rekursiv protsedura parametrlari bo'yicha amalga oshirilishi kerak. Delphi-da yozilgan bunday protseduraning misoli quyida keltirilgan. Tartib daraxti (Tuval: TCanvas; // x, y: kengaytirilgan daraxt chizilgan tuval; // Ildizning koordinatalari: kengaytirilgan; // Daraxt o'sadigan burchak TrunkLength: kengaytirilgan; // Trunk uzunligi n: butun son / / Filiallar soni (hanuzgacha qancha // rekursiv chaqiriqlar mavjud)); var x2, y2: kengaytirilgan; // magistralning oxiri (filial nuqtasi) x2 bilan boshlanadi: \u003d x + TrunkLength * cos (Burchak); y2: \u003d y - TrunkLength * sin (burchak); Kanvas.MoveTo (yumaloq (x), dumaloq (y)); Canvas.LineTo (yumaloq (x2), dumaloq (y2)); agar n\u003e 1 bo'lsa, unda daraxtni boshlang (Tuval, x2, y2, Burchak + Pi / 4, 0.55 * TrunkLength, n-1); Daraxt (tuval, x2, y2, burchak-Pi / 4, 0,55 * TrunkLength, n-1); oxiri; oxiri; Anjir olish uchun. 6, ushbu protsedura quyidagi parametrlar bilan chaqirildi: Daraxt (Image1.Canvas, 175, 325, Pi / 2, 120, 15); E'tibor bering, rasm chizish rekursiv chaqiruvlardan oldin amalga oshiriladi, ya'ni daraxt to'g'ridan-to'g'ri tartibda chiziladi. 6.2. Xanoy minoralari Afsonaga ko'ra, Benaras shahridagi Buyuk ma'badda, dunyoning o'rtasida joylashgan soborning ostida bronza disk o'rnatilgan bo'lib, unda 3 ta olmos tayoq, bitta tirsak balandligi va asalari qalinligi o'rnatilgan. Bir paytlar, eng boshida, bu monastirning monaxlari xudo Brahma oldida aybdor edilar. G'azablangan Brahma uchta baland novda qurdi va ularning har biriga 64 tadan toza oltin disk qo'ydi, shunda har bir kichik disk kattaroq diskda yotadi. Xudo yaratgan paytida Brahma qo'ygan tayoqdan 64 ta disklarning barchasi boshqa bir tayoqqa ko'chirilishi bilan, minora va ma'bad changga aylanadi va dunyo momaqaldiroq ostida o'ladi. Jarayon kattaroq disk hech qachon kichikroq bo'lmasligini talab qiladi. Rohiblar qiynalmoqda, qanday ketma-ketlikni o'zgartirish kerak? Ushbu ketma-ketlikni hisoblash uchun ularni dasturiy ta'minot bilan ta'minlash talab qilinadi. Bramadan qat'i nazar, bu jumboq 19-asrning oxirida frantsuz matematiki Eduard Luqo tomonidan taklif qilingan. Sotilgan versiyada odatda 7-8 disk ishlatilgan (7-rasm). Anjir. 7. "Xanoy minorasi" jumboq. Masalan, buning echimi bor deylik n-1 haydovchi. Keyin siljitish uchun n disklarga quyidagicha davom eting: 1) Biz siljiymiz n-1 haydovchi. 2) siljiymiz nQolgan bo'sh pin ustidagi disk. 3) Biz qoziqni boshqa tomondan siljitamiz n(1) paragrafda olingan disk nth disk. Ish uchun beri n \u003d 1, siljish algoritmi aniq, keyin induktsiya yordamida (1) - (3) amallardan foydalanib, o'zboshimchalik bilan ko'plab disklarni siljitishimiz mumkin. Berilgan miqdordagi disklar uchun o'tkazmalarning butun ketma-ketligini bosib chiqaradigan rekursiv protsedurani yarating. Bunday protsedura, uning har bir chaqirig'ida bir smenada (algoritmning 2-bandidan) ma'lumotni chop etish kerak. (1) va (3) bandlardan ikkinchisiga o'tish uchun protsedura disklarning soni bittaga kamaygan holda chaqiriladi. // n - disklar soni // a, b, c - pin raqamlari. O'tkazish pin a dan amalga oshiriladi, // yordamchi pin bilan b pin bilan. protsedura Xanoy (n, a, b, c: butun son); agar n\u003e 1 bo'lsa, keyin Xanoydan boshlang (n-1, a, c, b); writeln (a, "-\u003e", b); Xanoy (n-1, c, b, a); end else writeln (a, "-\u003e", b); oxiri; E'tibor bering, bu holda rekursiv deb ataladigan protseduralar to'plami teskari tartibda o'tadigan daraxtni hosil qiladi. 6.3. Arifmetik ifodalarni tahlil qilish Sintaktik vazifa - arifmetik ifodani va unga kiritilgan o'zgaruvchilarning ma'lum qiymatlarini o'z ichiga olgan mavjud chiziqdan ifoda qiymatini hisoblash. Arifmetik ifodalarni hisoblash jarayoni ikkilik daraxt sifatida ifodalanishi mumkin. Darhaqiqat, har bir arifmetik operatorlar (+, -, *, /) ikkita operandni talab qiladi, ular ham arifmetik ifodalar bo'ladi va shunga mos ravishda substratlar sifatida ko'rib chiqilishi mumkin. Anjir. 8 iboraga mos keladigan daraxtning namunasini ko'rsatadi: Anjir. 8. Arifmetik ifoda (6) ga mos keladigan sintaksis daraxti. Bunday daraxtda oxirgi tugunlar har doim o'zgaruvchan bo'ladi (bu erda) x) yoki raqamli konstantalar va barcha ichki tugunlar arifmetik operatorlarni o'z ichiga oladi. Operatorni bajarish uchun avval uning operandlarini hisoblash kerak. Shunday qilib, rasmdagi daraxt oxir-oqibat kesib o'tilishi kerak. Tugunlarning tegishli ketma-ketligi chaqirdi teskari polishing notasi arifmetik ifoda. Sintaksis daraxtini yaratishda quyidagi xususiyatga e'tibor berish kerak. Agar mavjud bo'lsa, masalan, ifoda biz chap va o'ng tomonga qo'shish va ayirish amallarini qo'shamiz, to'g'ri sintaksis daraxti plyus o'rniga minusni o'z ichiga oladi (9 a-rasm). Aslida bu daraxt iboraga to'g'ri keladi Agar biz ifoda (8) ni, aksincha, o'ngdan chapga tahlil qilsak, daraxtning tuzilishini osonlashtirish mumkin. Bunday holda, anjir bilan daraxt. 9b, 8a daraxtiga ekvivalent, lekin belgilarini almashtirishni talab etmaydi. Xuddi shunday, o'ngdan chapga, siz ko'payish va bo'lish operatorlarini o'z ichiga olgan iboralarni tahlil qilishingiz kerak. Anjir. 9. Ifodalash uchun sintaksis daraxtlari a – b + v chapdan o'ngga (a) va o'ngdan chapga (b) o'qiyotganda. Ushbu yondashuv rekursiyani butunlay yo'q qilmaydi. Ammo, bu sizning rekursiv protseduraga faqat bitta qo'ng'iroq bilan cheklanishingizga imkon beradi, agar sabab maksimal ishlash haqida g'amxo'rlik qilish uchun etarli bo'lsa. 7.3. Daraxt tugunini uning soniga qarab aniqlash Ushbu yondashuvning g'oyasi, rekursiv qo'ng'iroqlarni oddiy pastadir bilan almashtirishdir, bu esa takrorlanadigan protseduralar natijasida hosil bo'lgan daraxtda tugunlar mavjud bo'lganda, ularni ko'p marta bajaradi. Har bir qadamda aniq nima qilinishini qadam raqami bilan aniqlash kerak. Bosqich raqamini va kerakli harakatlarni taqqoslash arzimas ish emas va har bir holatda uni alohida hal qilish kerak bo'ladi. Masalan, ruxsat bering k tomonidan joylashtirilgan ko'chadan n har birida qadamlar: I1: \u003d 0 uchun n-1 uchun i2: \u003d 0 dan n-1 uchun i3: \u003d 0 dan n-1 do ... Agar a k oldindan noma'lum, yuqorida ko'rsatilgandek, ularni aniq yozish mumkin emas. 6.5-bo'limda ko'rsatilgan texnikadan foydalanib, siz rekursiv protsedura yordamida kerakli miqdordagi joylashtirilgan ko'chadan olishingiz mumkin: NestedCycles protsedurasi (Indekslar: butun son; n, k, chuqurlik: butun son); var i: butun son; chuqurlik bo'lsa, boshlang Rekursiyadan xalos bo'lish va hamma narsani bitta tsiklga qisqartirish uchun, agar siz raqamlar tizimidagi qadamlarni bazasi bilan sanasangiz, biz shuni ta'kidlaymiz. n, keyin har bir bosqichda i1, i2, i3, ... raqamlaridan yoki indekslar qatoridan mos keladigan raqamlardan iborat raqam mavjud. Ya'ni raqamlar tsikl hisoblagichlarining qiymatlariga mos keladi. Oddiy kasr yozuvida qadam raqami: Jami qadamlar bo'ladi n k. O'nli kasr sonlar tizimida ularning raqamlari orqali borish va ularning har birini baza bilan tizimga tarjima qilish n, biz indekslarning qiymatlarini olamiz: M: \u003d dumaloq (IntPower (n, k)); uchun i: \u003d 0 dan M-1 gacha, boshlanadigan raqam: \u003d i; p: \u003d 0 to k-1 do uchun boshlang'ich ko'rsatkichlar: \u003d Mod n soni; Raqam: \u003d raqam div n; oxiri; DoSomething (indekslar); oxiri; Yana bir bor ta'kidlaymizki, usul universal emas va har bir vazifa uchun siz boshqacha kashf qilishingiz kerak bo'ladi. test savollari 1. Quyidagi rekursiv protseduralar va funktsiyalar nimani bajarishini aniqlang. a) Rec (4) ni chaqirganda, quyida keltirilgan protsedura nimani bosib chiqaradi? Rec (a: butun son) protsedurasi; writeln (a) boshlash; agar a\u003e 0 bo'lsa, Rec (a-1); writeln (a); oxiri; b) Nod funktsiyasining qiymati (78, 26) nimani anglatadi? Nod funktsiyasi (a, b: butun son): butun; agar a\u003e b keyin Nod: \u003d Nod (a - b, b), agar b\u003e a keyin Nod: \u003d Nod (a, b - a) boshqa Nod: \u003d a; oxiri; c) A (1) ni chaqirganda quyidagi protseduralar yordamida nimalar chop etiladi? Protsedura A (n: butun son); protsedura B (n: butun son); protsedura A (n: butun son); writeln (n) boshlamoq; B (n-1); oxiri; protsedura B (n: butun son); writeln (n) boshlamoq; agar n (d) BT (0, 1, 3) ni chaqirganda quyida keltirilgan protsedura nimani bosadi? BT protsedurasi (x: real; D, MaxD: butun son); agar D \u003d MaxD bo'lsa, bas, Bell (x - 1, D + 1, MaxD) writeln (x) boshlanadi; BT (x + 1, D + 1, MaxD); oxiri; oxiri; 2. Ouroboros - kengaytirilgan shaklda o'z dumini yutib yuboradigan ilonning uzunligi (14-rasm) Lbosh atrofida diametri Dqorin devorining qalinligi d. O'ziga qancha dumini tushirishini aniqlang va dumidan keyin qancha qatlam qo'yiladi? Anjir. 14. Kengaytirilgan bizningoborolar. 3. Anjir daraxt uchun. 10a tugmachalarga to'g'ridan-to'g'ri, orqaga va oxiriga borishni ketma-ketlik bilan tugatish tartibini bildiradi. 4. Yopiq qavslar yordamida aniqlangan daraxtni grafik ravishda tasvirlang: (A (B (C, D), E), F, G). 5. Quyidagi arifmetik ifoda uchun grafik sintaksis daraxtini chizing: Ushbu iborani teskari Polsha yozuvida yozing. 6. Quyidagi grafika uchun (15-rasm) qo'shilish matritsasi va egilish matritsasini yozing. Vazifalar 1. Faktorialni etarlicha ko'p marta (million yoki undan ko'p) hisoblab, rekursiv va iterativ algoritmlarning samaradorligini taqqoslang. Qo'rg'oshin vaqti necha marta farq qiladi va bu nisbat qanday omil koeffitsienti hisoblangan songa bog'liq bo'ladi? 2. Qavslar qatorga to'g'ri qo'yilganligini tekshiradigan rekursiv funktsiyani yozing. To'g'ri joylashtirish bilan quyidagi shartlar bajariladi: (a) ochilish va yopilish qavslari soni tengdir. (b) har qanday ochilish jufti ichida - mos keladigan yopiladigan qavs, qavslar to'g'ri joylashtirilgan. Noto'g'ri joylashtirish misollari :) (, ()) (, ()) ((), va hokazo. 3. Chiziq qavslar va kvadrat qavslardan iborat bo'lishi mumkin. Har bir ochiladigan qavs bir xil turga (yumaloq - yumaloq, kvadrat - kvadrat) mos keladi. Bu holda Qavslar to'g'ri ekanligini tekshiradigan rekursiv funktsiyani yozing. Noto'g'ri tartibga solishga misol: ([)]. 4. 6 uzunlikdagi oddiy qavslar soni 5 ga teng: () () (), (()) (), () (()), ((())), (() ()). 2 uzunlikdagi barcha oddiy qavsli tuzilmalarni yaratish uchun rekursiv dastur yozing n. Eslatma: Minimal uzunlikdagi qavsning to'g'ri tuzilishini "()". Qisqa tuzilmalardan uzunroq tuzilmalarni ikki yo'l bilan olish mumkin: (a) agar kichkina struktura qavs ichida olinsa, (b) agar ikkita kichik tuzilish ketma-ket yozilsa. 5. 1 dan N gacha bo'lgan butun sonlar uchun barcha mumkin bo'lgan ma'lumotlarni kiritadigan protsedurani yarating. 6. Tarkibning barcha pastki qismlarini chop etadigan protsedurani yarating (1, 2, ..., N). 7. N natural sonning barcha mumkin bo'lgan tasvirlarini boshqa natural sonlar yig'indisi kabi chiqaradigan protsedura yarating. 8. Quyidagi algoritmga binoan massiv elementlarining yig'indisini hisoblaydigan funktsiyani yarating: massiv yarmiga bo'lindi, har bir yarmidagi elementlarning yig'indisi hisoblab chiqiladi va qo'shiladi. Massivning yarmidagi elementlarning yig'indisi xuddi shu algoritmga ko'ra, ya'ni yana yarmiga bo'lish orqali hisoblanadi. Tarkibning hosil bo'lgan qismlarida bir vaqtning o'zida bitta element mavjud bo'lguncha bo'linishlar sodir bo'ladi va shunga mos ravishda summani hisoblash arzimas bo'lib qoladi. Izoh: Ushbu algoritm alternativadir. Haqiqiy qiymatga ega bo'lgan massivlar bo'lsa, odatda kichikroq yaxlitlash xatolarini olish imkonini beradi. 10. Kox egri chizig'ini tortadigan protsedurani yarating (12-rasm). 11. rasmni qayta tinglang. 16. Rasmda har bir keyingi iteratsiyada aylanalar 2,5 baravar kichikroq (bu koeffitsientni parametr qilish mumkin). Adabiyot 1. D. Knut. Kompyuter dasturlash san'ati. 1. (2.3. "Daraxtlar" bo'limi). 2. N. Wirth. Algoritmlar va ma'lumotlar tuzilmalari.