Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Saturday, January 24, 2015

/*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";
}

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts