|
Malumotlar tuzilmasi va algoritmlar fanidan Amaliy ish 2 Bajardi: Shoxrux Toshkent 2023
|
| Sana | 17.12.2023 | | Hajmi | 499,06 Kb. | | #121641 |
Bog'liq Shoxrux Mta 2 amaliy
O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
malumotlar tuzilmasi va algoritmlar fanidan
Amaliy ish 2
Bajardi: Shoxrux
Toshkent 2023
TOPSHIRIQ:
|
Butun sonlar to'plami va qidirish uchun ikkita kalit berilgan. Ma'lumotlar to'plamidan kalitlarni qidirish bosqichlarini uchta qidiruv (chiziqli, ikkilik va blokli) algoritmlari yordamida tasvirlab bering. Algoritmlarning samaradorligi jadvalini tuzing va berilgan ma'lumotlar bo'yicha samarali algoritm haqida xulosa chiqaring.
|
8.
|
02, 08, 13, 13, 21, 37, 44, 54, 60, 64, 74, 88
|
37 va 74
|
#include
#include
#include
// Chiziqli qidiruv algoritmi
int linearSearch(const std::vector& arr, int key) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == key) {
return i; // Kalit topildi
}
}
return -1; // Kalit topilmadi
}
// Ikkilik qidiruv algoritmi
int binarySearch(const std::vector& arr, int key) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
return mid; // Kalit topildi
}
if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Kalit topilmadi
}
// Blokli qidiruv algoritmi
int blockSearch(const std::vector& arr, int key, int blockSize) {
int n = arr.size();
int blockIndex = -1;
// Bloklar ustida chiziqli qidiruv
for (int i = 0; i < n; i += blockSize) {
if (arr[i] <= key && key <= arr[i + blockSize - 1]) {
blockIndex = i;
break;
}
}
// Blok ichida chiziqli qidiruv
if (blockIndex != -1) {
for (int i = blockIndex; i < std::min(blockIndex + blockSize, n); i++) {
if (arr[i] == key) {
return i; // Kalit topildi
}
}
}
return -1; // Kalit topilmadi
}
int main() {
std::vector arr = {02, 08, 13, 13, 21, 37, 44, 54, 60, 64, 74, 88 };
int key1 = 37;
int key2 = 74;
// Chiziqli qidiruv
int linearResult = linearSearch(arr, key1);
if (linearResult != -1) {
std::cout << "Chiziqli qidiruv: Kalit " << key1 << " topildi." << std::endl;
} else {
std::cout << "Chiziqli qidiruv: Kalit " << key1 << " topilmadi." << std::endl;
}
// Ikkilik qidiruv
std::sort(arr.begin(), arr.end()); // Ikkilik qidiruv uchun massiv saralangan holatda bo'lishi kerak
int binaryResult = binarySearch(arr, key1);
if (binaryResult != -1) {
std::cout << "Ikkilik qidiruv: Kalit " << key1 << " topildi." << std::endl;
} else {
std::cout << "Ikkilik qidiruv: Kalit " << key1 << " topilmadi." << std::endl;
}
// Blokli qidiruv
int blockSize = 3;
int blockResult = blockSearch(arr, key1, blockSize);
if (blockResult != -1) {
std::cout << "Blokli qidiruv: Kalit " << key1 << " topildi." << std::endl;
} else {
std::cout << "Blokli qidiruv: Kalit " << key1 << " topilmadi." << std::endl;
}
// Kalit 2 uchun qidirish
linearResult = linearSearch(arr, key2);
if (linearResult != -1) {
std::cout << "Chiziqli qidiruv: Kalit " << key2 << " topildi." << std::endl;
} else {
std::cout << "Chiziqli qidiruv: Kalit " << key2 << " topilmadi." << std::endl;
}
binaryResult = binarySearch(arr, key2);
if (binaryResult != -1) {
std::cout << "Ikkilik qidiruv: Kalit " << key2 << " topildi." << std::endl;
} else {
std::cout << "Ikkilik qidiruv: Kalit " << key2 << " topilmadi." << std::endl;
}
blockResult = blockSearch(arr, key2, blockSize);
if (blockResult != -1) {
std::cout << "Blokli qidiruv: Kalit " << key2 << " topildi." << std::endl;
} else {
std::cout << "Blokli qidiruv: Kalit " << key2 << " topilmadi." << std::endl;
}
return 0;
}
|
| |
