Imtihon topshirig'ini tahlil qilish uchun rekursiv algoritm. Rekursiya va rekursiv algoritmlar. Arifmetik ifodalarni tahlil qilish

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-parametrli 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 rekursiyaning abadiy tugashi uchun zaruriy shartdir. 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; B protsedurasi (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.

Agar oddiy rekursiyani Ouroborosga qiyoslash mumkin bo‘lsa (3-rasm), unda “Bo‘rilar qo‘rqib ketishdi, bir-birini yeb ketishdi” degan mashhur bolalar she’ridan murakkab rekursiya tasvirini olish mumkin. Ikki bo'ri bir-birini yeyayotganini tasavvur qiling va siz murakkab rekursiyani tushunasiz.

Guruch. 3. Ouroboros - o'z dumini yutib yuboradigan ilon. Teodor Pelekanosning "Sinoziy" simyoviy risolasidan olingan rasm (1478).

Guruch. 4. Kompleks rekursiya.

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
Salom N 2
…
Salom N 10

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 boshlasam

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
…
Salom N 1

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 shu 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
…
Salom N 10
Salom N 10
…
Salom N 1

Xuddi shu ishni rekursiyasiz bajarish uchun ikkita tsikl kerak bo'ladi.

Xuddi shu protsedura qismlarini bajarish vaqt o'tishi bilan intervalgacha bo'lganligidan 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'lishdan butun sonni 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. 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. Aynan:

Procedure BinaryRepresentation(x: integer); var c, x: integer; start (Birinchi blok. Protseduralarni chaqirish tartibida bajariladi) c:= x mod 2; 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);

Har bir bunday yangilanish (x:= x * i) chaqiriladi iteratsiya, va takroriy takrorlash jarayoni iteratsiya.

Ammo shuni ta'kidlaymizki, (1) munosabat ketma-ketlikning sof rekursiv ta'rifi va n-elementni hisoblash aslida f funktsiyasini o'zidan qayta-qayta olishdir:

Xususan, faktorial uchun quyidagilarni yozish mumkin:

Function Factorial(n: integer): integer; agar n > 1 bo'lsa, 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, ketma-ketlikdagi keyingi qiymat biriga emas, balki bir vaqtning o'zida bir nechta oldingi qiymatlarga bog'liq bo'lgan takroriy munosabatlarning alohida holatini ko'rib chiqaylik. Masalan, mashhur Fibonachchi ketma-ketligi, unda har bir keyingi element oldingi ikkitasining yig'indisidir:

"Frontal" yondashuv bilan siz quyidagilarni yozishingiz mumkin:

Funktsiya 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 Eksponensial ravishda, garchi iterativ yechim chiziqli bo'lsa ham n operatsiyalar soni.

Aslida, yuqoridagi misol bizga buni o'rgatmaydi QACHON aks holda rekursiya ishlatilmasligi kerak QANAQASIGA uni ishlatmaslik 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; Fib:= Fib(x1, x2, n-1); end else Fib:= x2; oxiri;

Shunga qaramay, takroriy echimlar afzalroqdir. Savol shundaki, bu holatda rekursiyadan qachon foydalanish kerak?

Faqat bitta rekursiv qo'ng'iroqni o'z ichiga olgan har qanday rekursiv protseduralar va funktsiyalar iterativ tsikllar bilan osongina almashtirilishi mumkin. Oddiy rekursiv bo'lmagan hamkasbi bo'lmagan narsani olish uchun siz o'zlarini ikki yoki undan ortiq marta chaqiradigan protseduralar va funktsiyalarga murojaat qilishingiz kerak. Bunday holda, chaqirilgan protseduralar to'plami endi rasmdagi kabi zanjir hosil qilmaydi. 1, lekin butun daraxt. Hisoblash jarayoni shu tarzda tashkil etilishi kerak bo'lgan muammolarning keng sinflari mavjud. Ular uchun rekursiya eng oddiy va eng tabiiy yechim bo'ladi.

5. Daraxtlar

O'zini bir necha marta chaqiradigan rekursiv funktsiyalarning nazariy asosi daraxtlarni o'rganuvchi diskret matematikaning bo'limidir.

5.1. Asosiy ta'riflar. Daraxtlarni tasvirlash usullari

Ta'rif: biz chekli to'plamni chaqiramiz T, bir yoki bir nechta tugunlardan iborat bo'lib, shunday qilib:
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.

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 aksincha 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.

Daraxtni boshqa usullar bilan grafik 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 ifodalashning 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 dasturni bir-birining ichida joylashgan tuzilmalardan iborat daraxt sifatida ko'rsatish mumkin.

