Amaliy mashg’ulot- 3 Mavzu: Saralash usullari va ularning qo‘llanilishi. Saralashning yaxshilangan usullari va ularning qo’llanilishi

int fact(int k)
{
if (k==1)
return 1;
else
return k * fact(k-1);
// 5*fact(4);
// fact(4) = 4* fact(3);
// fact(3) = 3 * fact(2);
// fact(2) = 2 * fact(1);
// fact(1) = 1
}
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 n-Fibonachchi soni (n-1)- va (n-2)-Fibonachchi sonlarining yig’indisiga teng.
- Amaliyotda barcha geometrik fraktallar cheksiz rekursiya orqali beriladi (masalan, Serpin uchburchagi).


TOPSHIRIQ