Guruh: 630-19 Talaba: Abdupattayev Abbosxon Fan: Ma'lumotlar tuzilmasi va algoritmlar

Guruh: 630-19

Talaba: Abdupattayev Abbosxon

Fan: Ma'lumotlar tuzilmasi va algoritmlar
LABORATORIYA ISHI - 8
Mavzu: Rekursiv va Iterativ algoritmlarni ishlatishga misollar

Ishdan maqsad: Ushbu laboratoriya ishining maqsadi talabalar rekursiv funksiyalar mavjudligini va ularning samaradorliklarini baholashni o‘rganishlari kerak. Shu asosda saralash usullarini qiyosiy tahlil qilishlari, C++ dasturlash tilida fayllar bilan ishlashni va ularga oid dasturlar tuzishni o‘zlashtirishlari kerak.

Qo‘yilgan masala: Talabalar topshiriq variantiga mos saralash usuli yordamida masalani yechish dasturini yaratish ko‘nikmasiga ega bo‘lishlari kerak. Ish tartibi:

Tajriba ishi nazariy ma’lumotlarini o‘rganish;

Berilgan topshiriqning algoritmini ishlab chiqish;

C++ dasturlash muhitida dasturni yaratish;

Natijalarni tekshirish;

Hisobotni tayyorlash va topshirish.

Matematikada rekursiya.

Matematikada rekursiya funksiyalar va sonli qatorlarning aniqlanish metodlariga nisbatan qo’llaniladi: rekursiv ravishda berilgan funksiya o'z qiymatini boshqa argumentlar bilan chaqirish orqali aniqlanadi. Bundan holda ikkita variant mavjud:

Tugallangan (sonli) rekursiv funksiyalar. Bunday funksiyalar chekli sondagi rekursiv murojaat (chaqiruv) uchun ixtiyoriy sonli argumentda rekursiyasiz hisoblanadigan alohida aniqlanuvchi xususiy hollardan biriga olib kelish orqali beriladi. Klassik misol: manfiy bo’lmagan butun sonning rekursiv aniqlanishi:

Bu yerda har bir keyingi rekursiv chaqiruvda argument bir birlikka kichiklashadi. Ya’ni, aniqlanishi bo’yicha manfiy bo’lmagan butun sonning faktorialini hisoblovchi funksiya argumenti n ga rekursiv murojaat qilishi 0!=1 xususiy holatga kelganda hisoblashni to’xtatadi. Shunday qilib, rekursiv aniqlanishiga qaramasdan, ixtiyoriy argument uchun bu funksiya aniqlanish sohasida tugallangan funksiya bo’ladi.

Cheksiz rekursiv funksiyalar. Bunday funksiyalar barcha hollarda (hech bo’lmaganda ba’zi argumentlar uchun) o’z-o’ziga murojaat ko’rinishida beriladi. Misol sifatida cheksiz sonli qatorlar, cheksiz davomli kasrlar va boshqalarni olish mumkin. Amaliyotda bunday hollarda aniq qiymatni hisoblashning tabiiyki imkoni yo’q, ya’ni cheksiz vaqt talab etadi. Talab qilingan natijalar analitik usullarda topiladi. Shunga qaramay, agar absolyut aniq qiymatni olish haqida emas, balki kerakli (talab qilingan) qiymatning berilgan yaqinligini hisoblash haqida gapiradigan bo'lsak, unda ba'zi hollarda to'g'ridan-to'g'ri rekursiya ta'rifidan foydalanish mumkin: bunday holda kerakli (talab qilingan) aniqlikka erishmaguncha hisoblash davom ettiriladi. Bu kabi funksiyaga misol sifatida Eyler sonining matematik yoyilmasini olish mumkin:

Bu yerda

Yuqoridagi formuladan foydalangan holda to'g'ridan-to'g'ri hisoblash cheksiz rekursiyani keltirib chiqaradi, lekin n ning o’sib borishi bilan f(n) ning qiymati birga yaqinlashishi (intilishi)ni isbotlash mumkin (shuning uchun qatorning cheksizligiga qaramay, Eyler sonining qiymati chekli bo’ladi). Eyler soni e-ning qiymatini taxminiy hisoblash uchun rekursiya chuqurligini oldindan ma'lum bir songa sun'iy ravishda cheklash va unga erishilganda f(n)-ning qiymatiga birni ta’minlash yetarli bo’ladi.

Matematikada rekursiyaga yana bir misol sifatida rekurrent formula bilan berilgan sonli qatorlarni olish mumkin. Bunday qatorlarning har bir keyingi hadi o’zidan oldingi n ta hadga bog’liq funksiya natijasi bilan aniqlanadi.

Shunday qilib, cheklangan ifoda yordamida cheksiz qator aniqlanishi mumkin (bu ketma-ketlikning birinchi n hadlari uchun takrorlanadigan (rekurrent) formula va qiymatlar to'plamining kombinatsiyasi bo’ladi).

Matematik induksiya rekursiya bilan chambarchas bog'liq: bu natural sonlar bo'yicha o’zining kichik qiymatlari orqali berilgan rekursiv funksiya xususiyatlarini isbotlashning tabiiy usuli hisoblanadi.

Matematikada rekursiyaga misollar:

chiziqli algebraik tenglamalar sistemasini yechish uchun Gaus-Jordan usuli rekursiv hisoblanadi.

manfiy bo’lmagan butun sonning faktorialini hisoblash.

Fibonachchi soni rekurrent munosabat yordamida aniqlanadi, ya’ni Fibonachchi sonining birinchi va ikkinchi hadlari 1 ga teng. n>2 uchun nFibonachchi soni (n-1)- va (n-2)-Fibonachchi sonlarining yig’indisiga teng.

Amaliyotda barcha geometrik fraktallar cheksiz rekursiya orqali beriladi (masalan, Serpin uchburchagi).

primitiv rekursiv bo’lmagan rekursiv hisoblanuvchi funksiyaga standart misol – Akkerman funksiyasi bo’ladi, bu funksiya manfiy bo’lmagan m va n butun sonlar uchun quyidagi ko’rinishda bo’ladi:

Nazorat savollari

Rekursiya nima?

O’zini o’zi qaytaruvchi funksiyalar rekursiv funksiyalar deyiladi

Rekursiya nima maqsadda qo’llaniladi?

Matematik funksiyalarini dasturda osonroq ishlashda yordam beradi.

Recursiya qanday turlarga bo’linadi?

Tugallangan (sonli) rekursiv funksiyalar

Cheksiz rekursiv funksiyalar ga bo’linadi.

Xulosa

. Rekursiv funksiyalar haqida umumiy ma’lumotlarga ega bo’ldim. Ularni qayerda ishlatish kerak ekanligini o’ragandim. Ular necha turga bo’linishini bilib oldim.