Mediana va uni hisoblash algoritmi Bajardi: Javxanov Dilshod


K sonlarning S to'plami uchun x ning ma'nosi “rank" bo'lsin, x S dagi eng kichik sondir



Download 2,25 Mb.
bet3/5
Sana26.06.2022
Hajmi2,25 Mb.
#705392
1   2   3   4   5
Bog'liq
Algoritmqw111

6. K sonlarning S to'plami uchun x ning ma'nosi “rank" bo'lsin, x S dagi eng kichik sondir.

7a. Agar i = k bo'lsa, x ni qaytaring.

7b. Agar i

7c. Agar i >k bo'lsa, (A[k+1,…, i ], i-k) bo'yicha median-of−medians algoritmidan foydalanib qaytadan yozing.

 

Imtihon ballari A ro'yxatidagi uchinchi eng past ballni topish uchun median-of-medians algoritmining bosqichlarini ko'rsating.

Izoh: ushbu algoritmning ba'zi tatbiqlari, xuddi quyidagi algoritm kabi, nol indekslangan, ya'ni eng past ball ro'yxatdagi eng past ball bo'ladi. Ushbu misolda nol indekslashdan foydalaning-shuning uchun uchinchi eng past ball bo'ladi tartiblangan ro'yxatda chap element.

A=[25,21,98,100,76,22,43,60,89,87]

Birinchidan, biz ro'yxatni beshta element ro'yxatiga ajratamiz:

=[25,21,98,100,76] va =[22,43,60,89,87]

Keyin, har bir ro'yxatdan medianni oling va ularni M medianlar ro'yxatiga qo'ying,

M=[76,60].

 

Ushbu ro'yxatdan medianani tanlang-chunki ro'yxat uzunligi 2 ga teng va biz median indeksini ro'yxat uzunligi bo'yicha ikkiga bo'linishini aniqlaymiz: biz 2/2=1, median indeksi 1 ga teng va M[1] = 76. Buni burilish elementi sifatida foydalaning va chapga 76 dan kichik va o'ngga 76 dan katta bo'lgan barcha elementlarni AA ga qo'ying:

A’=[25,22,43,60,21,76,100,89,87,98].

76 bo'lgan 5 ning indeksini toping. 5 bilan 3 qanday taqqoslanadi? 5 > 3,5 > 3 bo'lgani uchun [25,22,43,60,21][25,22,43,60,21] bo'lgan a',a' ro'yxatning chap yarmida qaytadan yozishimiz kerak.

Ushbu ro'yxat faqat beshta elementdan iborat, shuning uchun biz uni tartiblashimiz va 3-indeksda nima borligini topishimiz mumkin: [21,22,25,43,60][21,22,25,43,60] va 43 uchinchi indeksda.

Demak, 43-A ning to'rtinchi eng kichik soni.

Endi biz quyidagi massivda uchinchi eng kichigini qidirmoqdamiz:

[3,4,5,6] Biz o'zimizning asosiy omilimiz bo'lish uchun tasodifiy indeksni tanla


Download 2,25 Mb.

Do'stlaringiz bilan baham:

1   2   3   4   5




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