Các giải thuật tìm kiếm

Tham khảo tài liệu các giải thuật tìm kiếm, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Các giải thuật tìm kiếm CÁC GIẢI THUẬT TÌM KIẾM12. CÁC GIẢI THUẬT TÌM KIẾM Có 2 giải thuật thường được áp dụng: Tìm tuyến tính và tìm nhị phân. Để đơn giản cho việc minh họa, ta đặc tả như sau: a1 a2 a3 a4 a5 … an-1 aN  Tập dữ liệu được lưu trữ là dãy số a , a , ... ,a .  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];  Khoá cần tìm là x, được khai báo như sau: int x; 23. Tìm kiếm tuyến tính Ý tưởng Tiến hành so sánh x lần lượt với phần tử thứ nhất, thứ hai, ... của mảng a cho đến khi gặp được phần tử có khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x. Minh họa tìm x =10 Chưa Đã tìm 10 thấy t ại hế 7 5 12 41 10 32 13 9 15 3 vị ảng m trí 5 1 2 3 4 5 6 7 8 9 10 Minh họa tìm x =25 Chưa Đã hết hết 25 mảng mảng 3 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 Giải thuật Bước 1: i=1;//bắtđầutừphầntửđầutiêncủa dãy Bước 2: Sosánha[i]vớix, có2khảnăng: a[i]=x:Tìmthấy.Dừng a[i]!=x:SangBước3. Bước 3: i=i+1;//xéttiếpphầntửkếtrongmảng Nếui>N:Hếtmảng,khôngtìmthấy.Dừng 4 Ngượclại:LặplạiBước2.Cài đặt intLinearSearch(inta[],intN,intx) { inti=0; while((iCai tiên (dung linh canh) giup giam bớt môt ̉ ́ ̀ ́ ́ ̉ ̣ ́ ́phep so sanh Minh họa tìm x =10 10 10 7 5 12 41 10 32 13 9 15 3 Minh 2họa tìm 1 3 x4= 255 6 7 8 9 10 25 25 7 5 12 41 10 32 13 9 15 3 25 1 2 3 4 5 6 7 8 9 10 11 6 Giải thuật Bước 1: i=1; a[N+1]=1; //phầntử“línhcanh” Bước 2: Sosánha[i]vớix, có2khảnăng: a[i]=x:sangbước3 a[i]!=x:i=i+1; Bước 3: Nếui≤N:tìmthấyxtạivịtríi. Ngượclại:khôngtìmthấyxtrongdãy. 7Cài đặt intLinearSearch2(inta[],intN,intx) { inti=0; //mảnggồmNphầntửtừa[0]..a[N-1] a[N]=x;//thêmphầntửthứN+1 while(a[i]!=x) i++; if(i==N) //tìmhếtmảngnhưngkhôngcóx return-1; else //tìmthấyxtạivịtríi returni; } giá giải thuật Ðánh 8 Độ phức tạp tính toán cấp n: T(n)=O(n)4. Tìm kiếm nhị phânÝ tưởng Áp dụng đối với những dãy số đã có thứ tự. Giải thuật tìm cách giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành. 9Minh họa tìm x = 41 x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 Tìm thấy x tại vị trí 6 l m m r m 10Minh họa tìm x = 45 x x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 l m m r l > r: Kết thúc: Không tìm thấy m m 11Giải thuật Bước 1: left = 1; right = N; // tìm kiếm trên tất c ...