Amaliy mashg’ulot- 2 Mavzu: Qidiruv algoritmlari: chiziqli va binary qidiruv. Xesh funksiyalar va xesh algoritmlarini tuzish

AMALIY MASHG’ULOT- 2
Mavzu: Qidiruv algoritmlari: chiziqli va binary qidiruv. Xesh funksiyalar va xesh algoritmlarini tuzish.


Ishdan maqsad: Ushbu laboratoriya ishining maqsadi talabalar qanday qidirish usullari va algoritmlari mavjudligini va ularning samaradorliklarini baholashni o’rganishlari kerak. Shu asosda qidirish usullarini qiyosiy tahlil qilishlari, C++ dasturlash tilida qidirish bilan islashni va ularga oid dasturlar tuzishni o’zlashtirishlari kerak.
Qo’yilgan masala: Talabalar topshiriq variantiga mos qidirish usuli yordamida masalani yechish dasturini yaratish ko’nikmasiga ega bo’lishlari kerak.
Ish tartibi:
1.Tajriba ishi nazariy ma’lumotlarini o’rganish;
2.Berilgan topshiriqning algoritmini ishlab chiqish;
3. C++ dasturlash muhitida dasturni yaratish;
4. Natijalarni tekshirish;
5.Hisobotni tayyorlash va topshirish.



Aytaylik bizga massiv berilgan:
a[]={15, 23, 7, 45, 87, 16};
Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan dastur tuzish sharti qo'yilgan. Ushbu masalani yechishda eng birinchi xayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
Chiziqli qidiruv - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:
#include
usingnamespace std;
int linearSearch(int array[], int size, int searchValue)
{
for(int i =0; i < size; i++)
{
if(searchValue == array[i])
{
return i;
}
}
return-1;
}
int main()
{
int a[]={15, 23, 7, 45, 87, 16};
int userValue;
cout<<"Enter an integer: "<< endl;
cin>> userValue;
int result = linearSearch(a, 6, userValue);
if(result >=0)
{
cout<<"The number "<< a[result]<<" was found at the"
" element with index "<< result << endl;
}
else
{
cout<<"The number "<< userValue <<" was not found. "<< endl;
}
}

Ko'rib turganingizdek, funksiyamiz 2 ta parametr qabul qiladi, birinchisi massivni o'zi, ikkinchisi esa biz qidirayotgan element. Agar uni topa olmasak, "-1" qiymatni qaytaramiz.

Endi bundan optimal bo'lgan usul - binar(ikkilik) qidiruvni ko'rib chiqsak. Bu usulda ham funksiyaga 2 ta parametr, birinchisi massiv o'zi keyin esa biz qidirayotgan elementni parametr sifatida beriladi. Qidiruv esa quyidagicha: Dastlab biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz, mening kodimda bu left va right o'zgaruvchilaridir:
left := 0 right := len(a)
so'ngra quyidagi shart bajarilgan holda
left< right
quyidagi ketma-ket operatsiyalarni amalga oshiramiz

1. 
   left va right index lari markazidagi elementni topamiz (left + right) / 2
   
2. 
   topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
   
3. 
   agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi.
   
4. 
   agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right = mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom etadi.
   

Shu zaylda qidiruv left < right shart bajarilmagunicha davom etadi, agar bu jarayonda biz qidirgan element topilmasa u xolda -1 javob qaytariladi, quyida dastur kodi keltirilgan:
#include
Using namespace std;
int binarySearch(int array[], int size, int searchValue)
{
int low =0;
int high = size -1;
int mid;
while(low <= high)
{
mid =(low + high)/2;
if(searchValue == array[mid])
{
return mid;
}
elseif(searchValue > array[mid])
{
low = mid +1;
}
else
{
high = mid -1;
}
}
return-1;
}
int main()
{
int a[]={12, 22, 34, 47, 55, 67, 82, 98};
int userValue;
cout<<"Enter an integer: "<< endl;
cin>> userValue;
int result = binarySearch(a, 8, userValue);
if(result >=0)
{
cout<<"The number "<< a[result]<<" was found at the"
" element with index "<< result << endl;
}
else
{
cout<<"The number "<< userValue <<" was not found. "<< endl;
}
}

Bu usul binar qidiruvni iterativ usuli deyiladi, shuningdek bu algoritmni rekursiya usulida ham yozish mumkin, rekursiv usulni erinmasangiz o'zingiz yozib ko'ring. Bitta urinishda ko'pchilik dasturchilar bu narsani to'g'ri yoza olishmaydi va bu normal holat, chunki xato bor joyda o'z ustida ishlash uchun imkoniyat bo'ladi.

Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz:

1. 
   funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q
   
2. 
   chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n)
   

"Xesh" so'zi ingliz tilidagi «hash» so’zidan olingan bo’lib, uning ma'nosi “shovqin” yoki “aralash” kabi ta'riflanadi. Aslida, bular atamaning haqiqiy ma'nosini to'liq ifodalaydi.
1. Xesh jadvalni tashkil etish: asosiy tushunchalar
• Xeshlash – bu ma'lum bir turdagi va ixtiyoriy uzunlikdagi kirish ma'lumotlari massivini fiksirlangan uzunlikdagi chiquvchi bitlar qatoriga (butun son) aylantirish. Bunday akslantirish (aylantirish) xesh-funksiya deb ham ataladi. Xesh-funksiya – bu kirish ma’lumotlarini sonlarga aylantiruvchi funksiya bo’lib, bir xil ma’lumotlar to’plami hamma vaqt bir xil natija beradi.
•Xesh-jadval – bu elementlari “kalit-qiymat” juftliklari bo'lgan assotsiativ massiv shaklidagi ma'lumotlar tuzilmasi.

• Xeshlash assotsiativ massivlarni tashkil qilish uchun qo’llaniladi, bunda indekslari sonlar emas, balki ixtiyoriy qiymatlar bo’ladi. Xeshlashdan odatda matnlardan nusxalarning takrorlanishini qidirishda, ya'ni xesh-funksiyalarining bir xil qiymatiga ega bo'laklarni qidirishda foydalaniladi. Bundan tashqari, xeshlash ko'pincha parollarni saqlash uchun ishlatiladi; shu bilan birgalikda noyob identifikatorlarni yaratish uchun, masalan, agar fayl o'ziga xos nomni talab qilsa, siz ushbu faylni xeshlash natijasini hisoblab chiqishingiz va natijani faylga nom sifatida ishlatishingiz mumkin. Shuningdek, bu matnlarning nazorat summasini hisoblash uchun juda muhimdir. Aytaylik, foydalanuvchi tarmoq orqali bir nechta matn yuborishi kerak. Tekshirish summasi matn bilan birga uzatiladi, olinganidan keyin asl nusxasi bilan tekshiriladi. Agar summasi mos kelmasa, demak matnni uzatishda qandaydir xatolik bo’lganligi haqida xulosa qilish mumkin bo’ladi.
TOPSHIRIQ