Trang 1 trên 1

[C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: CN 05/10/2008 10:50 pm
gửi bởi anhtuyenbk
Tên bài viết: Thuật toán tìm kiếm - C#
Tác giả: Nguyễn Anh Tuyên
Cấp độ bài viết: Cơ bản tới nâng cao
Tóm tắt: Trong thực tế, khi thao tác, khai thác dữ liệu chúng ta hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm. Việc tìm kiếm nhanh hay chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên đó. Kết quả của việc tìm kiếm có thể là không có (không tìm thấy) hoặc có (tìm thấy). Nếu kết quả tìm kiếm là có tìm thấy thì nhiều khi chúng ta còn phải xác định xem vị trí của phần tử dữ liệu tìm thấy là ở đâu?



Thuật toán tìm kiếm - C#


Trong thực tế, khi thao tác, khai thác dữ liệu chúng ta hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm. Việc tìm kiếm nhanh hay chậm tùy thuộc vào trạng thái và trật
tự của dữ liệu trên đó. Kết quả của việc tìm kiếm có thể là không có (không tìm thấy) hoặc có (tìm thấy). Nếu kết quả tìm kiếm là có tìm thấy thì nhiều khi chúng ta còn phải xác định xem vị trí của phần tử dữ liệu tìm thấy là ở đâu?

1. Dữ liệu để test việc thực hiện tìm kiếm
Đây là một mảng số nguyên tăng dần ta tạo ra.

Mã: Chọn hết

  1. int[] MangData = new int[100];
  2. //Tao du lieu de thuc hien cac phuong phap tim kiem
  3.             for (int i = 0; i < MangData.Length; i++)
  4.             {
  5.                 MangData[i] = 2 * i + 1;                
  6.             }
  7.  

Khi ta chạy đoan code này mảng tạo ra sẽ có dạng 1,3,5,7................199.

2. Tìm tuyến tính (Linear Search)
Thuật toán tìm tuyến tính còn được gọi là Thuật toán tìm kiếm tuần tự (Sequential
Search).
a. Tư tưởng:
Lần lượt so sánh các phần tử của mảng M với giá trị X bắt đầu từ phần tử đầu tiên
cho đến khi tìm đến được phần tử có giá trị X hoặc đã duyệt qua hết tất cả các phần
tử của mảng M thì kết thúc.
b.Code
Dùng vòng lặp for

Mã: Chọn hết

  1. int giatricantim = Convert.ToInt16(txtSocantim.Text);
  2.             //-----------------------Tim voi vong lap for
  3.             int Vitri=-1;
  4.             for (int i = 0; i < MangData.Length; i++)
  5.             {
  6.                 if (MangData[i] == giatricantim) // Tim thay gia tri can tim
  7.                 {
  8.                     Vitri=i;
  9.                     break;
  10.                 }
  11.             }
  12.             if (Vitri == -1)
  13.                 MessageBox.Show("Khong tim duoc");
  14.             else
  15.     MessageBox.Show("Tim duoc o vi tri = " + Vitri.ToString());

Dùng vòng lặp Do While

Mã: Chọn hết

  1. int Vitri = 0;
  2.             while (Vitri< MangData.Length && MangData[Vitri] != giatricantim)
  3.                 Vitri++;
  4.             if (Vitri < MangData.Length)
  5.                 MessageBox.Show("Tim duoc o vi tri = " + Vitri.ToString());
  6.             else
  7.                 MessageBox.Show("Khong tim duoc");

c. Đánh giá
Thuật toán tìm tuyến tính tỏ ra đơn giản và thuận tiện trong trường hợp số phần tử của
dãy không lớn lắm. Tuy nhiên, khi số phần tử của dãy khá lớn, chẳng hạn chúng ta tìm kiếm tên một khách hàng trong một danh bạ điện thoại của một thành phố lớn theo thuật toán tìm tuần tự thì quả thực mất rất nhiều thời gian.

Re: Tìm hiểu thuật toán tìm kiếm - C#

Đã gửi: T.Ba 07/10/2008 10:29 am
gửi bởi anhtuyenbk
3. Tìm kiếm nhị phân (Binary Search)

Thuật toán tìm tuyến tính tỏ ra đơn giản và thuận tiện trong trường hợp số phần tử của dãy không lớn lắm. Tuy nhiên, khi số phần tử của dãy khá lớn, chẳng hạn chúng ta tìm kiếm tên một khách hàng trong một danh bạ điện thoại của một thành phố lớn theo thuật toán tìm tuần tự thì quả thực mất rất nhiều thời gian.
Trong thực tế, thông thường các phần tử của dãy đã có một thứ tự, do vậy thuật toán tìm nhị phân sau đây sẽ rút ngắn đáng kể thời gian tìm kiếm trên dãy đã có thứ tự. Trong thuật toán này chúng ta giả sử các phần tử trong dãy đã có thứ tự tăng (không giảm dần), tức là các phần tử đứng trước luôn có giá trị nhỏ hơn hoặc bằng phần tử đứng sau nó.
a. Tư tưởng:
Phạm vi tìm kiếm ban đầu của chúng ta là từ phần tử đầu tiên của dãy (First = 1) cho đến phần tử cuối cùng của dãy (Last = N).
So sánh giá trị X với giá trị phần tử đứng ở giữa của dãy M là M[Mid].
Nếu X = M[Mid]: Tìm thấy
Nếu X < M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa đầu của dãy M (Last = Mid-1)
Nếu X > M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa sau của dãy M (First = Mid+1)
Lặp lại quá trình này cho đến khi tìm thấy phần tử có giá trị X hoặc phạm vi tìm
kiếm của chúng ta không còn nữa (First > Last).
b. Code :
Có 2 cách dùng là dùng đệ quy và ko đệ quy ở đây mình sẽ hướng dẫn các bạn dùng ko đệ quy - nó cúng ko phức tạp hơn đệ quy là bao nhưng tốc độ nhanh hơn.

Mã: Chọn hết

  1. private int BinarySearchKoDeQuyTangDan(int[] array, int ValueFind)
  2.         {
  3.             int First = 0;
  4.             int Last = array.Length-1;
  5.             while (First <= Last)
  6.             {
  7.                 int MID = (First + Last) / 2;
  8.                 if (array[MID] == ValueFind)  //Tim thay
  9.                     return MID;
  10.                 else if (ValueFind <array[MID] )
  11.                     Last = MID - 1;
  12.                 else
  13.                     First = MID + 1;
  14.             }
  15.             //Ko tim duoc gi
  16.             return -1;
  17.         }

Đây là code để test thử phương phá tìm kiếm trên

Mã: Chọn hết

  1. private void btnBinarySearch_Click(object sender, EventArgs e)
  2.         {
  3.             int giatricantim = Convert.ToInt32(txtSocantim.Text);
  4.             int vitri = BinarySearchKoDeQuyTangDan(MangData,  giatricantim);
  5.             if (vitri != -1)
  6.                 MessageBox.Show("Tim duoc o vi tri = " + vitri.ToString());
  7.             else
  8.                 MessageBox.Show("Khong tim duoc");
  9.         }

c. Lưu ý:
- Thuật toán tìm nhị phân chỉ có thể vận dụng trong trường hợp dãy/mảng đã có
thứ tự. Trong trường hợp tổng quát chúng ta chỉ có thể áp dụng thuật toán tìm
kiếm tuần tự.
- Các thuật toán đệ quy có thể ngắn gọn song tốn kém bộ nhớ để ghi nhận mã
lệnh chương trình (mỗi lần gọi đệ quy) khi chạy chương trình, do vậy có thể
làm cho chương trình chạy chậm lại. Trong thực tế, khi viết chương trình nếu có
thể chúng ta nên sử dụng thuật toán không đệ quy.

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: CN 16/11/2008 5:33 pm
gửi bởi tiger86love102
Anh Tuyên ơi, cái này áp dụng cho VB.NET đc ko anh? Có khác nhiều lắm ko anh?

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: CN 16/11/2008 5:40 pm
gửi bởi anhtuyenbk
Chỉ cần convert code từ C# qua VB.Net là xong.

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: CN 16/11/2008 5:46 pm
gửi bởi tiger86love102
Ý tưởng vẫn vậy hả anh? Gán dữ liệu vào mảng và thực hiện tìm kiếm trên mảng hả anh? Có thể tìm kiếm trực tiếp trên DatagridView chứ ạ?
Con vớt từ C# => VB.NET ư ? :-? Cùng lắm em hiểu đc ý tưởng và thuật giải thôi, tự mò xem sao :-? [-(
Thực hành nào =D>

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: T.Ba 18/11/2008 8:07 pm
gửi bởi hoachithuydiep
trong c# đã có tạo sẵn rồi cứ việc lên msdn mà coi cách sử dụng thôi cần gì viết lại vậy bạn.

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: CN 07/12/2008 9:38 am
gửi bởi T7
Bổ sung thêm một cách khác cho bài thêm phong phú tí :)
4/ Sử dụng Array.Find
a) Tư tưởng:
Em thấy dùng hàm Find trong array vẫn nhanh lắm chứ. Nó là hàm cung cấp sẳng mà, cớ gì mà ta không xài chứ :D

