thuật toán tìm kiếm tuyến tính

/*thuật toán tìm kiếm tuyến tính
Cho danh sách có n phần tử a0, a1, a2…, an-1.
Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách các phần tử nói trên trong bộ nhớ chính.
Tìm phần tử có khoá bằng X trong mảng
Giải thuật tìm kiếm tuyến tính (tìm tuần tự)
Giải thuật tìm kiếm nhị phân
Lưu ý: Trong quá trình trình bày thuật giải ta dùng ngôn ngữ lập trình C.
Ý tưởng : So sánh X lần lượt với phần tử thứ 1, thứ 2,…của mảng a cho đến khi gặp được khóa cần tìm, hoặc tìm hết mảng mà không thấy.
Các bước tiến hành
Bước 1: Khởi gán i=0;
Bước 2: So sánh a[i] với giá trị x cần tìm, có 2 khả năng
+ a[i] == x tìm thấy x. Dừng;
+ a[i] != x sang bước 3;
Bước 3: i=i+1 // Xét tiếp phần tử kế tiếp trong mảng
Nếu i==N: Hết mảng. Dừng;
Ngược lại: Lặp lại bước 2;
Hàm trả về 1 nếu tìm thấy, ngược lại trả về 0:
int LinearSearch(int a[],int n, int x)
{
int i=0;
while((i<n)&&(a[i]!=x))
i++;
if(i==n)
return 0; //Tìm không thấy x
else
return 1; //Tìm thấy
}Nhận xét: Số phép so sánh của thuật toán trong trường hợp xấu nhất là 2*n.
Để giảm thiểu số phép so sánh trong vòng lặp cho thuật toán, ta thêm phần tử “lính canh” vào cuối dãy.
int LinearSearch(int a[],int n, int x)
{ int i=0; a[n]=x;   // a[n] là phần tử “lính canh”
while(a[i]!=x) 
i++;
if(i==n)
return 0; // Tìm không thấy x
else
return 1; // Tìm thấy
}

*/
#include<iostream>
using namespace std;
int tim(int a[], int n,int x)
{
for (int i = 0; i < n;i++) if (x == a[i]) return i+1;
return 0;
}
void main()
{
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int x;
cout << "nhap gia tri muon tim: ";
cin >> x;
int vt = tim(a, 10, x);
if (vt !=0) cout << "tim thay tai vi tri: " << vt << "\n";
else cout << "khong tim thay\n";
}

Không có nhận xét nào:

Đăng nhận xét