• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

[C]Thuật toán tìm kiếm

Các bài viết hướng dẫn và tham khảo chung, không thuộc ngôn ngữ nào

Điều hành viên: vietluyen

Hình đại diện của người dùng
nimgiaminh
Thành viên danh dự
Thành viên danh dự
Bài viết: 431
Ngày tham gia: T.Bảy 07/08/2010 9:24 am
Đến từ: Ở dưới đó đó
Has thanked: 6 time
Been thanked: 18 time
Liên hệ:

[C]Thuật toán tìm kiếm

Gửi bàigửi bởi nimgiaminh » T.Sáu 21/01/2011 7:26 pm

Tên bài viết: Thuật toán tìm kiếm
Tác giả: Sưu tầm
Cấp độ bài viết: Cơ bản
Tóm tắt: Đây là bài viết nói về thuật toán tìm kiếm dành cho các Newbie, sử dụng ngôn ngữ C để biểu diễn thuật toán


Có 2 giải thuật thường được áp dụng để tìm kiếm dữ liệu là tìm tuyến tínhtìm nhị phân.
Để đơn giản trong việc trình bày giải thuật, bài toán được đặc tả như sau :
+ Tập dữ liệu được lưu trữ là các dãy số a1, a2, ......, aN. Giả sử chọn cấu trúc dữ liệu mảng để lưu trữ dãy số này trong bộ nhớ chính, có khai báo : int a[N]
+ Khóa cần tìm là x, được khai báo như sau : int X;

1. Thuật toán tìm kiếm tuyến tính :

- Ý 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 :

+ B1 : Khởi gán i=0;
+ B2 : 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.
+ B3 : i=i+1 //Xét tiếp phần tử kế tiếp trong mảng.
* i ==n //Hết mảng. Dừng.
* Ngược lại : Lặp lại B2.

- Giải thuật :

[c]int Timtuyentinh(int a[],int n,int x)
{
int i=0;
while((i<n) && (a[i]!=x))
i++;
if(i==n)
return 0; //Tìm hết mảng nhưng không có x
else
return 1; //a[i] là phần tử có khóa x
}[/c]

2. Thuật toán tìm kiếm nhị phân :

- Ý tưởng :
+ Giả sử ta xét mảng có thứ tự tăng, khi ấy ta có a[i-1] <= a[i] <= a[i+1].
+ Nếu x > a[i] thì x chỉ có thể xuất hiện trong đoạn [a[i+1],a[n]]
+ Nếu x < a[i] thì x chỉ có thể xuất hiện trong đoạn [a[0],a[i-1]]
+ Ý tưởng của giải thuật là tại mỗi bước ta so sánh x với phần tử đứng giữa trong dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm ở nữa dưới hay nửa trên của dãy tìm kiếm hiện hành.

- Các bước tiến hành :

Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử nằm trong aleft, aright, các bước của giải thuật như sau:

+ B1 : Khởi gán left=0;right=n-1;
+ B2 :
mid=(left+right)/2;//Chỉ số phần tử giữa dãy hiện hành
So sánh a[mid] với giá trị x cần tìm, có 3 khả năng :
* a[mid]==x //Tìm thấy x. Dừng.
* a[mid] > x //Tìm tiếp x trong dãy con a[left].......a[mid-1]
right = mid -1
* a[mid] < x //Tìm tiếp x trong dãy con a[mid+1].......a[right]
left = mid+1
+ B3 :Nếu left <= right //Còn phần tử chưa xét => tìm tiếp
Lặp lại bước 2
Ngược lại : Dừng //Đã xét hết tất cả các phần tử

- Giải thuật :

[c]int Timnhiphan(int a[],int n,int x)
{
int left,right,mid;
left = 0;
right = n-1;
do
{
mid=(left + right)/2;
if(a[mid]==x)
return 1; // tìm thấy khóa x
else if (a[mid]<x)
left=mid+1;
else
right=mid-1;
}while(left <= right);
return 0;
}[/c]

Hình đại diện của người dùng
dazzlingvit
Guru
Guru
Bài viết: 959
Ngày tham gia: T.Ba 18/01/2011 10:21 am
Đến từ: Sinh ra từ hư vô, sống trong thế giới ảo...
Has thanked: 6 time
Been thanked: 110 time
Liên hệ:

Re: Thuật toán tìm kiếm

Gửi bàigửi bởi dazzlingvit » T.Ba 25/01/2011 3:14 pm

Nên trình bày thuật toán tìm kiếm nhị phân tổng quát hơn tí nữa, tức là k0 phải tìm trong đoạn từ 0 đến n - 1 mà tìm trong đoạn từ u đến v ;)

minhanhnhoem
Bài viết: 2
Ngày tham gia: T.Bảy 19/11/2011 2:52 am

Re: [C]Thuật toán tìm kiếm

Gửi bàigửi bởi minhanhnhoem » T.Bảy 19/11/2011 3:18 am

.................. cau hoi hay tra loi cung hay nhung..............minh chua biet ve no
minh muon tim hieu ve vb nhung chua biet bat dau tu dau
mong cac ban cho the cho minh nhung chi dan de minh co the theo cac ban
nhiet tinh jup do
thank


Quay về “Bài viết hướng dẫn”

Đang trực tuyến

Đang xem chuyên mục này: Không có thành viên nào trực tuyến.0 khách