1-Laboratoriya ishi. Mavzu: Chiziqli qidiruv Ishdan maqsad


Download 440.98 Kb.
Sana04.08.2022
Hajmi440.98 Kb.
#790740
Bog'liq
1-lab
5-вариа, Rasulov atom-molekulyar ta\'limot, озбетинше (3), 2 5192873004282943731, ORALIQ NAZORAT (2), F - TEST, T - TEST uchun jadval qiymatlar, ДИПЛОМ, Якуний саволлар, Mikroiqtisodiyot mustaqil ish, проект Современный компьютер, 1111111111, 2 Ич кетар касаллиги

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.


6-topshiriq
Bir o’lchamli sonli massiv berilgan. Sizning vazifangiz uning elementlari 
Orasida nechtasi massivning barcha elementiga qoldiqsiz bo’lishini topish.
Kiruvchi ma’lumotlar
Birinchi qatorda bitta butun son n – massiv elementlari soni berilgan(1≤n≤105).Ikkinchi qatorda n ta butun son – massiv elementlari bitta probel bilan ajratib berilgan. Massiv elementlari qiymatlari 1 dan 109 gacha bo’lishi mumkin.
Chiquvchi ma’lumotlar
Massivdagi uning barcha elementlariga qoldiqsiz bo’linadigan elementlar soninichiqaring.
Misollar



Kiruvchi ma’lumotlar

Chiquvchi ma’lumotlar

1

4
1 3 6 2

1

2

5
1 1 1 1 1

5

3

2
5 2

0

Izoh: 1-misolda 6 soni massivning barcha elementiga qoldiqsiz bo’linadi.
Bir o’lchamli sonli massiv berilgan. Sizning vazifangiz uning elementlari 
Orasida nechtasi massivning barcha elementiga qoldiqsiz bo’lishini topish.







Download 440.98 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2022
ma'muriyatiga murojaat qiling