10 Tin 2k11 - THPT Chuyên Lương Thế Vinh Đồng Nai Data Structures + Algorithms = Programming Tuesday, 18-01-22, 4:41 PM
Site menu
Statistics

Total online: 1
Guests: 1
Users: 0
Clock
Why Can't We Be Friends
Main » 2011 » August » 12 » Các thuật toán tìm kiếm
4:07 PM
Các thuật toán tìm kiếm

Thuật toán tìm kiếm tuần tự:
Input: Mảng A gồm n phần tử và giá trị x cần tìm

Output: vị trí mà phần tử x xuất hiện trong mảng A, nếu trong mảng A không có phần tử X thì xuất ra thông báo: khong tim thay

Bắt đầu từ phần tử đầu tiên, lần lượt so sánh từng phần tử với điều kiện tìm kiếm.
Nếu gặp phần tử đầu tiên thỏa mãn điều kiện tìm thì dừng.
Ngược lại tăng chỉ số lên 1 đơn vị để kiểm tra phần tử kế tiếp.

Chú ý: thuật toán dừng nếu một trong hai điều kiện dưới đây xảy ra:

- Tìm thấy

- Hết mảng.

 Tương đương với điều kiện tiếp tục tìm: Chưa tìm được và chưa hết mảng.

- nếu tìm thấy thì xuất ra vị trí mà X xuất hiện trong mảng (trong thuật toán này sẽ là vị trí đầu tiên mà X xuất hiện)

- nếu không tìm thấy thì xuất ra thông báo : khong tim thay


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

Thuật toán tìm kiếm nhị phân dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp, ví dụ như trong một danh bạ điện thoại sắp xếp theo tên, có thể tìm kiếm số điện thoại của một người theo tên người đó một cách dễ dàng như khi ta tra từ điển

Dữ liệu vào: mảng A có thứ tự (a1<a2<a3<...<an) và giá trị x cần tìm

Kết quả: thứ tự của x trong A nếu tìm thấy, nếu không trả về KHÔNG_THẤY

- Cấu trúc dữ liệu cần thiết để cài đặt thuật toán:

+ Mảng A có thứ tự gồm n phần tử.

+ X là giá trị cần tìm.

+ L: lưu chỉ số của phần tử đầu trong đoạn cần kiểm tra.

+ R: lưu chỉ số của phần tử cuối trong đoạn cần kiểm tra.

+ mid:= (L+R) div 2 : lưu chỉ số của phần tử được kiểm tra tại mỗi bước

+ isFound: lưu lại kết quả tìm kiếm, đươc khởi tạo là false;

Thuật toán (thuật toán tham khảo) :

bước 1: L:=1; R:= n; Mid:= (L+R) div 2; isFound:= false;

bước 2: trong khi L <= R ta thực hiện:

          - nếu a[mid] = x thì

                             Begin

                              + Thông báo tìm thấy X tại vị trí mid;

                              + isFound:=true;// đánh dấu lại đã tìm thấy  

                              + Thoát khỏi vòng lặp.

                             End;

          - nếu a[mid] < x thì L:= mid + 1;

          - nếu a[mid] > x thì R:= mid -1;

          - mid:= (L+R) div 2;

          - quay lại bước 2

bước 3: 

         - nếu isFound = false thì xuất ra thông báo không tìm thấy x trong mảng;

Views: 864 | Added by: Angle_Bup | Rating: 4.0/2
Total comments: 8
-1
8 ngkhtien   [Entry]
sr nhé, đúng là phải ghi là <= happy

0
7 ngkhtien   [Entry]
ah làm đc rồi, hihi (ủa sao mình làm l<r vẫn ra mà roll )

1
6 hex1105   [Entry]
thay oi cho L<R phải là L<=R chứ zậy nó mới tính dc

0
4 siêu_trộm_1412_76   [Entry]
thay chua gioi thieu ze thay biggrin

2
5 Angle_Bup   [Entry]
có trong forum rồi nhé! ^^

0
2 Dhbinh   [Entry]
e thay tìm kiếm này phải làm 1 bước chạy cho ct sap xếp lại 1 mảng theo thứ tự rùi mới tìm kiếm , vậy thì nó làm lâu hơn cái tìm kiem tuan tu

1
3 Angle_Bup   [Entry]
vậy đặt trường hợp dãy đã sắp xếp rồi thì cái nào nhanh hơn? ^^
thầy cũng đã nhấn mạnh hồi sáng:
nếu dãy đã có thứ tự rồi thì mới nên dùng tìm kiếm nhị phân còn khi dãy không có thứ tự thì mới dùng tìm kiếm tuần tự nhé em.

2
1 Dhbinh   [Entry]
thay hok chay 1 ct cho tui em xem thử hả thầy

Name *:
Email *:
Code *:
Login form
Chat Box
Search
Calendar
«  August 2011  »
SuMoTuWeThFrSa
 123456
78910111213
14151617181920
21222324252627
28293031
Entries archive
Site friends
  • VNOI
  • THPT Chuyên Lương Thế Vinh
  • Website builderuCoz!-->
    Copyright Hoàng Anh © 2022