4-Mavzu: Rekursiya va Rekursiv triada Reja

• 4-Mavzu: Rekursiya va Rekursiv triada

• Reja:
• Rekursiya haqida tushuncha. Rekursiv algoritmlar.
• Daraxtlar xaqida tushuncha.
• Daraxtlar klassifikatsiyasi.
• Daraxtlarni tasvirlash.

Rekursiya haqida tushuncha.

• Izoh

• Rekursiya (umuman) – bu ob’ektni mazkur ob’ektga murojat qilish orqali aniqlashdir.

• Izoh

• Rekursiv algoritm – bu algoritmi aniqlashda o’ziga bevosita yoki bilvosita murojat qilishdir.

• Eslatma: Algoritm va dasturlarni tuzishda rekursiyadan foydalanish vaqtni tejaydi, hajmi kichi bo’ladi, lekin interaksion usulga isbatan dastur sekinroq ishlaydi hamda ko’proq hotira talab qiladi.

• Def.1.

• Agar ma’lumotlar tuzilmasi elementlari ham mazkur tuzilmaga o’xshash tuzilma bo’lsa , u holda bunday tuzilmaga rekursiv ma’lumotlar tuzilmasi deyiladi.

Rekursiv ob’ektlarga misollar.

• Serpinskiy uchburchagi.

• Rekursiv triada.

• Parametrizatsiya qilish – masala shartini tasniflash va uni hal etish uchun parametrlar aniqlanadi;
• Rekursiya bazasi (asosi) – masala yechimi aniq bo’lgan trivial holat aniqlanadi, ya’ni bu holatda funksiyani o’ziga murjat qilishi talab etilmadi.;
• Dekompozitsiya – umumiy holatni nisbatan ancha oddiy bo’lgan o’zgargan parametrli qisim masalalar orqali ifodalaydi.

• Izoh

• Rekursiv yoki interatsion usul samaradorligi berilgan masalani hal qiluvchi dasturni turli boshlang’ich qiymatlarda tahlil etish orqali aniqlaydi.

• Izoh

• Rekursiv algoritmlarni samaradorligini oshirish ko’pincha triada bosqichlarini qayta ko’rib chiqish natijasida amalga oshirish mumin.

• Faktorialini xisoblash:
• n!=1*2*…*n=n*(n-1)!
• int i,m,N; double long fact;
• void factorial(int m);
• void main()
• {
• clrscr();
• cin>>N;
• fact=1; factorial(N);
• }
• void factorial(int m)
• { if(m==1)
• {cout<
• getch();
• exit(1); }
• fact*=m; factorial(m-1); }

• Rekursiv triada:
• Parametrizatsiya:
• n – номанфий бутун сон.
• Rekursiya bazasi:
• n =0 ва n =1 учун факториал 1 га тенг.
• Dekompozitsiya:
• n!=(n-1)!*n.

Daraxt tushunchasi.

• Daraxt-bu chiziqsiz bog’langan ma’lumotlar.
• Darat o’zining quyidagi belgilari bilan tasniflanadi:
• Daraxtda shunday bitta element borki, unga boshqa elementlardan murojat yo’q. Mazkur elementga daraxt ildizi deyiladi;
• Daraxtda ixtiyoriy elementga chekli sondagi ko’rsatgichlar yordamida murojaat qilish mmkin;
• Daraxtning har bir elementi faqatgina o’zidan oldingi kelgan bitta element bilan bog’langan. Daraxtning har bir tuguni orqali yoki terminal (barg bo’lishi mumkin.

• Def.2.

• Daraxt bosqichlari soniga daraxt balandligi deyiladi.

• Def.3.

• Tugunlardan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi.

• 0-bosqich

• 1- bosqich

• 2- bosqich

• Chiqish darajalari.

• 3

• 1

• 2

Daraxtlar klassifikatsiyasi

• 1) Agar maksimal darajasi m bo’lsa, u holda bunday daraxt m-tartibli daraxt deyiladi;
• 2) Agar chiqish darajasi 0 yoki m bo’lsa u holda to’liq m – tartibli daraxt deyiladi;
• 3) agar maksimal chiqish darajasi 2 bo’lsa u holda bunday daraxt binary daraxt deyiladi;
• 4) agar chiqish darajasi 0 yoki 2 bo’lsa, u holda to’liq binary daraxt deyiladi.
• Tugunlar orasidagi bog’liqlini tavsiflash uchun yana quyidagicha atamadan foydaliniladi: Otao’g’il.

• Eslatma

• Daraxt chiqish darajasi bo’yicha klassifikatsiya qilinadi.

Daraxtlarni tavsiflash

• Mantiqiy tasvirlashda daraxtlar bog’langan ro’yhatlar ko’rinishda ifodalanadi. Bunda ro’yhat elementi tugun qiymati va chiqish darajasini o’z ichiga oluvchi information maydonga hamda chiqish darajasiga teng bo’lgan ko’rsatkichlar maydoniga ega bo’ladi.
• Daraxt grafik va chiziqsiz ro’yhat shaklidagi tasvirlanishi.

4-mavzu bo’yicha nazorat savollari

• Rekursiya nima?
• Rekursiv obyekt, algoritm, funksiya tushunchasi.
• Rekursiv triada.
• Rekursiv algoritm samaradorligini aniqlash va oshirish yo’llari.
• Daraxt tushunchasi: balandligi, chiqish darajasi.
• Daraxt klassifikassiyasi.
• Daraxtlarni mantiqiy mavsiflash.