• 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#] Tìm hiểu thuật toán tìm kiếm

Các bài viết hướng dẫn về Visual Basic .NET và C#

Điều hành viên: tungcan5diop, QUANITGROBEST

Hình đại diện của người dùng
anhtuyenbk
Guru
Guru
Bài viết: 1311
Ngày tham gia: T.Năm 22/09/2005 4:12 pm
Đến từ: Một nơi chừa từng biết, chưa từng nghe, chưa từng thấy
Been thanked: 38 time

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

Gửi bàigửi bởi anhtuyenbk » CN 05/10/2008 10:50 pm

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.
Sửa lần cuối bởi anhtuyenbk vào ngày T.Ba 07/10/2008 10:29 am với 1 lần sửa.


Kiếm cơm cho qua ngày tháng
https://www.facebook.com/pinduphongpisenchinhhang

Hình đại diện của người dùng
anhtuyenbk
Guru
Guru
Bài viết: 1311
Ngày tham gia: T.Năm 22/09/2005 4:12 pm
Đến từ: Một nơi chừa từng biết, chưa từng nghe, chưa từng thấy
Been thanked: 38 time

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

Gửi bàigửi bởi anhtuyenbk » T.Ba 07/10/2008 10:29 am

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.
Kiếm cơm cho qua ngày tháng
https://www.facebook.com/pinduphongpisenchinhhang

Hình đại diện của người dùng
tiger86love102
Thành viên danh dự
Thành viên danh dự
Bài viết: 610
Ngày tham gia: CN 19/10/2008 1:10 am
Đến từ: http://ready.vn
Has thanked: 4 time
Been thanked: 21 time
Liên hệ:

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

Gửi bàigửi bởi tiger86love102 » CN 16/11/2008 5:33 pm

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?
Đội bóng Ready
facebook.com/tiger86love102

Hình đại diện của người dùng
anhtuyenbk
Guru
Guru
Bài viết: 1311
Ngày tham gia: T.Năm 22/09/2005 4:12 pm
Đến từ: Một nơi chừa từng biết, chưa từng nghe, chưa từng thấy
Been thanked: 38 time

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

Gửi bàigửi bởi anhtuyenbk » CN 16/11/2008 5:40 pm

Chỉ cần convert code từ C# qua VB.Net là xong.
Kiếm cơm cho qua ngày tháng
https://www.facebook.com/pinduphongpisenchinhhang

Hình đại diện của người dùng
tiger86love102
Thành viên danh dự
Thành viên danh dự
Bài viết: 610
Ngày tham gia: CN 19/10/2008 1:10 am
Đến từ: http://ready.vn
Has thanked: 4 time
Been thanked: 21 time
Liên hệ:

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

Gửi bàigửi bởi tiger86love102 » CN 16/11/2008 5:46 pm

Ý 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>
Đội bóng Ready
facebook.com/tiger86love102

hoachithuydiep
Bài viết: 1
Ngày tham gia: T.Hai 17/11/2008 7:44 am

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

Gửi bàigửi bởi hoachithuydiep » T.Ba 18/11/2008 8:07 pm

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.

Hình đại diện của người dùng
T7
Thành viên danh dự
Thành viên danh dự
Bài viết: 415
Ngày tham gia: T.Năm 24/05/2007 8:19 pm
Đến từ: Long Xuyên - An Giang
Been thanked: 12 time
Liên hệ:

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

Gửi bàigửi bởi T7 » CN 07/12/2008 9:38 am

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
While (i <= you) i++;

tienlbhoc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 415
Ngày tham gia: T.Bảy 14/07/2007 10:06 pm
Đến từ: Hà Nội
Been thanked: 1 time

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

Gửi bàigửi bởi tienlbhoc » CN 07/12/2008 10:21 am

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õ .
Diễn đàn và blog phần mềm tự làm :
http://my.opera.com/DienDanTienlbhoc/forums/
http://my.opera.com/tienlbhoc/blog/

cau123
Thành viên chính thức
Thành viên chính thức
Bài viết: 11
Ngày tham gia: CN 07/12/2008 8:17 am

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

Gửi bàigửi bởi cau123 » CN 07/12/2008 11:07 pm

Những đoạn code trên sử dụng cho c# đúng ko mấy anh ơi

cau123
Thành viên chính thức
Thành viên chính thức
Bài viết: 11
Ngày tham gia: CN 07/12/2008 8:17 am

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

Gửi bàigửi bởi cau123 » T.Bảy 13/12/2008 1:18 am

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

Hình đại diện của người dùng
tiger86love102
Thành viên danh dự
Thành viên danh dự
Bài viết: 610
Ngày tham gia: CN 19/10/2008 1:10 am
Đến từ: http://ready.vn
Has thanked: 4 time
Been thanked: 21 time
Liên hệ:

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

Gửi bàigửi bởi tiger86love102 » T.Bảy 13/12/2008 4:30 am

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.
Đội bóng Ready
facebook.com/tiger86love102

tienlbhoc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 415
Ngày tham gia: T.Bảy 14/07/2007 10:06 pm
Đến từ: Hà Nội
Been thanked: 1 time

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

Gửi bàigửi bởi tienlbhoc » T.Bảy 13/12/2008 1:41 pm

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 ;))
Diễn đàn và blog phần mềm tự làm :
http://my.opera.com/DienDanTienlbhoc/forums/
http://my.opera.com/tienlbhoc/blog/

Hình đại diện của người dùng
anhtuyenbk
Guru
Guru
Bài viết: 1311
Ngày tham gia: T.Năm 22/09/2005 4:12 pm
Đến từ: Một nơi chừa từng biết, chưa từng nghe, chưa từng thấy
Been thanked: 38 time

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

Gửi bàigửi bởi anhtuyenbk » T.Bảy 13/12/2008 4:06 pm

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.
Kiếm cơm cho qua ngày tháng
https://www.facebook.com/pinduphongpisenchinhhang

tieutu8x
Bài viết: 9
Ngày tham gia: T.Ba 20/09/2011 7:37 am

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

Gửi bàigửi bởi tieutu8x » T.Tư 16/05/2012 9:09 am

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

Hình đại diện của người dùng
QUANITGROBEST
Thành viên trung thành
Thành viên trung thành
Bài viết: 227
Ngày tham gia: T.Năm 11/10/2012 9:47 am
Đến từ: Thái Bình
Has thanked: 78 time
Been thanked: 24 time
Liên hệ:

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

Gửi bàigửi bởi QUANITGROBEST » T.Hai 12/11/2012 9:50 pm

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.
http://grobest.com.vn/[url]spasenhong.vn[/url]

Hình đại diện của người dùng
QUANITGROBEST
Thành viên trung thành
Thành viên trung thành
Bài viết: 227
Ngày tham gia: T.Năm 11/10/2012 9:47 am
Đến từ: Thái Bình
Has thanked: 78 time
Been thanked: 24 time
Liên hệ:

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

Gửi bàigửi bởi QUANITGROBEST » T.Hai 12/11/2012 9:53 pm

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ó
http://grobest.com.vn/[url]spasenhong.vn[/url]


Quay về “[.NET] 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.2 khách