b) Code:

Mã: Chọn hết

  1. 'Khai báo giá trị <<<Lưu ý là khai báo biến toàn cục nhé>>>
  2. Dim Vitri As Integer
  3. Dim Match As Integer
  4. Dim mangData(100000) As Integer
  5.  
  6. 'Thêm các phần tử vào mảng
  7.         Dim i As Integer
  8.         For i = 0 To 100000
  9.             mangData(i) = 2 * i + 1
  10.         Next


Hàm FindProc có nhiệm vụ tìm kiếm giá trị

Mã: Chọn hết

  1.    Private Function FindProc(ByVal a As Integer) As Boolean
  2.         Vitri += 1
  3.         If a = Match Then 'Nếu tìm thấy thì trả về True, nếu không thì trả về False
  4.             Return True
  5.         Else
  6.             Return False
  7.         End If
  8.     End Function


Dùng Array.Find để tìm giá trị trong mảng:

Mã: Chọn hết

  1.        Vitri = 0
  2.         Match = 155555 'Đây là giá trị cần tìm kiếm
  3.         If Array.Find(mangData, AddressOf FindProc) Then 'Đưa con trỏ đến hàm FindProc để tìm kiếm
  4.             MsgBox("Tìm thấy giá trị: " & Match & " ở vị trí: " & Vitri & " của mảng")
  5.         Else
  6.             MsgBox("Không tìm thấy giá trị")
  7.         End If

