- Reja:
- Rekursiya haqida tushuncha. Rekursiv algoritmlar.
- Daraxtlar xaqida tushuncha.
- Daraxtlar klassifikatsiyasi.
- Daraxtlarni tasvirlash.
Rekursiya haqida tushuncha. - Rekursiya (umuman) – bu ob’ektni mazkur ob’ektga murojat qilish orqali aniqlashdir.
- 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.
- 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. - 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.
- Rekursiv yoki interatsion usul samaradorligi berilgan masalani hal qiluvchi dasturni turli boshlang’ich qiymatlarda tahlil etish orqali aniqlaydi.
- 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.
- Daraxt bosqichlari soniga daraxt balandligi deyiladi.
- Tugunlardan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi.
- 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: Otao’g’il.
- Daraxt chiqish darajasi bo’yicha klassifikatsiya qilinadi.
- 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.
Do'stlaringiz bilan baham: |