Shuningdek, siz bosqichli ro'yxat va kitoblardagi mundarijalarning ko'rinishi o'rtasida o'xshashlikni chizishingiz mumkin, bu erda bo'limlar kichik bo'limlarni o'z ichiga oladi, 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 ushbu 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;

5.2. O'tayotgan daraxtlar

Daraxt tuzilmalari bilan bog'liq barcha algoritmlarda har doim bir xil g'oya, 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:

Ildizga boring
To'g'ridan-to'g'ri tartibda chapdan o'ngga barcha pastki daraxtlardan o'ting.

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((Arguments)); begin //DoSomething ildizini uzatish ((Argumentlar)); //Chap pastki daraxtning o'tishi if (Chap pastki daraxt mavjud) keyin PreorderTransversal((2-argumentlar)); //O'ng pastki daraxtning ko'chishi agar (O'ng pastki daraxt mavjud bo'lsa) keyin PreorderTransversal((3-argumentlar)); oxiri;

Ya'ni, birinchi navbatda protsedura barcha amallarni bajaradi va shundan keyingina barcha rekursiv qo'ng'iroqlar sodir bo'ladi.

Teskari o'tish algoritmi:

Chap pastki daraxtdan o'ting,
Ildizga boring
Chapdagi keyingi pastki daraxtdan o'ting.
Ildizga boring
eng o'ng pastki daraxtni kesib o'tmaguncha va hokazo.

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((Arguments)); start //Chap pastki daraxt bo'ylab sayohat qilish, agar (chap pastki daraxt mavjud bo'lsa) keyin InorderTraversal((2-argumentlar)); //DoSomething((Argumentlar)) ildizini uzatish; //O'ng pastki daraxtni aylanib o'ting, agar (o'ng pastki daraxt mavjud bo'lsa) keyin InorderTraversal((3-argumentlar)); oxiri;

Yakuniy tartib o'tish algoritmi:

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.

Tegishli rekursiv protsedurada harakatlar rekursiv chaqiruvlardan keyin joylashgan bo'ladi. Xususan, ikkilik daraxt uchun:

// 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 bo'lgan ikkilik daraxt quyida tavsiflangan PTree tipidagi o'zgaruvchi yordamida saqlanishi mumkin:

PTree = ^TTree turi; TTree = rekord Inf: butun son; LeftSubTree, RightSubTree: PTree; oxiri;

Har bir tugun PTree turiga ega. Bu ko'rsatgich bo'lib, har bir tugun undagi Yangi protsedurani chaqirish orqali yaratilishi kerak. Agar tugun barg tugun bo'lsa, uning LeftSubTree va RightSubTree maydonlariga qiymat beriladi. nol. Aks holda, LeftSubTree va RightSubTree tugunlari ham Yangi protsedura yordamida yaratiladi.

Bunday yozuvlardan biri sxematik tarzda rasmda ko'rsatilgan. 5.

Guruch. 5. TTree tipidagi yozuvning sxematik tasviri. Yozuv uchta maydonga ega: Inf - raqam, LeftSubTree va RightSubTree - bir xil TTree tipidagi yozuvlarga ko'rsatgichlar.

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 nol, 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 tanishishingizni tavsiya qilamiz.

6. Rekursiv algoritmlarga misollar

6.1. Daraxt chizish

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)); agar n > 1 bo'lsa, daraxtni boshlang (Canvas, x2, y2, Angle+Pi/4, 0,55*TrunkLength, n-1); Daraxt(Canvas, x2, y2, Angle-Pi/4, 0,55*TrunkLength, n-1); oxiri; oxiri;

Rasmni olish uchun. 6 ushbu protsedura quyidagi parametrlar bilan chaqirildi:

Daraxt(Image1.Canvas, 175, 325, Pi/2, 120, 15);

E'tibor bering, chizish rekursiv chaqiruvlardan oldin amalga oshiriladi, ya'ni daraxt to'g'ridan-to'g'ri tartibda chiziladi.

6.2. Xanoy minoralari

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.
Jarayon kattaroq 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.

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.
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.

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 siljishlarning 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); Xanoy (n-1, c, b, a); end else writeln(a, " -> ", b); oxiri;

E'tibor bering, bu holda rekursiv chaqirilgan protseduralar to'plami teskari tartibda kesib o'tiladigan daraxtni hosil qiladi.

6.3. Arifmetik ifodalarni tahlil qilish

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 quyidagi xususiyatga e'tibor berish kerak. 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). Aslini olganda, 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 paydo 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 qo'ng'iroq bilan cheklash imkonini beradi, agar motiv maksimal samaradorlikni oshirish bo'lsa, bu etarli bo'lishi mumkin.

