Karimov asadbek 1-Laboratoriya ishi. Mavzu: Chiziqli qidiruv Ishdan maqsad



Download 178,88 Kb.
Sana31.12.2021
Hajmi178,88 Kb.
#211298
Bog'liq
1-LAB


921-19 guruh talabasi

KARIMOV ASADBEK

1-Laboratoriya ishi.



Mavzu: Chiziqli qidiruv

Ishdan maqsad. Chiziqli qidiruv algoritmini o’rganish va dasturini yozish.

Nazariy qism.

Dasturlashda eng ko’p qo’llaniladigan amallardan biri bu – ma’lumotlarni qidiruv. Qidiruvning birnechta asosiy variantlari mavjud bo’lib, ular uchun har xil algoritmlar yaratilgan.



Chiziqli qidiruv – ixtiyoriy funksiyaning qandaydir kesmadagi berilgan qiymatini qidirishga aytiladi. Bu algoritm oddiy algoritm hisoblanib, boshqa algoritmlardan, masalan binar qidiruvdan farqli tamoni funsiyaga hecha qanday cheklanish qo’yilmaydi va amalga oshirish oddiy hisoblanadi.

Chiziqli qidiruv algoritmi

Funksiya qiymatini izlash navbatdagi qiymatni (odatda chapdan o’nga argument oshishi tartibida amalga oshiriladi)oddiy taqqoslash orqali tekshiriladi. Masala ikki xil qo’yilishi mumkin: 1) Birinchi topilgan argumentni topish 2) Barcha argumentlarni topish.

Agar funkisya sifatida massiv argument sifatida massiv indeksi qo’llanilsa u holda chiziqli qidiruv natijasida berilgan massivdan bo’lgan shunday i indekslarni topish lozim.

Massiv: 45, 12 , 89, 12, -78, 12;

12 sonining pozitsiyalari 2, 4, 6;

Chiziqli qidiruv.

Oddiy chiziqli qidiruvda massivning har bir elementi bilan birma-bir tekshirib chiqiladiz.

int function LinearSearch (Array A, int L, int R, int Key);

begin


for X = L to R do

if A[X] = Key then

return X

return -1; // элемент не найден

end;

Bunda L va R o’zgruvchilar element qidiriladigan oraliq.



Ishlash vaqti.

Agar massivdagi birinchi uchraydigan indeks izlanayotgan bo’lsa u holda chiziqli qidiruv algoritmining ishlash vaqti:

Eng yaxshi holatda: O(1). Ya’ni izlanayotgan element qaralayotgan intervalning boshida bo’lsa.

Eng yomon holatda: O(n). Ya’ni izlanayotgan element izlanayotgan intervalning oxirida bo’lsa yoki umuman uchramasa.

n – izlanayotgan intervaldagi elementlar soni. Yuqoridagi misol uchun n=R-L+1.

Chiziqli qidiruv algoritmi qidirilayotgan interval uzunligi kichik bo’lgan vaqtdagina effektiv bo’ladi.



Amaliy qism.

Berilgan qiymatning berilgan massivdagi uchrashlari sonini qaytaruvchi funksiya yarating va undan foydalaning..

Misollar:



Input

Output

1

8

-8 9 -8 5 6 78 -8 8

-8


3


2

4

1 2 3 4


5

0



Yechimi.

#include

using namespace std;

int cnt_accureces(int x, int a[], int n) {

int res = 0;

for (int i = 0; i < n; i++) {

if (a[i]==x)

res++;


}

return res;

}

int main() {



int n;

cin >> n;

int a[n];

for (int i = 0; i < n; i++) {

cin >> a[i];

}

int x;



cin >> x;

cout << cnt_accureces(x, a, n) << endl;

}



Topshiriqlar

11-topshiriq

Vasiliy sportchi xokkeybolda qatnashdi va yakka tartibda kumush medalni qo'lga kiritdi. Ma'lumki, bir xil miqdordagi ball to'plagan ishtirokchilarga bir xil mukofotlar beriladi. Shuningdek, ular oltin, kumush va bronza medallari bilan yutqazilganligini bilamiz. Muammoda xokkeybola qoidalari so'ralmagan. Vasiliy qancha ochko to'planganligini aniqlashingiz kerak.

Kiritish

Birinchi qatorda musobaqalarda qatnashadigan n (2 ≤ n-1000) sportchilar soni ko'rsatilgan. Ikkinchi qatorda n tamsayılar berilgan - raqobat natijalari. Raqamlar 1 dan 109 gacha.

Chiqish

Bitta raqamni chop eting - Vasiliyning natijasi.

Namunalar





Input

Output

1

5

4 3 3 1 2



3

2

8

1 2 5 3 5 6 6 5



5


Download 178,88 Kb.

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