Algoritmlar va berilganlar strukturalari

#include

int fack1(int); int main()

{

int n;

cout << "n="; cin >> n; cout << fack1(n) << endl; return 0;

system ("pause");

}

int fack1(int k)

{

if (k < 0) return 0; if (k == 0) return 1;

else return fack1(k)*fack1(k-1);

}


Misol 2: Fibonachchi ketma ketligining n – hadini rekursiya qism dastur orqali hisoblovchi dastur.

#include

int fib(int); int main()

{

int n;

cout << "n="; cin >> n;

cout << fib(n) << endl;

return 0;

}

int fib(int k)

{

if (k == 0 || k == 1) return 1; else return fib(k - 1) + fib(k - 2);

}

5. 
   14 Funksiya murojaatlari va Rekursiya Joriyi
   
6. 
   Rekursiv algoritmlar muammoning yechimini xuddi shu muammoning kichik kichik muammolariga echim topish orqali topish mumkin degan fikrga asoslanadi. Rekursiv algoritmda funktsiya o'zi oldingi versiyasi nuqtai nazaridan belgilanadi. Shuni ta'kidlash kerakki, bu o'z-o'zidan murojaat qilish abadiy murojaat etmaslik uchun tugatish shartiga ega bo'lishi kerak. To'xtatish holati o'ziga murojaat qilishdan oldin tekshiriladi. Rekursiv algoritmning dastlabki bosqichi muammoning rekursiv ta'rifining asosiy bandiga bog'liq. Dastlabki bosqichdan keyingi bosqichlar muammoning induktiv bandlari bilan bog'liq. Rekursiv algoritmlar ko'p holatlarda sodda echimni ta'minlaydi va xuddi shu muammo uchun iterativ algoritmga qaraganda tabiiy fikrlash usuliga yaqinroq bo'ladi. Ammo umuman olganda, rekursiv algoritmlar ko'proq xotirani talab qiladi va ular hisoblash uchun qimmatga tushadi.
   

15. Rekusiv murojaat anatomiyasi

Funksiya o’ziga o’zi to’g’ridan-to’g’ri yoki qandaydir vosita orqali murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv funksiya deb ataladi.
16 . Dumli Rekursiya
Dumli rekursiyasi nima?
Rekursiv chaqiruv funktsiya tomonidan bajarilgan oxirgi narsa bo'lganda, rekursiv funktsiya dumli rekursiv bo'ladi. Masalan, quyidagi C ++ funktsiyasi print () dumli rekursivdir. Dumli bo'lmagan rekursiv funktsiyani optimallashtirish uchun dumli-rekursiv deb yozish mumkinmi?
N ning faktorialini hisoblash uchun quyidagi funktsiyani ko'rib chiqing. Bu dumsizsiz-rekursiv funktsiya. Garchi u birinchi qarashda dumli rekursiviga o'xshasa ham. Agar yaqindan ko'rib chiqsak, haqiqat (n-1) bilan qaytarilgan qiymat aslida (n) ishlatilganligini ko'rishimiz mumkin, shuning uchun haqiqatga (n-1) qo'ng'iroq haqiqat (n) tomonidan bajarilgan oxirgi narsa emasa

5. 
   18 Daraxtlar haqida tushucha. Daraxtlar klassifikatsiyasi va ularni mantiqiy tasvirlash.
   
6. 
   Uzellar (elementlar) va ularning munosabatlaridan iborat elementlar to‟plamining ierarxik tuzilmasiga daraxtsimon ma‟lumotlar tuzilmasi deyiladi.
   
7. 
   Daraxt – bu shunday chiziqsiz bog‟langan ma‟lumotlar tuzilmasiki, u quyidagi belgilari bilan tavsiflanadi:
   
8. 
   - daraxtda shunday bitta element borki, unga boshqa elementlardan murojaat yo‟q. Bu element daraxt ildizi deyiladi;
   
9. 
   - daraxtda ixtiyoriy element chekli sondagi ko‟rsatkichlar yordamida boshqa tugunlarga murojaat qilishi mumkin;
   
10. 
    - daraxtning har bir elementi faqatgina o‟zidan oldingi kelgan bitta element bilan
    
11. 
    bog‟langan.
    

19. 
    Binar daraxtlar.
    

