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

Uchidan oxirigacha o'tish algoritmi:

• 
  Barcha pastki daraxtlarni chapdan o'ngga o'ting,
  
• 
  Ildizga boring.
  

Shakldagi daraxt uchun. 3 va 4 bu tugunlarning ketma-ketligini beradi: B, D, E, G, F, C, A.
Tegishli rekursiv protsedurada harakatlar rekursiv chaqiriqlardan keyin paydo bo'ladi. Xususan, ikkilik daraxt uchun:
// Postorder Traversal - bu PostorderTraversal ((Argumentlar)) buyrug'i protsedurasining inglizcha nomi; begin // Chap subtree bo'ylab harakatlaning, agar (Chap subtree mavjud bo'lsa), keyin PostorderTraversal ((Argumentlar 2)); // Agar o'ng tomondagi daraxtni kesib o'ting (Agar o'ng pastki daraxt mavjud bo'lsa), keyin PostorderTraversal ((3-dalillar)); // DoSomething ((Argumentlar)) ildizi orqali yurish; oxiri;
5.3. Kompyuter xotirasida daraxt ko'rinishi
Agar biron bir ma'lumot daraxt tugunlarida joylashgan bo'lsa, uni saqlash uchun tegishli dinamik ma'lumotlar tuzilmasidan foydalanishingiz mumkin. Paskalda bu bir xil turdagi kichik daraxtlarga ko'rsatgichlarni o'z ichiga olgan yozuv (yozuv) o'zgaruvchisi yordamida amalga oshiriladi. Masalan, har bir tugun butun sonni o'z ichiga olgan ikkilik daraxtni quyida tavsiflangan PTree turidagi o'zgaruvchidan foydalanib saqlash mumkin:
PTree \u003d ^ TTree yozing; TTree \u003d yozuv Inf: integer; LeftSubTree, RightSubTree: PTree; oxiri;
Har bir tugun PTree turiga kiradi. Bu ko'rsatkich, ya'ni har bir tugun undagi New protsedurasini chaqirish orqali yaratilishi kerak. Agar tugun barg bo'lsa, unda uning LeftSubTree va RightSubTree maydonlariga qiymat beriladi nol... Aks holda, LeftSubTree va RightSubTree tugunlari ham New protsedurasi tomonidan yaratiladi.
Bunday yozuvlardan biri sxematik ravishda shakl. 5.

Shakl: 5. TTree yozuvining sxematik tasviri. Yozuvda uchta maydon mavjud: Inf - ba'zi raqamlar, LeftSubTree va RightSubTree - bir xil TTree yozuvlariga ko'rsatgichlar. Bunday yozuvlardan tashkil topgan daraxt namunasi 6-rasmda keltirilgan.

Shakl: 6. TTree yozuvlaridan tashkil topgan daraxt. Har bir yozuv bitta raqamni va ikkita ko'rsatgichni saqlaydi, ular ikkitasini o'z ichiga olishi mumkin nol, yoki shu turdagi boshqa yozuvlarning manzillari.
Agar ilgari bir xil turdagi yozuvlarga havolalarni o'z ichiga olgan yozuvlardan tashkil topgan tuzilmalar bilan ishlamagan bo'lsangiz, u holda material bilan tanishishingizni tavsiya qilamiz.
6. Rekursiv algoritmlarga misollar
6.1. Daraxt chizish
Shaklda ko'rsatilgan daraxtni chizish algoritmini ko'rib chiqing. 6. Agar har bir satr tugun deb hisoblansa, unda bu rasm oldingi bobda berilgan daraxt ta'rifini to'liq qondiradi.