7.3. Daraxt tugunini uning soni bo'yicha aniqlash

Ushbu yondashuvning g'oyasi rekursiv qo'ng'iroqlarni oddiy tsikl bilan almashtirishdan iborat bo'lib, u daraxtda rekursiv protseduralar orqali hosil bo'lgan tugunlar qanchalik ko'p bo'lsa, shuncha marta 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, ularni yuqorida ko'rsatilganidek, 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; Raqam:= Raqam div n; oxiri; DoSomething (indekslar); oxiri;

Yana bir bor ta'kidlab o'tamizki, usul universal emas va har bir vazifa uchun siz boshqacha narsani o'ylab topishingiz kerak bo'ladi.

Nazorat savollari

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;

Protsedura A(n: butun son); B protsedurasi (n: butun son); protsedura A(n: butun son); boshlash writeln(n); B(n-1); oxiri; B protsedurasi (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: integer); 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. L, bosh atrofidagi diametri D, qorin devorining qalinligi d. Aniqlang, u o'ziga qancha quyruq siqib qo'yishi mumkin va undan keyin quyruq nechta qatlamga qo'yiladi?

Guruch. 14. Kengaytirilgan Ouroboros.

3. Shakldagi daraxt uchun. 10a oldinga, teskari va oxirgi o'tish tartibida tashrif tugunlarining ketma-ketligini ko'rsatadi.

4. Ichki qavslar yordamida aniqlangan daraxtni grafik tarzda tasvirlang: (A(B(C, D), E), F, G).

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.

Vazifalar

1. Faktorialni etarlicha ko'p marta (million yoki undan ko'p) hisoblab, rekursiv va iterativ algoritmlarning samaradorligini solishtiring. Bajarilish vaqti necha marta farqlanadi va bu nisbat faktorial hisoblanayotgan songa 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.
(b) har qanday juftlik ichida ochilish - mos keladigan yopish qavslari mavjud, qavslar to'g'ri joylashtirilgan.

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: ()()(), (())(), ()(()), ((())), (()()).
2 uzunlikdagi barcha oddiy qavs tuzilmalarini yaratish uchun rekursiv dastur yozing n.

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,
(b) ikkita kichikroq struktura ketma-ket yozilsa.

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 tuzing.

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).

Adabiyot

1. D. Knut. Kompyuter dasturlash san'ati. v. 1. (2.3-bo'lim. “Daraxtlar”).
2. N. Wirth. Algoritmlar va ma'lumotlar tuzilmalari.

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 almashtirish usuli yordamida muammoni hal qiladi. Har ikkala usul yordamida vazifalarni hal qilishning 4 ta misoli ko'rib chiqiladi. Quyidagi taqdimotda Konstantin Polyakov veb-saytidan javoblar bilan mashg'ulotlar uchun 25 ta mashq mavjud.

Yuklab oling:

Ko‘rib chiqish:

Taqdimotni oldindan ko‘rishdan foydalanish uchun Google hisobini yarating va unga 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. Rossiya Federatsiyasining gerbi - bu rekursiv aniqlangan grafik ob'ekt: unda tasvirlangan ikki boshli burgutning o'ng panjasida gerbning kichikroq nusxasi bilan toj kiygan tayoq qisilgan. Ushbu gerbda burgutning o'ng panjasida ham tayoq borligi sababli, cheksiz rekursiya olinadi. Rossiyaning rekursiv gerbi

Dasturlashda rekursiya funksiyani oʻzidan bevosita yoki boshqa funksiyalar orqali chaqiradi, masalan, A funksiyasi B funksiyasini, B funksiyasi esa A funksiyasini chaqiradi. Funksiya yoki protseduraga oʻrnatilgan qoʻngʻiroqlar soni rekursiya chuqurligi deyiladi. Rekursiyaga misol: Agar kiyimingizda yog 'dog'i bo'lsa, tashvishlanmang. Yog 'dog'lari benzin bilan olib tashlanadi. Ishqorlar esa, moy bilan tozalanadi.

Misol topshiriq: Rekursiv algoritm berilgan: protsedura F(n: integer); boshlash writeln(n); agar n

Misol topshiriq: Rekursiv algoritm berilgan: protsedura F(n: integer); writeln boshlash (n); agar n

Berilgan misol: Rekursiv algoritm berilgan: procedure F(n: integer); boshlash writeln(n); agar n Slayd 9

Misol topshiriq: Rekursiv algoritm berilgan: protsedura 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: protsedura F(n: integer); 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? * "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. S(n) F(n) ni chaqirganda chop etiladigan “yulduzlar” soni 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

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: butun son); 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