Binar daraxtda har bir tugun-elementdan ko‟pi bilan 2 ta shox chiqadi. Daraxtlarni xotirada tasvirlashda uning ildizini ko‟rsatuvchi ko‟rsatkich berilishi kerak. Daraxtlarni kompyuter xotirasida tasvirlanishiga ko‟ra har bir element (binar daraxt tuguni) to‟rtta maydonga ega yozuv shaklida bo‟ladi, ya‟ni kalit maydon, informatsion maydon, ushbu elementni o‟ngida va chapida joylashgan elementlarning xotiradagi adreslari saqlanadigan maydonlar.
Shuni esda tutish lozimki, daraxt hosil qilinayotganda, otaga nisbatan chap tomondagi o‟g‟il qiymati kichik kalitga, o‟ng tomondagi o‟g‟il esa katta qiymatli kalitga ega bo‟ladi. Har safar daraxtga yangi element kelib qo‟shilayotganda u avvalambor daraxt ildizi bilan solishtiriladi. Agar element ildiz kalit qiymatidan kichik bo‟lsa, uning chap shoxiga, aks holda o‟ng shoxiga o‟tiladi. Agar o‟tib ketilgan shoxda tugun mavjud bo‟lsa, ushbu tugun bilan ham solishtirish amalga oshiriladi, aks holda, ya‟ni u shoxda tugun mavjud bo‟lmasa, bu element shu tugunga joylashtiriladi

19. 
    Ko’p o’lchamli daraxtni binar ko’rinishga keltirish.
    

Mazkur funksiyaning vazifasi shundan iboratki, u berilgan kalit bo‟yicha daraxt tuguni qidiruvini amalga oshiradi. Qidiruv operatsiyasining davomiyligi daraxt tuzilishiga bog‟liq bo‟ladi. Haqiqatdan, agar elementlar daraxtga kalit qiymatlari o‟sish (kamayish) tartibida kelib tushgan bo‟lsa, u holda daraxt 4.7-rasmdagidek bir tomonga yo‟nalgan ro‟yhat hosil qiladi (chiqish darajasi bir bo‟ladi, ya‟ni yagona shoxga ega), masalan:

Bu holda daraxtda qidiruv vaqti, bir tomonlama yo‟naltirilgan ro‟yhatdagi kabi bo‟lib, o‟rtacha qarab chiqishlar soni N/2 bo‟ladi. Agar daraxt muvozanatlangan bo‟lsa, u holda qidiruv eng samarali natija beradi. Bu holda qidiruv dan ko‟p bo‟lmagan elementlarni ko‟rib chiqadi.

19. 
    Daraxtlar ustidagi bajariladigan amallar.
    

22. MERGE va SPLIT amallari
23 Graflar nazariyasining asosiy tushunchalar
Graf - bu murakkab chiziqsiz ko’pbog’lamli dinamik tuzilma bo’lib, murakkab obyektlarning xususiyatlari va munosabatlarini aks ettiradi.
Matematik nazariyada va informatikada graf — bu tugunlar(uchlar)dan iborat bo’lgan bo’sh bo’lmagan to’plam va tugunlarni birlashtiruvchi yoylar majmuidir.
Obyektlar tugun yoki graf uzellari ko’rinishida va munosabatlar yoy yoki yo’naltirilgan qirralar kabi ifodalanadi.
Graf turlari
Ixtiyoriy tugundan boshqa bironta tugunga murojaat mavjud bo’lsa, u xolda bunday graf yo’naltirilmagan graf deyiladi (1-rasm).
Agar graf tugunlari o’zaro bog’langan bo’lsa-yu, lekin bu yoylar orqali munosabat faqat bir tomonlama bo’lsa, u xolda bunday graflar yo’naltirilgan graflar deyiladi.

1. 
   Graflarni ifodalash usullari
   
2. 
   Graflarda ko'rik o'tkazish.
   

3. 
   Graflarda eng qisqa yo’lni aniqlash haqida.
   
4. 
   Graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili.
   
5. 
   Floyd – Uorshell algoritmi.
   
6. 
   Ford – Belmann algoritmi.
   

7. 
   Deykstra algoritmi.
   

Deykstra algoritmi

Eng qisqa masofani aniqlash misolini ko’rib chiqaylik. Shahar viloyatlarini birlashtiruvchi avtomobil yo’llari tarmog’I berilgan bo’lsin. Ba’zi yo’llar bir tomonlama. Shahar markazidan har bir viloyatga eng qisqa yo’lni topishimiz zarur.

Keltirilgan masalani yechishda Deykstraning algoritmidan foydalanishimiz mumkin. Algoritm graflarga asoslangan bo’lib, u 1959 yil niderlandiyalik olim E. Deykstra tomonidan yaratilgan. U grafning bitta uchidan boshqa uchlarigacha eng qisqa masofani aniqlaydi, bunda grafning quvurg’alari manfiy og’irlikka ega bo’lmasligi lozim. Bizdan birinchi uchdan qolganlariga borishning qisqa masofasini toppish talab qilinsin.

Doiralar shaklida uchlar, chiziqlar shaklida ular orasidagi yo’l (grafning qovurg’alari) tasvirlangan. Doiralar ichida uchlarning nomerlari, qovurg’alar ostida ularning og’irligi – yo’l uzunligi berilgan. Har bir uchning yonida qizil belgi bilan shu uchga birinchi uchdan eng qisqa masofa uzunligi belgilangan.

