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

3-misol: sonni ikkilik tizimga aylantirish.
Ma'lumki, ikkilik sonning raqamlarini olish, 2-sanoq tizimining bazasiga qoldiq bilan bo'lish orqali sodir bo'ladi. Agar raqam bo'lsa, u holda uning ikkilik vakolatxonasidagi oxirgi raqam
Butun qismni 2 ga bo'linishdan olish:
biz bir xil ikkilik tasvirga ega bo'lgan raqamni olamiz, lekin oxirgi raqamsiz. Shunday qilib, yuqoridagi ikkita amalni keyingi bo'linish maydoniga qadar takrorlash kifoya, biz butun sonni 0 ga tenglashtiramiz, rekursiyasiz shunday bo'ladi:
X\u003e 0 boshlanganda c: \u003d x mod 2 boshlanadi; x: \u003d x div 2; yozish (c); oxiri;
Bu erda muammo shundaki, ikkilik vakolatxonaning raqamlari teskari tartibda hisoblanadi (oxirgisi birinchi). Raqamni normal shaklda chop etish uchun massiv elementlaridagi barcha raqamlarni eslab, ularni alohida tsiklda aks ettirishingiz kerak bo'ladi.
Rekursiya massivsiz va ikkinchi tsiklsiz chiqishni to'g'ri tartibda olishni osonlashtiradi. Aynan:
BinaryRepresentation protsedurasi (x: integer); var c, x: integer; begin (Birinchi blok. Protsedurali qo'ng'iroqlar tartibida bajariladi) c: \u003d x mod 2; x: \u003d x div 2; (Rekursiv chaqiruv) agar x\u003e 0 bo'lsa, BinaryRepresentation (x); (Ikkinchi blok. Teskari tartibda bajarilgan) yozing (c); oxiri;
Umuman olganda, biz hech qanday yutuq olmadik. Ikkilik vakolatxonaning raqamlari lokal o'zgaruvchilarda saqlanadi, ular rekursiv protseduraning har bir ishlaydigan misoli uchun har xil. Ya'ni xotirani saqlashning imkoni bo'lmadi. Aksincha, biz ko'plab mahalliy o'zgaruvchilarni saqlash uchun qo'shimcha xotirani yo'qotamiz. Shunga qaramay, ushbu echim menga chiroyli ko'rinadi.
4. Takrorlanish munosabatlari. Rekursiya va takrorlash
Vektorlarning ketma-ketligi, agar dastlabki vektor va keyingi vektorning oldingisiga funktsional bog'liqligi berilgan bo'lsa, takrorlanish munosabati bilan beriladi, deyishadi.
Takrorlanish munosabatlari yordamida hisoblangan miqdorning oddiy misoli faktorialdir
Keyingi faktorialni avvalgisidan quyidagicha hisoblash mumkin:
Belgilanishni kiritib, biz quyidagi nisbatni olamiz:
Formuladan (1) vektorlarni o'zgaruvchan qiymatlar to'plamlari sifatida talqin qilish mumkin. Keyin ketma-ketlikning kerakli elementini hisoblash ularning qiymatlarini takroriy yangilashdan iborat bo'ladi. Xususan, faktorial uchun:
X: \u003d 1; i: \u003d 2 dan n gacha x: \u003d x * i; writeln (x);
Har bir shunday yangilanish (x: \u003d x * i) chaqiriladi takrorlashva takroriy takrorlash jarayoni takrorlash.
Shunga qaramay, (1) munosabati ketma-ketlikning aniq rekursiv ta'rifi va n elementni hisoblash aslida f funktsiyani o'zidan ko'p marta olishdir:
Xususan, faktorial uchun quyidagilarni yozishingiz mumkin:
Funktsional funktsiya (n: integer): integer; start n\u003e 1 bo'lsa, u holda Faktorial: \u003d n * Factorial (n-1) else Faktorial: \u003d 1; oxiri;
Shuni anglash kerakki, chaqiruv funktsiyalari qo'shimcha xarajatlarni keltirib chiqaradi, shuning uchun faktorialni hisoblashning birinchi varianti biroz tezroq bo'ladi. Umuman olganda, takroriy echimlar rekursiv echimlarga qaraganda tezroq ishlaydi.
Rekursiya foydali bo'lgan holatlarga o'tishdan oldin, uni ishlatmaslik kerak bo'lgan yana bir misolni ko'rib chiqing.
Ketma-ketlikning navbatdagi qiymati bittaga emas, balki bir nechta oldingi qiymatlarga birdaniga bog'liq bo'lgan takroriy munosabatlarning maxsus holatini ko'rib chiqing. Bunga misol sifatida taniqli Fibonachchi ketma-ketligi keltirilgan bo'lib, unda har bir keyingi element avvalgi ikkitasining yig'indisi:
"Boshga" yondashuv bilan siz quyidagilarni yozishingiz mumkin:
Fib funktsiyasi (n: integer): integer; agar n\u003e 1 bo'lsa boshlang Fib: \u003d Fib (n-1) + Fib (n-2) else Fib: \u003d 1; oxiri;
Fibga har bir qo'ng'iroq bir vaqtning o'zida ikkita nusxasini yaratadi, har bir nusxasi yana ikkitasini yaratadi va hokazo. Bitimlar soni raqam bilan o'sib boradi n eksponent sifatida, ammo iterativ echim bilan bo'lsa ham, chiziqli n operatsiyalar soni.
Aslida yuqoridagi misol bizni o'rgatmaydi QACHON rekursiyadan foydalanmaslik kerak va bu AS uni ishlatmaslik kerak. Axir, agar tezkor takrorlanadigan (tsiklga asoslangan) echim bo'lsa, unda xuddi shu tsiklni rekursiv protsedura yoki funktsiya yordamida amalga oshirish mumkin. Masalan:
// x1, x2 - boshlang'ich shartlar (1, 1) // n - kerakli Fibonachchi sonli funktsiya soni Fib (x1, x2, n: integer): integer; var x3: tamsayı; Agar n\u003e 1 bo'lsa boshlang, keyin x3 boshlang: \u003d x2 + x1; x1: \u003d x2; x2: \u003d x3; Fib: \u003d Fib (x1, x2, n-1); end else Fib: \u003d x2; oxiri;
Shunga qaramay, takroriy echimlarga afzallik beriladi. Savol tug'iladi, qachon bu holda siz rekursiyadan foydalanishingiz kerak?
O'zlariga faqat bitta rekursiv qo'ng'iroqni o'z ichiga olgan har qanday rekursiv protsedura va funktsiyalarni osongina takrorlanadigan ko'chadanlar bilan almashtirish mumkin. Oddiy rekursiv bo'lmagan analogga ega bo'lmagan narsani olish uchun siz o'zlarini ikki yoki undan ortiq marta chaqiradigan protsedura va funktsiyalarga murojaat qilishingiz kerak. Bunday holda, chaqirilgan protseduralar to'plami endi shaklda bo'lgani kabi zanjir hosil qilmaydi. 1, lekin butun bir daraxt. Hisoblash jarayoni shu tarzda tashkil etilishi kerak bo'lgan muammolarning keng sinflari mavjud. Ular uchun rekursiya uni hal qilishning eng oson va tabiiy usuli bo'ladi.
5. Daraxtlar
O'zlarini bir necha bor chaqiradigan rekursiv funktsiyalarning nazariy asoslari daraxtlarni o'rganadigan diskret matematikaning bo'limi hisoblanadi.
5.1. Asosiy ta'riflar. Daraxtlarni aks ettirish usullari