4-Mavzu: Rekursiya va Rekursiv triada Reja



Download 0,74 Mb.
Sana04.12.2019
Hajmi0,74 Mb.
#28297
Bog'liq
MTA-4

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

Download 0,74 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish