Rekursiya va rekursiv algoritmlar. Rekursiya va rekursiv algoritmlar Rekursiv algoritm protsedurasi berilgan f n butun
Talabalarni informatika va AKT bo'yicha yagona davlat imtihoniga tayyorlash uchun "Rekursiv algoritmlar" mavzusida taqdimot yaratildi. Maqolada rekursiya ta'rifi ko'rib chiqiladi va rekursiv aniqlangan grafik ob'ektlarga misollar keltirilgan. Taqdimotda informatika bo'yicha Yagona davlat imtihoni - 2015 demo versiyasi loyihasidan 11-sonli vazifani hal qilish usullari mavjud. Birinchi usul chaqiruv daraxtini qurishni o'z ichiga oladi, ikkinchi usul muammoni almashtirish usuli yordamida hal qiladi. Ikkala usuldan foydalangan holda muammolarni hal qilishning 4 ta misoli ko'rib chiqiladi. Quyidagi taqdimotda Konstantin Polyakovning veb-saytidan javoblar bilan mashg'ulotlar uchun 25 ta mashq mavjud.
Yuklab oling:
Ko‘rib chiqish:
Taqdimotni oldindan ko'rishdan foydalanish uchun o'zingiz uchun hisob yarating ( hisob) Google va tizimga kiring: https://accounts.google.com
Slayd sarlavhalari:
Vazifa No 11 Yagona davlat imtihoni (asosiy daraja, vaqt - 5 daqiqa) Rekursiv algoritmlar. Muallif – “71-sonli umumta’lim maktabi” shahar ta’lim muassasasi informatika fani o‘qituvchisi Korotun O.V.
Siz bilishingiz kerak bo'lgan narsa: Rekursiya - bu ob'ekt yoki jarayonni ushbu ob'ekt yoki jarayonning o'zida belgilash, tavsiflash, tasvirlash, ya'ni ob'ekt o'zining bir qismi bo'lgan vaziyat. Gerb Rossiya Federatsiyasi rekursiv aniqlangan grafik ob'ektdir: unda tasvirlangan ikki boshli burgutning o'ng panjasida gerbning qisqartirilgan nusxasi bilan toj kiygan tayoq qisilgan. Ushbu gerbda burgutning o'ng panjasida ham tayoq borligi sababli, cheksiz rekursiya olinadi. Rossiyaning rekursiv gerbi
Dasturlashda rekursiya funksiyaning o‘zidan, to‘g‘ridan-to‘g‘ri yoki boshqa funksiyalar orqali chaqirilishidir, masalan, A funksiyasi B funktsiyasini chaqiradi va B funksiyasi A funksiyasini chaqiradi. Funksiya yoki protseduraga o‘rnatilgan qo‘ng‘iroqlar soni chuqurligi deyiladi. rekursiya. Rekursiyaga misol: Agar kiyimingizda yog 'dog'i bo'lsa, tashvishlanmang. Yog 'dog'lari benzin bilan olib tashlanadi. Ishqorlar esa, moy bilan tozalanadi.
Berilgan misol: Rekursiv algoritm berilgan: procedure F(n: integer); boshlash writeln(n); agar n
Berilgan misol: Rekursiv algoritm berilgan: procedure F(n: integer); writeln(n) boshlash ; agar n
Berilgan misol: Rekursiv algoritm berilgan: procedure F(n: integer); boshlash writeln(n); agar n Slayd 9
Berilgan misol: Rekursiv algoritm berilgan: procedure F(n: integer); boshlash writeln(n); agar n Slayd 10
Berilgan misol: Rekursiv algoritm berilgan: procedure F(n: integer); boshlash writeln(n); agar n Slayd 11
15 2-misol: Rekursiv algoritm berilgan: F(n: integer) protsedurasi; boshlash writeln(n); agar n
2-misol: Rekursiv algoritm berilgan: protsedura F(n: integer); boshlash writeln(n); agar n Slayd 13
3-misol: Rekursiv algoritm berilgan: protsedura F(n: integer); begin writeln("*"); agar n > 0 bo'lsa, F(n-2) boshlanadi; F(n div 2) end end ; F(7) ni chaqirganda ekranda nechta yulduzcha bosiladi? 7 5 3 2 3 1 1 1 1 Ushbu misolda ekranda qiymatlar oʻrniga * -2 div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0 belgisi koʻrsatiladi. parametr n.
3-misol: Rekursiv algoritm berilgan: protsedura F(n: integer); begin writeln("*"); agar n > 0 bo'lsa, F(n-2) boshlanadi; F(n div 2) end end ; F(7) ni chaqirganda ekranda nechta yulduzcha bosiladi? * "Yulduzlar" sonini sanab, biz 21 ni olamiz Ushbu misolda ekranda n parametrining qiymatlari emas, balki * * * * * * * * * * * * belgisi ko'rsatiladi. * * * * * * * * *
3-misol: Rekursiv algoritm berilgan: protsedura F(n: integer); begin writeln("*"); agar n > 0 bo'lsa, F(n-2) boshlanadi; F(n div 2) end end ; F(7) ni chaqirganda ekranda nechta yulduzcha bosiladi? Keling, muammoni daraxtsiz hal qilaylik. F(n) ni chaqirganda chop etiladigan “yulduzlar” soni S(n) bo‘lsin. Keyin 1+S(n-2)+ S(n div 2), n>0 1 , n S(7) ni bilishimiz kerak. S(7)= 1 +S(5)+ S(3) S(5)= 1 +S(3)+S(2) S(3)= 1 +S(1)+S(1) S( 2)=1+S(0)+S(1)=1+1+S(1)=2+S(1) S(1)= 1+ S(-1)+S(0)=1+ 1+1=3 Teskari: S(2)=2+3=5 S(3)=1+3+3=7 S(5)=1+7+5=13 S(7)=1+ 13+ 7= 21 S(n)=
4-misol: protsedura F(n: butun son); boshlang, agar n Slayd 18
4-misol: protsedura F(n: butun son); boshlang agar n Slayd 19
4-misol: protsedura F(n: butun son); boshlang, agar n
4-misol: protsedura F(n: butun son); boshlang, agar n
Trening vazifalari
1-masala: Rekursiv algoritm berilgan: protsedura F(n: butun son); begin writeln("*"); agar n > 0 bo'lsa, F(n-2) boshlanadi; F(n div 2); F(n div 2); oxirigacha; F(5) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 34
2-masala: Rekursiv algoritm berilgan: protsedura F(n: integer); begin writeln("*"); agar n > 0 bo'lsa, F(n-2) boshlanadi; F(n-2); F(n div 2); oxirigacha; F(6) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 58
3-masala: Rekursiv algoritm berilgan: protsedura F(n: butun son); begin writeln("*"); agar n > 0 bo'lsa, F(n-3) boshlanadi; F(n div 2); oxirigacha; F(7) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 15
4-masala: Berilgan rekursiv algoritm: F(n: integer) protsedurasi; begin writeln("*"); agar n > 0 bo'lsa, F(n-3) boshlanadi; F(n-2); F(n div 2); oxirigacha; F(7) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 55
5-masala: Rekursiv algoritm berilgan: protsedura F(n: integer); begin writeln("*"); agar n > 0 bo'lsa, F(n-3) boshlanadi; F(n-2); F(n div 2); F(n div 2); oxirigacha; F(6) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 97
6-masala: Rekursiv algoritm berilgan: protsedura F(n: butun son); begin writeln("*"); agar n > 0 bo'lsa, writeln("*"); F(n-2); F(n div 2); oxirigacha; F(7) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 31
7-masala: Rekursiv algoritm berilgan: protsedura F(n: butun son); begin writeln("*"); agar n > 0 bo'lsa, writeln("*"); F(n-2); F(n div 2); F(n div 2); oxirigacha; F(7) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 81
8-masala: Rekursiv algoritm berilgan: protsedura F(n: butun son); begin writeln("*"); agar n > 0 bo'lsa, writeln("*"); F(n-2); F(n-2); F(n div 2); oxirigacha; F(6) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 77
9-masala: Rekursiv algoritm berilgan: protsedura F(n: butun son); agar n > 0 bo'lsa, F(n-2) boshlanadi; F(n-1); F(n-1); oxiri; writeln("*"); oxiri ; F(5) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 148
10-masala: Rekursiv algoritm berilgan: protsedura F(n: butun son); agar n > 0 bo'lsa, boshlanadi writeln("*"); F(n-2); F(n-1); F(n-1); oxiri; writeln("*"); oxiri; F(5) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 197
11-masala: Rekursiv algoritm berilgan: protsedura F(n: butun son); agar n > 1 bo'lsa, keyin F(n-2) boshlanadi; F(n-1); F(n div 2); oxiri; writeln("*"); oxiri ; F(7) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 88
12-masala: Rekursiv algoritm berilgan: protsedura F(n: butun son); agar n > 2 bo'lsa, boshlanadi writeln("*"); F(n-2); F(n-1); F(n div 2); oxiri ; writeln("*"); oxiri; F(6) ni chaqirganda ekranda nechta yulduzcha bosiladi? Javob: 33
13-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
14-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
15-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
16-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
17-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
18-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
19-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
20-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
21-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
22-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
23-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
24-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
25-masala: Rekursiv algoritm berilgan: F protsedurasi (n: butun son); boshlash writeln(n); agar n
Rekursiya - bu pastki dastur o'zini chaqirganda. Bunday algoritmik dizayn bilan birinchi marta duch kelganda, ko'pchilik ma'lum qiyinchiliklarni boshdan kechiradi, biroq ozgina amaliyot bilan rekursiya sizning dasturlash arsenalingizda tushunarli va juda foydali vositaga aylanadi.
1. Rekursiyaning mohiyati
Protsedura yoki funksiya boshqa protsedura yoki funksiyalarga qo'ng'iroqlarni o'z ichiga olishi mumkin. Jarayon o'zini ham 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 boshlanadi
Asosiy dasturda, masalan, Rec(3) ko'rinishdagi chaqiruv amalga oshirilsa, nima bo'lishini ko'rib chiqamiz. Quyida bayonotlarning bajarilishi ketma-ketligini ko'rsatadigan oqim diagrammasi keltirilgan.
Guruch. 1. Rekursiv protseduraning blok diagrammasi.
Protsedura Rec 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 yaratilganligini va birinchisi o‘z ishini tugatmaguncha tasavvur qilishingiz mumkin. tugatadi. Chaqiruv jarayoni parametr a = 0 bo'lganda tugaydi. Bu nuqtada 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 chop etadi va o'z ishini tugatadi. Shundan so'ng, boshqaruv uni chaqirgan protseduraga qaytadi (Rec(1)) va barcha protseduralar tugamaguncha 1 raqami chop etiladi. Asl qo'ng'iroq to'rtta raqamni chop etadi: 0, 1, 2, 3.
Nima sodir bo'layotganining yana bir vizual tasviri rasmda ko'rsatilgan. 2.
Guruch. 2. 3-parametr bilan Rec protsedurasini bajarish 2-parametr bilan Rec protsedurasini bajarish va 3-raqamni chop etishdan iborat. .
Mustaqil mashq sifatida Rec(4) ga qo'ng'iroq qilganingizda nima sodir bo'lishini ko'rib chiqing. Agar siz operatorlar teskari bo'lgan holda quyidagi Rec2(4) protsedurasini chaqirsangiz nima bo'lishini ham ko'rib chiqing.
Protsedura Rec2(a: butun son); yozishni boshlash (a);
agar a>0 bo'lsa, Rec2(a-1); oxiri; E'tibor bering, ushbu misollarda rekursiv qo'ng'iroq shartli bayonot ichida joylashgan. Bu zarur shart
rekursiya hech qachon tugamasligi uchun. Shuni ham yodda tutingki, protsedura o'zini chaqirilganidan boshqa parametr bilan chaqiradi. Agar protsedura global o'zgaruvchilardan foydalanmasa, bu rekursiya cheksiz davom etmasligi uchun ham kerak. 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 tasvirlangan protsedura hali tasvirlanmagan protsedurani 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); (A protsedurasining to'liq tavsifi) begin writeln(n);
B(n-1); oxiri; protsedura B(n: butun son); (B protsedurasining to'liq tavsifi) begin writeln(n);
agar n
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.
3. Rekursiya yordamida siklni simulyatsiya qilish
Agar protsedura o'zini chaqirsa, u o'z ichiga olgan ko'rsatmalarni tsiklga o'xshab yana bajarilishiga olib keladi. 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 tsiklining ishlashini simulyatsiya qilaylik. Buning uchun bizga, masalan, protsedura parametri sifatida amalga oshirilishi mumkin bo'lgan qadam hisoblagichi o'zgaruvchisi kerak.
1-misol.
Protsedura LoopImitation(i, n: integer); (Birinchi parametr qadam hisoblagichi, ikkinchi parametr qadamlarning umumiy soni) begin writeln("Salom N ", i); //Mana, agar i bo'lsa, takrorlanadigan ko'rsatmalar mavjud LoopImitation(1, 10) shaklidagi chaqiruv natijasi hisoblagichni 1 dan 10 ga o'zgartirib, ko'rsatmalarning o'n marta bajarilishi bo'ladi. Bu holda quyidagilar chop etiladi: Salom N 1 Umuman olganda, protsedura parametrlari hisoblagich qiymatlarini o'zgartirish chegaralari ekanligini ko'rish qiyin emas. Quyidagi misolda bo'lgani kabi takrorlanadigan qo'ng'iroq va ko'rsatmalarni almashtirishingiz mumkin. 2-misol.
Protsedura LoopImitation2(i, n: integer); agar men Bunday holda, rekursiv protsedura chaqiruvi ko'rsatmalar bajarilishini boshlashdan oldin sodir bo'ladi. Protseduraning yangi nusxasi, shuningdek, birinchi navbatda, hisoblagichning maksimal qiymatiga etgunimizcha, boshqa misolni chaqiradi va hokazo. Shundan keyingina oxirgi chaqirilgan protseduralar o'z ko'rsatmalarini bajaradi, keyin ikkinchidan oxirgisi o'z ko'rsatmalarini bajaradi va hokazo. LoopImitation2(1, 10) ni chaqirish natijasi salomlashishni teskari tartibda chop etish bo'ladi: Salom N 10 Agar biz rekursiv deb ataladigan protseduralar zanjirini tasavvur qilsak, u holda 1-misolda biz undan oldingi protseduralardan keyingilariga o'tamiz. 2-misolda, aksincha, keyinroqdan oldinga. Nihoyat, rekursiv qo'ng'iroqni ikkita ko'rsatmalar bloki orasiga qo'yish mumkin. Masalan: Protsedura LoopImitation3(i, n: integer); begin writeln("Salom N", i); (Ko'rsatmalarning birinchi bloki bu erda joylashgan bo'lishi mumkin) agar i Bu erda birinchi blokdagi ko'rsatmalar birinchi navbatda ketma-ket bajariladi, keyin ikkinchi blokdagi ko'rsatmalar teskari tartibda bajariladi. LoopImitation3(1, 10) ga qo'ng'iroq qilganda biz quyidagilarni olamiz: Salom N 1 Xuddi shu ishni rekursiyasiz bajarish uchun ikkita tsikl kerak bo'ladi. Xuddi shu protsedura qismlarini bajarish vaqt o'tishi bilan oraliqda bo'lishidan foydalanishingiz mumkin. Masalan: 3-misol: Sonni ikkilik sistemaga aylantirish.
Ikkilik sonning raqamlarini olish, ma'lumki, sanoq tizimining asosiga qoldiqga bo'lish yo'li bilan sodir bo'ladi 2. Agar raqam mavjud bo'lsa, unda uning ikkilik ko'rinishidagi oxirgi raqami teng bo'ladi. 2 ga bo'linishning butun qismini olish: biz bir xil ikkilik ko'rinishga ega bo'lgan, ammo oxirgi raqamsiz raqamni olamiz. Shunday qilib, keyingi bo'linish maydoni 0 ga teng butun sonni olguncha yuqoridagi ikkita amalni takrorlash kifoya qiladi. Rekursiyasiz u quyidagicha ko'rinadi: x>0 esa c:=x mod 2 boshlanadi; x:=x div 2; yozish (c); oxiri; Bu erda muammo shundaki, ikkilik vakillikning raqamlari teskari tartibda hisoblanadi (oxirgi birinchi). Raqamni oddiy shaklda chop etish uchun siz massiv elementlaridagi barcha raqamlarni eslab qolishingiz va ularni alohida tsiklda chop etishingiz kerak bo'ladi. Rekursiyadan foydalanib, massiv va ikkinchi tsiklsiz to'g'ri tartibda chiqishga erishish qiyin emas. Ya'ni: x:= x div 2; (Rekursiv chaqiruv) agar x>0 bo'lsa, BinaryRepresation(x); (Ikkinchi blok. Teskari tartibda bajariladi) yozish(c); oxiri; Umuman olganda, biz hech qanday yutuq olmadik. Ikkilik tasvirning raqamlari mahalliy o'zgaruvchilarda saqlanadi, ular rekursiv protseduraning har bir ishlayotgan misoli uchun farq qiladi. Ya'ni, xotirani saqlashning iloji bo'lmadi. Aksincha, biz ko'plab mahalliy o'zgaruvchilarni saqlash uchun qo'shimcha xotirani behuda sarflaymiz. Biroq, bu yechim menga chiroyli ko'rinadi. 4. Qaytalanish munosabatlari. Rekursiya va iteratsiya Vektorlar ketma-ketligi, agar boshlang'ich vektor va keyingi vektorning oldingisiga funktsional bog'liqligi berilgan bo'lsa, takrorlanish munosabati bilan berilgan deyiladi. 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); 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, chaqiruv funktsiyalari 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. Keling, ko'rib chiqaylik maxsus holat ketma-ketlikdagi keyingi qiymat biriga emas, balki bir vaqtning o'zida bir nechta oldingi qiymatlarga bog'liq bo'lgan takroriy munosabatlar. Masalan, mashhur Fibonachchi ketma-ketligi, unda har bir keyingi element oldingi ikkitasining yig'indisidir: "Frontal" yondashuv bilan siz quyidagilarni yozishingiz mumkin: Function Fib(n: integer): integer; boshlang, agar n > 1 bo'lsa, Fib:= Fib(n-1) + Fib(n-2) boshqa Fib:= 1; oxiri; Har bir Fib qo'ng'irog'i o'zining ikkita nusxasini yaratadi, har bir nusxa yana ikkitasini yaratadi va hokazo. Operatsiyalar soni soni bilan ortadi n eksponent sifatida, garchi iterativ yechim uchun chiziqli n operatsiyalar soni. Aslida, yuqoridagi misol bizga buni o'rgatmaydi QACHON aks holda rekursiya ishlatilmasligi kerak QANAQASIGA 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 – dastlabki shartlar (1, 1) // n – talab qilinadigan Fibonachchi soni funksiyasining soni Fib(x1, x2, n: integer): butun son; var x3: integer; boshlang, agar n > 1 bo'lsa, unda x3 boshlanadi:= x2 + x1; x1:= x2; x2:= x3; end else Fib:= x2; oxiri; diskret matematika daraxtlarni o'rganish. Ta'rif:
biz chekli to'plamni chaqiramiz T, bir yoki bir nechta tugunlardan iborat bo'lib, shunday qilib: 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. Guruch. 3. Daraxt. Shaklda. 3-rasmda etti tugunli daraxt ko'rsatilgan. Oddiy daraxtlar pastdan yuqoriga qarab o'sadigan bo'lsa-da, ularni boshqa tomonga chizish odatiy holdir. Diagrammani qo'lda chizishda, bu usul yanada qulayroq ekanligi aniq. Ushbu nomuvofiqlik tufayli, ba'zida bir tugun boshqasining tepasida yoki ostida deyilsa, chalkashlik paydo bo'ladi. Shu sababli, shajarani tavsiflashda, tugunlarni ildiz ajdodlariga yaqinroq, uzoqroqlarni esa avlodlar deb atashda 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 bir chiziqqa cho'zilgan. Guruch. 4b-ni ichki qavslarni o'z ichiga olgan ba'zi algebraik formulalarning diagrammasi sifatida ham ko'rish mumkin. Guruch. 4c-rasmda daraxt tuzilishini bosqichma-bosqich ro'yxat sifatida ko'rsatishning yana bir mashhur usuli keltirilgan. Guruch. 4. Daraxt tuzilmalarini tasvirlashning boshqa usullari: (a) ichki to'plamlar; (b) ichki qavslar; (c) imtiyozlar ro'yxati. Qattiq ro'yxat dastur kodini formatlash usuli bilan aniq o'xshashliklarga ega. Darhaqiqat, tuzilgan dasturlash paradigmasi doirasida yozilgan dastur ichki o'rnatilgan tuzilmalardan iborat daraxt sifatida ifodalanishi mumkin. Siz, shuningdek, bir chet ro'yxati va o'rtasida o'xshashlik chizish mumkin ko'rinish bo'limlari kichik bo'limlarni o'z ichiga olgan kitoblardagi mundarijalar, 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'llaniladi. 3 va 4 bu tizim quyidagilarni beradi: 1. A; 1,1B; 1,2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G; Daraxt tuzilmalari bilan bog'liq barcha algoritmlarda har doim bir xil fikr, ya'ni g'oya paydo bo'ladi o'tish yoki daraxtning o'tishi. Bu daraxt tugunlariga tashrif buyurishning bir usuli bo'lib, unda har bir tugun bir martadan o'tadi. Bu daraxt tugunlarining chiziqli joylashishiga olib keladi. Xususan, uchta yo'l bor: tugunlardan oldinga, teskari va oxirgi tartibda o'tishingiz mumkin. Oldinga o'tish algoritmi: Bu algoritm rekursivdir, chunki daraxtning o'tishi pastki daraxtlarning o'tishini o'z ichiga oladi va ular o'z navbatida bir xil algoritm yordamida kesib o'tiladi. Xususan, rasmdagi daraxt uchun. 3 va 4, to'g'ridan-to'g'ri o'tish tugunlar ketma-ketligini beradi: A, B, C, D, E, F, G. Olingan ketma-ketlik daraxtni qavslar ichida va Dewey o'nli yozuvida tasvirlashda tugunlarning chapdan o'ngga sanab o'tishiga, shuningdek, uni stadlangan ro'yxat sifatida ko'rsatishda yuqoridan pastga o'tishga mos keladi. Ushbu algoritmni dasturlash tilida amalga oshirishda ildizni bosish ba'zi amallarni bajaruvchi protsedura yoki funksiyaga, pastki daraxtlardan o'tish esa o'ziga rekursiv qo'ng'iroqlarga mos keladi. Xususan, ikkilik daraxt uchun (har bir tugunda ko'pi bilan ikkita pastki daraxt mavjud), mos keladigan protsedura quyidagicha ko'rinadi: // Preorder Traversal – to'g'ridan-to'g'ri buyurtma protsedurasining inglizcha nomi PreorderTraversal((Argumentlar)); begin //DoSomething ildizini uzatish ((Argumentlar)); //Chap pastki daraxtning o'tishi if (Chap pastki daraxt mavjud) keyin PreorderTransversal((2-argumentlar)); //O'ng pastki daraxtning o'tishi if (O'ng pastki daraxt mavjud) keyin PreorderTransversal((3-argumentlar)); oxiri; Ya'ni, barcha pastki daraxtlar chapdan o'ngga o'tadi va ildizga qaytish bu kesishmalar orasida joylashgan. Shakldagi daraxt uchun. 3 va 4 tugunlar ketma-ketligini beradi: B, A, D, C, E, G, F. Tegishli rekursiv protsedurada harakatlar rekursiv chaqiruvlar orasidagi bo'shliqlarda joylashgan bo'ladi. Xususan, ikkilik daraxt uchun: // Inorder Traversal – teskari tartib protsedurasining inglizcha nomi InorderTraversal((Argumentlar)); begin //Chap pastki daraxt bo'ylab sayohat qilish if (Chap pastki daraxt mavjud) keyin InorderTraversal((Argumentlar 2)); //DoSomething((Argumentlar)) ildizini uzatish; Chapdan o'ngga barcha pastki daraxtlardan o'ting, Ildizga boring. Shakldagi daraxt uchun. 3 va 4 tugunlar ketma-ketligini beradi: B, D, E, G, F, C, A. // Postorder Traversal – yakuniy buyurtma protsedurasining inglizcha nomi PostorderTraversal((Arguments)); start //Chap pastki daraxt bo'ylab sayohat qilish if (Chap pastki daraxt mavjud) keyin PostorderTraversal((Argumentlar 2)); //O'ng pastki daraxtdan o'tish if (O'ng pastki daraxt mavjud) keyin PostorderTraversal((3-argumentlar)); //DoSomething((Argumentlar)) ildizini uzatish; oxiri; 5.3. Daraxtning kompyuter xotirasida tasvirlanishi Agar ba'zi ma'lumotlar daraxt 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'zgaruvchilar yordamida amalga oshiriladi. Masalan, har bir tugunda butun son mavjud boʻlgan ikkilik daraxt quyida tavsiflangan PTree tipidagi oʻzgaruvchi yordamida saqlanishi mumkin: PTree = ^TTree turi; TTree = rekord Inf: butun son; Bunday yozuvlardan tuzilgan daraxt misoli 6-rasmda keltirilgan. Guruch. 6. TTree tipidagi yozuvlardan tuzilgan daraxt. Har bir yozuv bitta raqam va ikkita ko'rsatgichni o'z ichiga oladi 5.3. Daraxtning kompyuter xotirasida tasvirlanishi, 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, sizga tegishli material bilan tanishib chiqishingizni tavsiya qilamiz. Keling, rasmda ko'rsatilgan daraxtni chizish algoritmini ko'rib chiqaylik. 6. Agar har bir chiziq tugun deb hisoblansa, u holda bu rasm oldingi bobda berilgan daraxt ta'rifini to'liq qondiradi. Guruch. 6. Daraxt. Rekursiv protsedura aniq bir chiziqni (birinchi novdagacha magistral) chizadi va keyin ikkita pastki daraxtni chizish uchun o'zini chaqiradi. Subdaraxtlar ularni o'z ichiga olgan daraxtdan boshlang'ich nuqtasi koordinatalari, aylanish burchagi, magistral uzunligi va ulardagi novdalar soni (bir kam) bilan farqlanadi. Bu farqlarning barchasi rekursiv protsedura parametrlari bo'lishi kerak. Delphida yozilgan bunday protseduraning namunasi quyida keltirilgan: Protsedura daraxti(Canvas: TCanvas; //Daraxt chiziladigan tuval x,y: kengaytirilgan; //Ildiz koordinatalari Burchak: kengaytirilgan; //Daraxt o'sadigan burchak TrunkLength: kengaytirilgan; //Magistral uzunligi n: butun son / / Filiallar soni (yana qancha //rekursiv qo'ng'iroqlar qoladi)); var x2, y2: kengaytirilgan; //Magistral uchi (tarmoq nuqtasi) boshlanadi x2:= x + TrunkLength * cos(Burchak); y2:= y - TrunkLength * sin(Burchak); Canvas.MoveTo(round(x), round(y)); Canvas.LineTo(round(x2), round(y2)); Banarasning Buyuk ibodatxonasidagi afsonaga ko'ra, dunyoning o'rtasini belgilovchi sobor ostida bronza disk joylashgan bo'lib, uning ustiga 3 ta olmos tayoq o'rnatilgan, balandligi bir tirsak va asalari kabi qalin. Uzoq vaqt oldin, vaqtning boshida, bu monastirning rohiblari Brahma xudosi oldida haqorat qilishgan. G'azablangan Brahma uchta baland tayoq o'rnatdi va ulardan biriga 64 ta sof oltin disk qo'ydi, shunda har bir kichikroq disk kattaroq bo'ladi. 64 ta diskning hammasi Xudo Brahma dunyoni yaratishda ularni qo'ygan tayoqdan boshqa tayoqqa o'tkazilishi bilanoq, minora ma'bad bilan birga changga aylanadi va dunyo momaqaldiroq ostida nobud bo'ladi. Brahmadan mustaqil ravishda, bu jumboq 19-asrning oxirida frantsuz matematigi Eduard Lukas tomonidan taklif qilingan. Sotilgan versiyada odatda 7-8 disk ishlatilgan (7-rasm). Guruch. 7. “Xanoy minoralari” boshqotirmasi. Buning yechimi bor deb faraz qilaylik n-1 disk. Keyin siljish uchun n disklar uchun quyidagi amallarni bajaring: 1) Shift n-1 disk. Chunki ish uchun n= 1 bo'lsa, qayta tartibga solish algoritmi aniq, keyin induksiya orqali (1) - (3) amallar yordamida biz ixtiyoriy sonli disklarni qayta tartibga solishimiz mumkin. Berilgan disklar soni uchun qayta tartibga solishning butun ketma-ketligini chop etadigan rekursiv protsedura yarataylik. Har safar bunday protsedura chaqirilganda, u bir siljish haqida ma'lumotni chop etishi kerak (algoritmning 2-bandidan). (1) va (3) bandlardan qayta tartiblash uchun protsedura disklar soni bittaga kamaygan holda o'zini chaqiradi. //n – disklar soni //a, b, c – pin raqamlari. Shift a pinidan //b piniga yordamchi pin c bilan amalga oshiriladi. protsedura Xanoy(n, a, b, c: butun son); agar n > 1 bo'lsa, Xanoyni boshlang (n-1, a, c, b); writeln(a, " -> ", b); Tahlil qilish vazifasi arifmetik ifodani va unga kiritilgan o'zgaruvchilarning ma'lum qiymatlarini o'z ichiga olgan mavjud satr yordamida ifoda qiymatini hisoblashdir. 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 mos ravishda pastki daraxtlar sifatida ko'rib chiqilishi mumkin. Guruch. 8-rasmda quyidagi ifodaga mos keladigan daraxt misoli keltirilgan: Guruch. 8. Arifmetik ifodaga mos sintaksis daraxti (6). Bunday daraxtda oxirgi tugunlar har doim o'zgaruvchi 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 daraxtni terminal tartibida kesib o'tish kerak. Tegishli tugunlar ketma-ketligi chaqirdi teskari polyak yozuvi arifmetik ifoda. Sintaksis daraxtini qurishda siz e'tibor berishingiz kerak keyingi xususiyat. Agar, masalan, ifoda mavjud bo'lsa va chapdan o'ngga qo'shish va ayirish amallarini o'qiymiz, keyin to'g'ri sintaksis daraxtida ortiqcha o'rniga minus bo'ladi (9a-rasm). Aslida, bu daraxt ifodaga mos keladi, agar siz (8) ifodani o'ngdan chapga qarab tahlil qilsangiz, daraxt yaratishni osonlashtirishingiz mumkin. Bunday holda, natijada rasm bilan daraxt hosil bo'ladi. 9b, 8a daraxtiga teng, lekin belgilarni 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 chaqiruv bilan cheklash imkonini beradi, agar motiv samaradorlikni oshirish bo'lsa, bu etarli bo'lishi mumkin. 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 ko'p bajariladi. Har bir qadamda aniq nima qilinishini qadam raqami bilan aniqlash kerak. Qadam raqamini 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 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 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 ichki 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 siz radix sanoq tizimidagi qadamlarni raqamlasangiz, 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. Oddiy kasrli yozuvdagi qadam raqami: Jami qadamlar bo'ladi n k. Ularning sonlarini o'nlik sanoq sistemasida ko'rib chiqish va ularning har birini radiks tizimiga aylantirish orqali n, biz indeks qiymatlarini olamiz: M:= round(IntPower(n, k)); for i:= 0 to M-1 do begin Number:= i; for p:= 0 to k-1 do start Indexes := Number mod n; oxiri; DoSomething (indekslar); oxiri; Yana bir bor ta'kidlab o'tamizki, usul universal emas va har bir vazifa uchun har xil narsani o'ylab topishga to'g'ri keladi. Xavfsizlik masalalari 1. Quyidagi rekursiv protsedura va funksiyalar nima qilishini aniqlang. (a) Rec(4) chaqirilganda quyidagi protsedura qanday chop etiladi? Procedure Rec(a: integer); yozishni boshlash (a); agar a>0 bo'lsa, Rec(a-1); writeln(a); oxiri; (b) Nod(78, 26) funksiyaning qiymati qanday bo'ladi? Funktsiya Nod(a, b: integer): integer; start if a > b keyin Nod:= Nod(a – b, b) else if b > a then Nod:= Nod(a, b – a) else Nod:= a; oxiri; (c) A(1) chaqirilganda quyidagi protseduralar orqali nima chop etiladi? Protsedura A(n: butun son); protsedura B(n: butun son); protsedura A(n: butun son); boshlash writeln(n); B(n-1); oxiri; protsedura B(n: butun son); boshlash writeln(n); agar n (d) BT(0, 1, 3) ga qo'ng'iroq qilishda quyidagi protsedura qanday chop etiladi? Protsedura BT(x: real; D, MaxD: butun son); agar D = MaxD bo'lsa boshlanadi, keyin writeln(x) boshqacha boshlanadi BT(x – 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); oxiri; oxiri; 2. Ouroboros - ochilganda o'z dumini yutib yuboradigan ilon (14-rasm) uzunlikka ega. 5. Quyidagi arifmetik ifoda uchun sintaksis daraxtini grafik tarzda tasvirlang: Bu ifodani teskari polyak yozuvida yozing. 6. Quyidagi grafik uchun (15-rasm) qo'shnilik matritsasi va insidans matritsasini yozing. 1. Faktorialni yetarlicha hisoblab chiqish katta raqam marta (million yoki undan ortiq), rekursiv va iterativ algoritmlarning samaradorligini solishtiring. Bajarish vaqti qancha farq qiladi va bu nisbat faktorial hisoblanayotgan raqamga qanday bog'liq bo'ladi? 2. Qavslarning satrda to‘g‘ri joylashishini tekshiruvchi rekursiv funksiyani yozing. Agar tartib to'g'ri bo'lsa, quyidagi shartlar bajariladi: (a) ochish va yopish qavslar soni teng. Noto'g'ri joylashtirishga misollar:)(, ())(, ())(() va boshqalar. 3. Chiziqda yumaloq va kvadrat qavslar bo'lishi mumkin. Har bir ochiladigan qavsda bir xil turdagi (dumaloq - yumaloq, kvadrat - kvadrat) mos keladigan yopish qavslari mavjud. Bu holatda qavslar to'g'ri joylashtirilgan yoki yo'qligini tekshiradigan rekursiv funktsiyani yozing. Noto'g'ri joylashtirishga misol: ([) ]. 4. 6 uzunlikdagi oddiy qavs konstruksiyalari soni 5 ta: ()()(), (())(), ()(()), ((())), (()()). Eslatma: Minimal uzunlikdagi to'g'ri qavs tuzilishi "()". Uzunroq uzunlikdagi tuzilmalar qisqaroq uzunlikdagi tuzilmalardan ikki usulda olinadi: (a) agar kichikroq struktura qavs ichiga olingan bo'lsa, 5. 1 dan N gacha bo‘lgan butun sonlar uchun barcha mumkin bo‘lgan almashtirishlarni chop etuvchi protsedura yarating. 6. To‘plamning barcha kichik to‘plamlarini (1, 2, ..., N) chop etuvchi protsedura yarating. 7. N natural sonning barcha mumkin bo‘lgan tasvirlarini boshqa natural sonlar yig‘indisi sifatida chop etuvchi protsedura yarating. 8. Quyidagi algoritm yordamida massiv elementlari yig‘indisini hisoblaydigan funksiya tuzing: massiv ikkiga bo‘linadi, har bir yarmidagi elementlar yig‘indilari hisoblab chiqiladi va qo‘shiladi. Massivning yarmidagi elementlarning yig'indisi xuddi shu algoritm yordamida, ya'ni yana yarmiga bo'lish orqali hisoblanadi. Massivning hosil bo'lgan qismlari har birida bitta element bo'lmaguncha bo'linish sodir bo'ladi va shunga mos ravishda yig'indini hisoblash ahamiyatsiz bo'ladi. Izoh: Bu algoritm muqobildir. Haqiqiy qiymatli massivlar bo'lsa, u odatda kichikroq yaxlitlash xatolariga yo'l qo'yadi. 10. Kox egri chizig'ini chizuvchi protsedura yarating (12-rasm). 11. Shaklni takrorlang. 16. Rasmda har bir keyingi iteratsiyada aylana 2,5 marta kichikroq (bu koeffitsientni parametr qilish mumkin). 1. D. Knut. Kompyuter dasturlash san'ati. v. 1. (2.3-bo'lim. “Daraxtlar”).
Salom N 2
…
Salom N 10
…
Salom N 1
…
Salom N 10
Salom N 10
…
Salom N 1Protsedura BinaryRepresentation(x: integer); var c, x: integer; start (Birinchi blok. Protseduralarni chaqirish tartibida bajariladi) c:= x mod 2;
Fib:= Fib(x1, x2, n-1);
5.1. Asosiy ta'riflar. Daraxtlarni tasvirlash usullari
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.
5.2. O'tayotgan daraxtlar
Tegishli rekursiv protsedurada harakatlar rekursiv qo'ng'iroqlardan keyin joylashgan bo'ladi. Xususan, ikkilik daraxt uchun:
6. Rekursiv algoritmlarga misollar
6.1. Daraxt chizish
agar n > 1 bo'lsa, daraxtni boshlang (Canvas, x2, y2, Angle+Pi/4, 0,55*TrunkLength, n-1);
Jarayon katta disk hech qachon kichikroqning ustiga tushmasligini talab qiladi. Rohiblar ikkilanishda: ular siljishlarni qanday tartibda bajarishlari kerak? Ushbu ketma-ketlikni hisoblash uchun ularni dasturiy ta'minot bilan ta'minlash talab qilinadi.
2) Shift n th diskni qolgan bo'sh pinga joylashtiring.
3) Biz stackni o'zgartiramiz n Yuqoridagi (1) nuqtada -1 disk qabul qilindi n- disk.Xanoy (n-1, c, b, a);
7.3. Daraxt tugunini uning soni bo'yicha aniqlash
Raqam:= Raqam div n;
Vazifalar
(b) har qanday juftlik ichida ochilish - mos keladigan yopish qavslari mavjud, qavslar to'g'ri joylashtirilgan.
2 uzunlikdagi barcha oddiy qavs tuzilmalarini yaratish uchun rekursiv dastur yozing n.
(b) ikkita kichikroq struktura ketma-ket yozilsa.
Adabiyot
2. N. Wirth. Algoritmlar va ma'lumotlar tuzilmalari.
