Qidiruv algoritmlari - Информатика и ИТ - Рефераты

Информация о документе

Цена	2000UZS
Размер	177.8KB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Рефераты
Предмет	Информатика и ИТ

Qidiruv algoritmlari

Купить

O‘ZBEKISTON RESPUBLIKASI OLIY TA’LIM, FAN VA
INNOVATSIYALAR VAZIRLIGI
SHAROF RASHIDOV NOMIDAGI
SAMARQAND DAVLAT UNIVERSITETI
INTELLEKTUAL TIZIMLAR VA KOMPYUTER
TEXNOLOGIYALARI FAKULTETI
3-MUSTAQIL ISH
Bajardi:

Qidiruv algoritmlari
Kirish
Qidiruv algoritmlari kompyuter fanlarida eng muhim mavzulardan biridir. Bu algoritmlar
ma'lumotlar tuzilmalarida yoki graf shaklidagi tuzilmalar ichida ma'lum bir elementni yoki
ma'lumotni izlash uchun qo'llaniladi. Ular turli muammolarni hal qilishda, jumladan yo'lni
topish, tartiblash va ma'lumotni qayta ishlashda muhim rol o'ynaydi.
1. Qidiruv algoritmlari haqida umumiy ma'lumot
Qidiruv algoritmlari asosan ikki asosiy toifaga bo'linadi:
- **Chiziqli qidiruv**: Ma'lumotlar ro'yxatini boshidan oxirigacha ketma-ket qidirish algoritmi.
- **Ikkilik qidiruv**: Tartiblangan ro'yxatlarda tezkor qidiruv uchun qo'llaniladi. Bu algoritm
ma'lumotlarni teng ikki qismga bo'lish tamoyiliga asoslanadi.
Qidiruv algoritmlari nafaqat ro'yxatlarda, balki graf kabi murakkab tuzilmalarda ham ishlaydi.
Masalan, DFS (Depth First Search) va BFS (Breadth First Search) kabi graf qidiruv algoritmlari.
2. Chiziqli qidiruv
Chiziqli qidiruv algoritmi sodda va intuitiv algoritmdir. Unda ro'yxatdagi har bir element
birma-bir tekshiriladi. Agar qidirilayotgan element topilsa, uning indeksi qaytariladi; aks
holda, algoritm davom etadi. Uning murakkablik darajasi O(n) ga teng.
C++da chiziqli qidiruv
#include <iostream>
using namespace std;
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;

}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int result = linearSearch(arr, size, target);
if (result != -1) {
cout << "Element topildi. Indeks: " << result << endl;
} else {
cout << "Element topilmadi." << endl;
}
return 0;
}
3. Ikkilik qidiruv
Ikkilik qidiruv algoritmi tartiblangan ro'yxatlar uchun samarali qidiruv algoritmidir. U
ro'yxatni teng ikki qismga ajratadi va qidirilayotgan element qaysi qismda ekanligini aniqlab,
faqat o'sha qismni tekshiradi. Bu jarayon rekursiv ravishda yoki iterativ usulda amalga
oshiriladi. Murakkablik darajasi O(log n) ga teng.
C++da ikkilik qidiruv
#include <iostream>
using namespace std;
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {

left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int result = binarySearch(arr, size, target);
if (result != -1) {
cout << "Element topildi. Indeks: " << result << endl;
} else {
cout << "Element topilmadi." << endl;
}
return 0;
}
4. Graf qidiruv algoritmlari
Graf qidiruv algoritmlari graf yoki daraxt kabi ma'lumotlar tuzilmalarida ishlatiladi. DFS
(Depth First Search) va BFS (Breadth First Search) algoritmlari eng mashhur graf qidiruv
usullaridir.
- **DFS**: Grafni chuqurlik bo'yicha qidiradi va rekursiya yordamida amalga oshiriladi.
- **BFS**: Grafni kenglik bo'yicha qidiradi va navbat ma'lumotlar tuzilmasidan foydalanadi.
C++da DFS
#include <iostream>
#include <vector>
using namespace std;

void DFS(int node, vector<bool>& visited, const vector<vector<int>>& graph) {
visited[node] = true;
cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
DFS(neighbor, visited, graph);
}
}
}
int main() {
int n = 5;
vector<vector<int>> graph = {
{1, 2}, {0, 3, 4}, {0, 4}, {1}, {1, 2}
};
vector<bool> visited(n, false);
cout << "DFS tartibi: ";
DFS(0, visited, graph);
cout << endl;
return 0;
}
Xulosa
Qidiruv algoritmlari turli ma'lumotlar tuzilmalarida samarali izlash imkonini beradi. Chiziqli
va ikkilik qidiruv algoritmlari oddiy ro'yxatlar uchun mo'ljallangan bo'lsa, DFS va BFS
algoritmlari graf tuzilmalarida qo'llaniladi. Har bir algoritmning o'ziga xos kuchli va zaif
tomonlari mavjud.
Foydalanilgan manbalar
1. "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.
2. GeeksforGeeks - Search Algorithms.
3. Programiz - Binary Search and Linear Search.

Qidiruv algoritmlari

Купить

Похожие документы
3d-max dasturida obektlarni yaratish
Algoritm va ma’lumotlar strukturasi
3D-MAX dasturi haqida
3D Studio MAX dasturiga kirish. 3D Studio MAX dasturi haqida tushuncha
Adobe photoshop dasturida tasvirlarda ishlov berish,taqdimot yaratish