Tadbiqi
1–uchning belgisi 0 ga teng deb hisoblanadi, qolgan uchlarning belgilari yetib bo’lmas darajada juda katta sonlardan iborat. Bu 1–uchdan boshqalarigacha bo’lgan masofa hali noma’lumligiki ko’rsatadi. Grafning barcha uchlari ko’rilmagan deb belgilanadi.


Birinchi qadam


Minimal belgiga 1–uch ega. Uning qo’shnilari 2, 3 va 6 uchlar. Uchning qo’shnilarini navbat bilan ko’rib chiqamiz. 1–uchning birinchi qo’shnisi 2–uch, chunki ungacha bo’lgan masofa minimal. 1–uch orqali ungacha bo’lgan masofa 1–uchgacha bo’lgan qisqa masofaning summasiga teng, 1–dan 2–ga boruvchi uning belgisi va qovurg’asi uzunligiga, ya’ni 0+7=7. Bu 2–uchning joriy belgisidan (10000) kichik, shu sababdan ham 2–uchning yangi belgisi 7 ga teng.

Shunga mos ravishda qolgan qo’shnilar (3 va 6 uchlar) uchun ham yo’l uzunligini aniqlaymiz. 1-uchning barcha qo’shnilari ko’rib chiqildi. 1-uchgacha joriy minimal masofa yakuniy hisoblanadi va qayta ko’rib chiqilmaydi. 1-uch ko’rib chiqildi deb belgilanadi.

Ikkinchi qadam

Birinchi qadam takrorlanadi. Ko’rib chiqilmagan uchlardan “yaqini”ni topamiz. Bu 2-uch belgisi 7 ga teng. Yana tanlangan uchning qo’shnilari belgilarini kamaytirishga harakat qilamiz, bunda ularga 2-uch orqali o’tamiz. 2- uchning qo’shnilari 1, 3 va 4 uchlar.

1-uch ko’rib chiqilgan, shu sababdan 3-uch ko’rib chiqilmagan va uchlar ichida minimal belgiga ega. Agar unga 2 orqali borilsa, u holda bu yo’lning uzunligi 17 (7+10=17)ga teng bo’ladi. Ammo 3-uchning joriy belgisi 9 ga teng, ya’ni 9<17, shu sababdan belgi o’zgarishsiz qoladi.


2-ucning yana bir qo’shnisi 4-uch. Agar unga 2-uch orqali borsak, u holda bunday yo’lning uzunligi 22 (7+15=22) ga teng. 22<10000 dan bo’lganligi sabab, 4-uchning belgisini 22 ga tenglaymiz.
2-uchning barcha qo’shnilari ko’rib chiqildi, endi uni ko’rib chiqilgan sifatida belgilaymiz. Uchinchi qadam


3-uchni tanlab algoritmning qadamini takrorlaymiz. Uni “qayta ishlab chiqish”dan so’ng quyidagi natijaga ega bo’lamiz.


To’rtinchi qadam


Beshinchi qadam


Oltinchi qadam
Shu tarzda 1-uchdan 5-uchga eng qisqa masofa 1 – 3 – 6 – 5 uchlari orqali bo’ladi. Shu yo’l orqali biz 20 ga teng minimal og’irlik yig’amiz.

Minimal masofa haqida xulosaga keladigan bo’lsak. Har bir uch uchun yo’l uzunligini bilamiz va endi uchlarni oxirdan ko’rib chiqamiz. Yakuniy uchni ko’rib chiqamiz (bu holatda 5-uch). U bilan bog’langan barcha uchlarni ham ko’rib chiqamiz, yakuniy uch yo’li uzunligidan mos qovurg’aning og’irligini ayirgan holda yo’l uzunligini topamiz. Bizda 5-uch yo’l uzunligi 20. U 6 va 4 uchlar bilan bog’langan. 6- uch uchun 20-9=11 og’irlikka ega bo’lamiz (mos tushdi). 4-uch uchun 20-6=14 og’irlikka ega bo’lamiz (mos tushmadi). Agar natijada biz ko’rilayotgan uchning (joriy holda 6-uch) yo’l uzunligiga mos qiymatga ega bo’lsak, u holda yakuniy uchga o’tish aynan o’sha uchdan amalga oshirilgan bo’ladi. Bu uchni qidirilayotgan yo’lda belgilan qo’yamiz.

6-uchga qaysi qovurg’a orqali kelganimizni aniqlaymiz. Va shu holda toki boshiga chiqmagunimizcha davom qildiramiz.

Agar bunday kuzatish natijasida bizda qaysidir qadamda bir nechta uchlar uchun bu qiymat mos tushsa, u holda ulardan ixtiyoriy birini olish mumkin – bir necha yo’llar bir xil uzunlikka ega bo’ladi.