Shakl: 6. Kichkina daraxt.
Rekursiv protsedura aniq bir qatorni (birinchi vilkadan oldin magistral) tortib, so'ngra ikkita kichik daraxtni chizish uchun chaqirishi kerak. Subtrees ularni o'z ichiga olgan daraxtdan boshlang'ich nuqtaning koordinatalari, burilish burchagi, magistral uzunligi va ular tarkibidagi shoxlar soni (bir oz) bilan farq qiladi. Ushbu farqlarning barchasi rekursiv protsedura parametrlari bo'yicha amalga oshirilishi kerak.
Delphi-da yozilgan bunday protseduraning namunasi quyida keltirilgan:
Jarayon daraxti (Tuval: TCanvas; // Daraxt chizilgan tuval x, y: kengaytirilgan; // Ildiz koordinatalari Burchak: kengaytirilgan; // Daraxt o'sadigan burchak TrunkLength: kengaytirilgan; // Magistral uzunligi n: tamsayı / / Vilkalar soni (hali qancha rekursiv qo'ng'iroqlar //)); var x2, y2: kengaytirilgan; // Magistralning oxiri (filial nuqtasi) x2 boshlanadi: \u003d x + TrunkLength * cos (Angle); y2: \u003d y - TrunkLength * sin (Angle); Canvas.MoveTo (dumaloq (x), dumaloq (y)); Canvas.LineTo (dumaloq (x2), dumaloq (y2)); agar n\u003e 1 bo'lsa, daraxtni boshlang (Tuval, x2, y2, Angle + Pi / 4, 0.55 * TrunkLength, n-1); Daraxt (Tuval, x2, y2, Angle-Pi / 4, 0,55 * TrunkLength, n-1); oxiri; oxiri;
Shaklni olish uchun. 6 ushbu tartib quyidagi parametrlar bilan chaqirildi:
Daraxt (Image1.Canvas, 175, 325, Pi / 2, 120, 15);
E'tibor bering, chizma rekursiv chaqiruvlardan oldin amalga oshiriladi, ya'ni daraxt to'g'ridan-to'g'ri tartibda chiziladi.
6.2. Xanoy minoralari
Afsonalarga ko'ra, Buyuk Benaras ibodatxonasida, dunyoning o'rtasini belgilaydigan sobor ostida bronza disk joylashgan bo'lib, uning ustiga bitta tirsak balandlikda va asalari kabi qalinlikda uchta olmos novdasi mahkamlangan. Uzoq vaqt oldin, bu ibodatxonaning rohiblari Brahma xudosi oldida aybdor edilar. G'azablangan Brahma uchta baland tayoqni o'rnatdi va ulardan biriga 64 dona sof oltindan yasalgan disklarni joylashtirdi, shunda har bir kichik disk kattarog'iga suyanadi. Xudo Brahma dunyoni yaratishda ularni qo'ygan novdadan 64 ta diskning barchasi boshqa bir tayoqqa ko'chirilishi bilanoq, minora ma'bad bilan birga changga aylanadi va olam momaqaldiroqlar ostida halok bo'ladi.
Jarayon shuni talab qiladiki, kattaroq disk hech qachon kichkinasini ortib ketmaydi. Monaxlar qiynalmoqda, transpozitsiyalarni qanday tartibda bajarish kerak? Ushbu ketma-ketlikni hisoblash uchun ularni dasturiy ta'minot bilan jihozlash talab qilinadi.

Braxadan qat'i nazar, 19-asrning oxiridagi ushbu jumboq frantsuz matematikasi Eduard Lukas tomonidan taklif qilingan. Sotilgan versiyada odatda 7-8 ta disk ishlatilgan (7-rasm).

Shakl: 7. "Xanoy minoralari" jumboq.
Uchun echim bor deylik n-1 disk. Keyin siljish uchun n disklar, quyidagicha davom eting:
1) almashtirish n-1 disk.
2) almashtirish nqolgan diskka qadar disk.
3) Biz to'plamini siljitamiz n(1) bosqichda olingan -1 disk ndisk.
Ish uchun n \u003d 1, siljish algoritmi aniq, keyin (1) - (3) amallari yordamida induksiya yordamida biz o'zboshimchalik bilan disklar sonini siljitishimiz mumkin.
Berilgan disklar uchun o'tkazmalarning butun ketma-ketligini nashr etadigan rekursiv protsedura yarataylik. Bunday protsedura har bir qo'ng'irog'i bilan bitta uzatish to'g'risidagi ma'lumotlarni (algoritmning 2-bandidan) bosib chiqarishi kerak. (1) va (3) bandlardan o'tkazmalar uchun protsedura disklar soni bittaga kamaytirilgan holda o'zini o'zi chaqiradi.
// n - disklar soni // a, b, c - pin raqamlari. O'tkazish a, // pinidan b pinagacha c yordamchi pimi bilan amalga oshiriladi. protsedura Xanoy (n, a, b, c: tamsayı); agar n\u003e 1 bo'lsa, keyin Xanoyni boshlang (n-1, a, c, b); writeln (a, "-\u003e", b); Xanoy (n-1, c, b, a); end else Writeln (a, "-\u003e", b); oxiri;
Shuni esda tutingki, bu holda rekursiv deb ataladigan protseduralar to'plami teskari tartibda o'tgan daraxtni hosil qiladi.
6.3. Arifmetik ifodalarni tahlil qilish
Tahlil qilishning vazifasi - arifmetik ifodani va unga kiritilgan o'zgaruvchilarning ma'lum qiymatlarini o'z ichiga olgan mavjud satrdan ifoda qiymatini hisoblash.
Arifmetik ifodalarni hisoblash jarayoni ikkilik daraxt sifatida ifodalanishi mumkin. Darhaqiqat, arifmetik operatorlarning har biri (+, -, *, /) ikkita operandani talab qiladi, ular ham arifmetik ifodalar bo'ladi va shunga ko'ra, ularni kichik daraxtlar deb hisoblash mumkin. Shakl: 8 iboraga mos keladigan daraxt namunasini ko'rsatadi:

Shakl: 8. (6) arifmetik ifodaga mos keladigan sintaksis daraxti.
Bunday daraxtda so'nggi tugunlar har doim o'zgaruvchan bo'ladi (bu erda x) yoki sonli konstantalar va barcha ichki tugunlarda arifmetik operatorlar bo'ladi. Operatorni bajarish uchun avval uning operandlarini baholash kerak. Shunday qilib, rasmdagi daraxtni oxirgi tartibda kesib o'tish kerak. Tugunlarning tegishli ketma-ketligi
deb nomlangan teskari jilo yozuvlari arifmetik ifoda.
Sintaksis daraxtini qurishda siz quyidagi xususiyatga e'tibor berishingiz kerak. Agar mavjud bo'lsa, masalan, ifoda
va biz chapdan o'ngga qo'shish va ayirish amallarini o'qiymiz, keyin to'g'ri sintaksis daraxti plyus o'rniga minusni o'z ichiga oladi (9-rasm). Darhaqiqat, bu daraxt ifodaga mos keladi (8) ifodasini, aksincha, o'ngdan chapga tahlil qilib daraxt qurilishini osonlashtirish mumkin. Bunday holda, anjir bilan daraxt. 9b, bu 8a ga teng, ammo belgilar o'zgarishini talab qilmaydi.
Xuddi shunday, ko'paytirish va bo'lish operatorlarini o'z ichiga olgan iboralarni o'ngdan chapga tahlil qilish kerak.

Shakl: 9. Ekspression uchun sintaksis daraxtlari a – b + v chapdan o'ngga (a) va o'ngdan chapga (b) o'qiyotganda.
Ushbu yondashuv rekursiyani to'liq bartaraf etmaydi. Biroq, bu o'zingizni rekursiv protseduraga faqat bitta qo'ng'iroq bilan cheklashingizga imkon beradi, agar bu maksimal ishlash haqida tashvishlanish bo'lsa etarli bo'lishi mumkin.
7.3. Daraxt tugunini uning raqamiga qarab aniqlash
Ushbu yondashuvning maqsadi - rekursiv chaqiriqlarni daraxtda rekursiv protseduralar natijasida hosil bo'lgan tugunlar qancha ko'p bo'lsa, shunchaki bajaradigan oddiy tsikl bilan almashtirish. Har bir qadamda aniq nima qilish kerakligi qadam raqami bilan belgilanishi kerak. Bosqich raqamini va kerakli harakatlarni taqqoslash ahamiyatsiz ish emas va har holda bu alohida hal qilinishi kerak.
Masalan, siz ijro etmoqchisiz k ichki ko'chadan n har birida qadamlar:
I1: \u003d 0 dan n-1 gacha bo'lganlar uchun i2: \u003d 0 dan n-1 gacha bo'lganlar uchun i3: \u003d 0 dan n-1 gacha bo'lganlar uchun ...
Agar k oldindan ma'lum emas, yuqorida aytib o'tilganidek, ularni aniq yozish mumkin emas. 6.5-bo'limda ko'rsatilgan texnikadan foydalanib, siz rekursiv protsedura yordamida kerakli miqdordagi ichki ko'chadan olishingiz mumkin:
NestedCycles protsedurasi (Ko'rsatkichlar: butun qator; n, k, chuqurlik: butun son); var i: tamsayı; agar chuqurlik bo'lsa, boshlang
Rekursiyadan xalos bo'lish va hamma narsani bitta tsiklga kamaytirish uchun, agar radiusdagi qadamlarni sanasangiz, e'tibor bering n, keyin har bir qadamda i1, i2, i3, ... raqamlaridan yoki indekslar qatoridan mos keladigan qiymatlardan tashkil topgan raqam mavjud. Ya'ni, raqamlar tsikl hisoblagichlarining qiymatlariga mos keladi. Odatiy o'nlik belgilaridagi qadam raqami:
Jami qadamlar bo'ladi n k... Ularning sonlarini o'nlik tizimda ko'rib chiqish va ularning har birini radiusli tizimga o'tkazish orqali n, biz indekslarning qiymatlarini olamiz:
M: \u003d dumaloq (IntPower (n, k)); uchun i: \u003d 0 dan M-1 gacha boshlanadi Raqam: \u003d i; p: \u003d 0 dan k-1 gacha boshlash uchun indekslar: \u003d Raqam mod n; Raqam: \u003d Raqam div n; oxiri; DoSomething (indekslar); oxiri;
Yana bir bor ta'kidlaymizki, bu usul universal emas va har bir vazifa uchun siz boshqacha narsani o'ylab topishingiz kerak bo'ladi.
Adabiyot
1. D. Knut. Kompyuter dasturlash san'ati. v. (2.3-bo'lim. "Daraxtlar").
2. N. Virt. Algoritmlar va ma'lumotlar tuzilmalari.