Mavzu: Qidiruv usullarini tadqiq qilish

O’zbekiston Respublikasi Raqamli Texnologiyalar Vazirligi

Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

Tizimli va amaliy dasturlashtirish kafedrasi

Ma’lumotlar tuzilmasi va algoritmlar fanidan

2-laboratoriya ishi

Mavzu: Qidiruv usullarini tadqiq qilish.

Bajardi: 028-21-guruh talabasi
Mo’minov Ma’mur
Tekshirdi: Kafedra assistenti
Buriyev Yusuf

19-variant

Masala sharti: Boshiga qo‘yish usulidan foydalanib ro‘yhatda kerakli elementdan keyingi elementlarning o‘rtacha kvadratik qiymati 10 dan kichik bo‘lgan elementni toping. Agar bunday elementlar ko‘p bo‘lsa, u holda ularning eng kattasini toping; agar bunday element mavjud bo‘lmasa – shunga mos ma’lumot chiqaring.

Topilgan element 5.2-rasmdagidek birdaniga ro‘yhat boshiga joylashtiriladi. Tuzilmadan har safar birorta element izlab topilsa va u ro‘yhat boshiga olib borib qo‘yilaversa, natijada oxirgi izlangan elementlar ro‘yhat boshiga joylashib qoladi va biz oxirgi vaqtlarda izlangan elementlarni tez izlab topish imkoniga ega bo‘lamiz.

Dastur kodi:
#include
#include
#include

int findNextElement(const std::vector& nums) {

int result = -1;
for (int i = 0; i < nums.size() - 1; i++) {
int average = (nums[i] + nums[i + 1]) / 2;
if (std::sqrt(average) < 10) {
result = std::max(result, average);
}
}
return result;
}

int main() {

std::vector numbers = {3, 12, 5, 20, 8, 14, 15};
int nextElement = findNextElement(numbers);
if (nextElement != -1) {
std::cout << "Eng katta element: " << nextElement << std::endl;
} else {
std::cout << "Bunday element topilmadi" << std::endl;
}
return 0;
}

Nazariy ma’lumot: C++ dasturlash tilida, qidiruv usullaridan eng oddiy va keng qo'llaniladiganlari quyidagilardir:

1. Linearni qidirish: Linearni qidirish usuli, bir ro'yxatni boshidan oxiriga tekshirib boradi va izlangan elementni topadigan bir qidiruv usulidir. Quyidagi funksiya ushbu usulni ishlatadi:

````cpp
int linearSearch(const std::vector& nums, int target) {

for (int i = 0; i < nums.size(); i++) {
if (nums[i] == target) {
return i; // Element indeksini qaytaradi
}
}
return -1; // Element topilmadi
}
```

Ushbu funksiya berilgan `nums` ro'yxatda `target` qiymatini qidiradi. Agar `target` qiymati ro'yxatda topilsa, funksiya indeksini qaytaradi; aks holda `-1` qiymatini qaytaradi.

2. Binarni qidirish: Binarni qidirish usuli, ro'yxatning tartiblangan holatda bo'lishi kerak. Ushbu usul yomonxonlik sifatida elementlarni yarim stadialar orqali qidirib boradi. Binarni qidirish usulidan foydalanishdan oldin ro'yxatni tartiblash kerak. Quyidagi funksiya binarni qidirish usulini ishlatadi:

````cpp
int binarySearch(const std::vector& nums, int target) {

int left = 0;
int right = nums.size() - 1;

while (left <= right) {

int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid; // Element indeksini qaytaradi
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Element topilmadi
}
```

Ushbu funksiya berilgan tartiblangan `nums` ro'yxatda `target` qiymatini binarni qidirish usuli bilan qidiradi. Agar `target` qiymati ro'yxatda topilsa, funksiya indeksini qaytaradi; aks holda `-1` qiymatini qaytaradi.

3. Boshqa usullar: C++ da qidiruv usullari juda ko'p mavjud va ulardan birini foydalanish mumkin. Boshqa usullar misol uchun Hash qidiruv, Interpolatsiya qidiruv, AVL Tree, BST (Binary Search Tree) kabi usullar bo'lishi mumkin. Usul tanlashda qidirishning kerak bo'lgan ro'yxatning xususiyatlariga, kengligiga, tartiblanganligiga va boshqa faktorlarga e'tibor berilishi kerak.

Qidiruv usulini tanlashda, ro'yxatning xususiyatlarini va amaldagi kerakli natijani hisobga oladigan vaqtni hisobga olish muhimdir. Masalan, agar ro'yxat kichik bo'lsa va tartiblangan bo'lmasa, linearni qidirish usuli yaxshi natijaga olib kelishi mumkin. Lekin agar ro'yxat katta bo'lsa va tartiblangan bo'lsa, binarni qidirish usuli yaxshi natijaga olib kelishi mumkin.

Xulosa: Xulosa qilib shuni aytish mumkinki, bu laboratoriya ishini bajarish natijasida C++ dasturlash tilida qidiruv usullari haqida ma’lumotga ega bo’ldim va qidiruv usullaridan boshiga qo’yish usulini amalda bajardim.