• 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#

Moderators: tungcan5diop, QUANITGROBEST

User avatar
anhtuyenbk
Guru
Guru
Posts: 1311
Joined: Thu 22/09/2005 4:12 pm
Location: Một nơi chừa từng biết, chưa từng nghe, chưa từng thấy
Been thanked: 38 times

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

Postby anhtuyenbk » Sun 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.

Code: Select all

  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

Code: Select all

  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

Code: Select all

  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.
Last edited by anhtuyenbk on Tue 07/10/2008 10:29 am, edited 1 time in total.


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

User avatar
anhtuyenbk
Guru
Guru
Posts: 1311
Joined: Thu 22/09/2005 4:12 pm
Location: Một nơi chừa từng biết, chưa từng nghe, chưa từng thấy
Been thanked: 38 times

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

Postby anhtuyenbk » Tue 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.

Code: Select all

  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

Code: Select all

  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

User avatar
tiger86love102
Thành viên danh dự
Thành viên danh dự
Posts: 610
Joined: Sun 19/10/2008 1:10 am
Location: http://ready.vn
Has thanked: 4 times
Been thanked: 21 times
Contact:

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

Postby tiger86love102 » Sun 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

User avatar
anhtuyenbk
Guru
Guru
Posts: 1311
Joined: Thu 22/09/2005 4:12 pm
Location: Một nơi chừa từng biết, chưa từng nghe, chưa từng thấy
Been thanked: 38 times

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

Postby anhtuyenbk » Sun 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

User avatar
tiger86love102
Thành viên danh dự
Thành viên danh dự
Posts: 610
Joined: Sun 19/10/2008 1:10 am
Location: http://ready.vn
Has thanked: 4 times
Been thanked: 21 times
Contact:

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

Postby tiger86love102 » Sun 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
Posts: 1
Joined: Mon 17/11/2008 7:44 am

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

Postby hoachithuydiep » Tue 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.

User avatar
T7
Thành viên danh dự
Thành viên danh dự
Posts: 415
Joined: Thu 24/05/2007 8:19 pm
Location: Long Xuyên - An Giang
Been thanked: 12 times
Contact:

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

Postby T7 » Sun 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:

Code: Select all

  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ị

Code: Select all

  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:

Code: Select all

  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
Posts: 415
Joined: Sat 14/07/2007 10:06 pm
Location: Hà Nội
Been thanked: 1 time

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

Postby tienlbhoc » Sun 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
Posts: 11
Joined: Sun 07/12/2008 8:17 am

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

Postby cau123 » Sun 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
Posts: 11
Joined: Sun 07/12/2008 8:17 am

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

Postby cau123 » Sat 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

User avatar
tiger86love102
Thành viên danh dự
Thành viên danh dự
Posts: 610
Joined: Sun 19/10/2008 1:10 am
Location: http://ready.vn
Has thanked: 4 times
Been thanked: 21 times
Contact:

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

Postby tiger86love102 » Sat 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
Posts: 415
Joined: Sat 14/07/2007 10:06 pm
Location: Hà Nội
Been thanked: 1 time

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

Postby tienlbhoc » Sat 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/

User avatar
anhtuyenbk
Guru
Guru
Posts: 1311
Joined: Thu 22/09/2005 4:12 pm
Location: Một nơi chừa từng biết, chưa từng nghe, chưa từng thấy
Been thanked: 38 times

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

Postby anhtuyenbk » Sat 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
Posts: 9
Joined: Tue 20/09/2011 7:37 am

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

Postby tieutu8x » Wed 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

User avatar
QUANITGROBEST
Thành viên trung thành
Thành viên trung thành
Posts: 227
Joined: Thu 11/10/2012 9:47 am
Location: Thái Bình
Has thanked: 78 times
Been thanked: 24 times
Contact:

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

Postby QUANITGROBEST » Mon 12/11/2012 9:50 pm

tiger86love102 wrote: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]

User avatar
QUANITGROBEST
Thành viên trung thành
Thành viên trung thành
Posts: 227
Joined: Thu 11/10/2012 9:47 am
Location: Thái Bình
Has thanked: 78 times
Been thanked: 24 times
Contact:

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

Postby QUANITGROBEST » Mon 12/11/2012 9:53 pm

cau123 wrote: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]


Return to “[.NET] Bài viết hướng dẫn”

Who is online

Users browsing this forum: No registered users and 1 guest