c) Nhận xét:
Em đã test với mảng 100 triệu phần tử. Phải nói là nó tìm ra cực nhanh, click cái là nó hiện ra liền :)) . Chỉ chậm ở chổ ngồi đợi nó gán giá trị vào 100 triệu phần tử đó thôi :D

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: CN 07/12/2008 10:21 am
gửi bởi tienlbhoc
100 triệu , cũng chả có ý nghĩa gì nếu trên ram , chỉ cần 1 triệu , mà em đọc từ file lên mà so sánh thì kích cái , vài giây sau mới ra , đơ máy trong lúc search ;)) (search dữ liệu phải đọc từ file ra chứ tự tạo dữ liệu thì để làm gì , nó vô giá ... trị ) . Lúc đó sẽ biết mèo nào cắn mỉu nào, binary search là tối ưu. hơn nữa em chỉ nghĩ kích 1 cái thôi , nếu truy vấn liên tục vài lần (search theo list chẳng hạn) thì sẽ rõ .

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: CN 07/12/2008 11:07 pm
gửi bởi cau123
Những đoạn code trên sử dụng cho c# đúng ko mấy anh ơi

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: T.Bảy 13/12/2008 1:18 am
gửi bởi cau123
Bác nào có lòng hảo tâm PM nick tienthanh209 giúp em bài tìm kiếm này với
Yêu cầu của thầy là viết bằng C#,ngôn ngữ chỉ mới nghe tên :((
Và phải làm cả phần đồ họa nữa
Pro nào giúp em với ,nếu ở Hà Nội sẽ có dịp cảm ơn

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: T.Bảy 13/12/2008 4:30 am
gửi bởi tiger86love102
Bạn không nên nhõng nhẽo xin code kẻo bị delete nick bạn ah.
Bạn cố gắng đọc và làm theo các anh hướng dẫn chứ, hiểu bạn có thể áp dụng vào bài toán bạn cần mà.
Thắc mắc ko hiểu ở đâu lại hỏi, như vậy có tốt hơn ko mà đỡ mất thời gian.

Yêu cầu của thầy là viết bằng C#,ngôn ngữ chỉ mới nghe tên
Và phải làm cả phần đồ họa nữa

Thế này khác ji bạn nhờ làm bài tập hộ, ko ai làm đâu bạn ạ. Tự chiến tự sướng thôi.

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: T.Bảy 13/12/2008 1:41 pm
gửi bởi tienlbhoc
chữa khéo ghê ;)) . Lúc đầu bảo chỉ cần thuật toán thôi mà , giờ thêm phần đồ họa là dâng bài cho bạn rồi còn gì :D .
Ra topic khác hỏi về đồ họa nhé , mà chưa học c# đã nhảy lên đồ họa , rõ ràng thích xin code thôi chứ đọc sao nổi mà đòi ;))

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: T.Bảy 13/12/2008 4:06 pm
gửi bởi anhtuyenbk
1. Ở trên là toàn bộ code cho các thuật toán tìm kiếm rồi, bạn hãy tự tay gõ vào thì mới hiểu được hoạt động của nó.
2. Còn về đồ họa bạn có thể tìm kiếm topic nói về GDI trong forum.

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: T.Tư 16/05/2012 9:09 am
gửi bởi tieutu8x
Mình hỏi tí nhé. ví dụ như bây giờ mình muốn tìm kiếm một chuỗi ký tự trên file định dạng *.htm. khi mình tìm được chuỗi cần tìm rồi nhưng làm thế nào để đánh dấu chuỗi tìm kiếm đó khi hiển thị file

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: T.Hai 12/11/2012 9:50 pm
gửi bởi QUANITGROBEST
tiger86love102 đã viết:Anh Tuyên ơi, cái này áp dụng cho VB.NET đc ko anh? Có khác nhiều lắm ko anh?

Bạn hiểu được giải thuật thì qua VB cũng vậy thôi có khác j đâu.

Re: [C#] Tìm hiểu thuật toán tìm kiếm

Đã gửi: T.Hai 12/11/2012 9:53 pm
gửi bởi QUANITGROBEST
cau123 đã viết:Những đoạn code trên sử dụng cho c# đúng ko mấy anh ơi

bạn học lập trình mà ko phân biệt dc đâu là code VB đâu là code c# ah, code C# giống với code C kết thúc có dâu ; còn VB thì ko có