Kombinatsiyalar. Rekurrent munosabatlar



Download 0,6 Mb.
Sana17.07.2022
Hajmi0,6 Mb.
#811750
Bog'liq
KOMBINATSIYALAR. REKURRENT MUNOSABATLAR

KOMBINATSIYALAR. REKURRENT MUNOSABATLAR

Yusupov Ozod


Algoritm murakkabligi uchun rekkurent munosabatlar algoritm ko‘rinishidan chiqariladi, lekin ular yordamida bu murakkablikni darhol hal etish oson emas. Buning uchun rekkurent munosabatni rekkurent tabiatidan voz kechuvchi yopiq ko‘rinishga keltirish kerak. Bu usulni tushunish uchun bir qator misollar ko‘rib chiqamiz.
Rekurrent munosabat ikki ko‘rinishda berilishi mumkin. Birinchisi sodda holatlar kam bo‘lganda:
T(p) = 2T(n-2) - 15;
T(2) = 40;
T(1) = 40.
Ikkinchi shakli sodda holatlar miqdori nisbatan ko‘proq bo‘lgan holda ishlatiladi:
T(p) = T(p) = 4T(n/2) - 1;
T(4) = 4;
T(3) = 4;
T(2) = 4;
T(1) = 4;
Bu shakllar ekvivalent. Oddiy qiymatlar ro‘yxatini chiqarib tashlab, ikkinchisidan birinchisiga o‘tish mumkin. Bundan kelib chiqadiki, yuqorida keltirilgan rekkurent munosabatlardan ikkinchisini quyidagi ko‘rinishda yozish mumkin:
Quyidagi rekkurent munosabatni ko‘rib chiqamiz:
T(p) = 2T(n-2)-15;
T(2) = 40;
T(1) = 40.
T(p-4) = 2T(n-6)-15;
T(p-6) = 2T(p-8)-15;
T(p-8) = 2T(n-10)-15;
T(p - 10) = 2T(n - 12) - 15.
T(p) = 32T(n-10)-16•15-8•15-4•15-2•15-15;
T(p)= 32(2T(n-12)-15)-16•15-8•15-4•15-2•15-15,
T(p) = 64T(n-12)-32•15-16•15-8•15-4•15-2•15-15.
Balki siz umumiy sxemani tushunib etgandirsiz. Avvalambor, har bir tenglikdagi qo‘shiluvchi ikkining navbatdagi darajasiga ko‘paytirilgan -15 ni ko‘rsatib turibdi. Ikkinchidan, koeffitsient T funksiyani rekursiv chaqiruvda ikkining darajasi bo‘lib hisoblanadi. Bundan tashqari, T funksiya argumenti har safar 2 taga kamayib bormoqda.
Agar p toq son bo‘lsachi? Bu formulalar ilgarigidek ishlaydimi? p=13 bo‘lganda ko‘rib chiqamiz. Tenglikda bitta o‘zgarish sodir bo‘ladi —T funksiya argumenti 2 emas 1 bo‘ladi, lekin n/2-1 qiymati 5 ga teng bo‘ladi (6 ga emas). Toq n da n/2-1 o‘rniga n/2 ni olamiz. Javobda ikki holatni ko‘rib chiqishimiz kerak.
juft n da;
toq p da.
Endi, juft n soni uchun (7.17) tenglikni qo‘llab, quyidagiga ega bo‘lamiz
T(p) = 2(p-2)-1•40-15•(2n/2-1)
= 2n/220-2n/2•30+15
= 2n/2 (20-15)+15
= 2 n/2 •5+15,
toq p da
T(p) = 2 n/2•40-15•(2n/2-1)
= 2 n/2•40-2 n/2 •30+15
= 2 n/2(40-30)+15
= 2 n/2 •10+15.
Ko‘rinib turibdiki, chto pri -1da koeffitsient har bir almashtirishda biror to‘rt darajaga oshadi, argumentga bo‘layotgan ikkilik darajasi -1da eng katta to‘rt darajadan har safar 1ga ko‘p bo‘ladi. Bundan tashqari, T da koeffitsientdagi to‘rtning darajasi biz argumentni bo‘layotgan ikkining darajasi kabi T(n/2i) da bu koeffitsient 4g ga teng, keyin esa -4i-1 dan -1gacha bo‘lgan qo‘shiluvchilar keladi. i ning qanday qiymatida almashtirishlar to‘xtatilishi kerak? Qiymatlar p≤4 da berilganligi uchun, T(4) = T(n/21og2n-2) ga etib kelganda to‘xtashi mumkin.
Biz birinchi tenglikni T(p-2) uchun ekvivalent ifodaga keltirmoqchimiz. Buning uchun undagi hamma n ni p – 2 bilan almashtiramiz:
T(p- 2) = 2T(n - 2 - 2) - 15 = 2T(n-4)-15.
Endi, T(n-4) qiymatini chiqarib tashlashimiz kerak. Xuddi shunday biz mos o‘rin almashtirishlarni bajarishimiz kerak. Buni katta bo‘lmagan ketma-ket qiymatlar uchun bajaramiz:
T(n-2) = 2T(n-4) - 15;
T(p-4) = 2T(n-6) - 15;
T(n-6) = 2T(n-8) - 15;
T(n-8) = 2T(n-10) - 15;
T(n-10) = 2T(n-12) - 15.
Birinchi navbatda, har bir tengsizlikdagi oxiridan boshlab qo‘shiluvchilar o‘zida ikkining navbatdagi darajalariga ko‘paygan -15 sonidan iborat. Ikkinchidan, sezish mumkinki, T funksiya rekursiv chaqilishidagi koefitsient ikkining darajalaridir. Bundan tashqari, T funksiya argumenti har safar 2 ga kamayadi. Bu jarayon qachon tugaydi deb so‘rashimiz mumkin. boshlang‘ich tenglikka qaytib eslaymizki, biz T(1) va T(2) lar qiymatini qayd qilgandik. Bu o‘lchovlarga etib borish uchun nechta almashtirishlar bajarishimiz kerak? p juft bo‘lgan holda 2 = n - (n- 2) ga egamiz. Bu shuni bildiradiki, biz (n - 2)/2 - 1 o‘rin almashtirish bajarishimiz kerak, qaysiki ular —15 ko‘paytmali p/2-1 qo‘shiluvchilar va T oldidan n/2 — 1 ikki darajalarini beradi. n = 14 da nima bo‘lishini tekshiramiz. Bu holda, yuqlridagi gapga ko‘ra biz besh almashtirish bajarishimiz kerak; —15 ko‘paytmali oltita qo‘shiluvchiga ega bo‘lamiz va T(2) da koefitsient 26 ga teng. Xuddi shunday natija n = 14 da oxirgi tenglik orqali olinadi.
Download 0,6 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