|
2-bosqich 731-23 guruh talabasining “MA’lumotlar tuzilmasi va algoritmlar” fanidan tayyorlagan mustaqil ishi bajardi: Nasridinov M
|
| bet | 2/8 | | Sana | 07.10.2024 | | Hajmi | 0,63 Mb. | | #273963 |
Bog'liq Raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi t Chiziqli (Ketma-ket) qidiruv.
Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz yoki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda ma’lumotlar butun jadval bo’yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma-ket qarab chiqiladi.
Massivda ketma-ket qidiruv (search o’zgaruvchi topilgan element raqamini saqlaydi).
C++ tilida dastur quyidagicha bo’ladi: #include
#include
int search(int a[], int N, int key)
{
int i=0;
while (i!=N)
if (a[i]==key) return i; else i++;
return -1;
}
main ()
{
int i, N, mas[1000], key, P;
cout<<”Masiv uzunligini kiriting!”<>N;
cout<<”Massiv elementlarini kiriting!”<cin>>mas[i];
cout<<”Qidiruv elementini kiriting!”<>key;
P=search(mas,N,key);
if (P==-1) cout<<”Bunday element massivda yoq”; else cout<<”Bunday element bor”<
getch(); return 0;
}
Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. Mmin = 1, Mmax = n. Agar ma’lumotlar massiv yacheykasida bir hil extimollik bilan taqsimlangan bo’lsa, u holda Msr (n + 1)/2 bo’ladi.
Agar kerakli element jadvalda bo’lmasa va mazkur elementni jadvalga qo’shish lozim bo’lsa, u holda yuqoridagi dasturdagi oxirgi ikkita operator quyidagiga almashtiriladi.
Paskalda
n:=n+1;
k[n]:=key;
r[n]:=rec; search:=n; exit;
Binar qidiruv (teng ikkiga bo’lish usuli).
Faraz qilaylik, o’sish tartibida tartiblangan sonlar massivi berilgan bo’lsin. Ushbu usulni asosiy g’oyasi shundan iboratki, tasodifiy qandaydir AM element olinadi va u X qidiruv argumenti bilan taqqoslanadi. AgarAM=X bo’lsa, u holda qidiruv yakunlanadi; agar AM M >X bo’lsa.
M ixtiyoriy tanlanganda ham taklif qilinayotgan algoritm korrekt ishlaydi. Shu sababali M ni shunday tanlash lozimki, tadqiq qilinayotgan algoritm samaraliroq natija bersin, ya’ni uni shunday tanlaylikki, iloji boricha kelgusi jarayonlarda ishtirok etuvchi elementlar soni kam bo’lsin. Agar biz o’rtacha elementni, ya’ni massiv o’rtasini tanlasak yechim mukammal bo’ladi.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
2-bosqich 731-23 guruh talabasining “MA’lumotlar tuzilmasi va algoritmlar” fanidan tayyorlagan mustaqil ishi bajardi: Nasridinov M
|
