tailieunhanh - Ebook Thuật toán thông dụng: Phần 2

Nối tiếp nội dung của phần 1 cuốn sách "Thuật toán thông dụng", phần 2 trình bày các nội dung: Thuật toán tìm kiếm, thuật toán sắp xếp, nguyên lý tham, bài tập lý thuyết trò chơi. Cuối mỗi chương đều có các bài tập vận dụng để người học có thể ôn tập là các kiến thức đã học. . | Chuông 3. THUẬT TOÁN TÌM K1ÉM 1. TÌM KIÉM THÔNG DỤNG I. lìm kiếm nhị phân Tìm kiếm nhị phân là thuật toán tìm kiếm nhanh một phần từ trên màng đã sắp tăng hoặc giảm theo khoá cùa các phần tử. Thuật toán dựa trên ý tường quan tâm tới phần tử đứng ở vị trí giữa. Giả sừ mảng đã sap tăng. Neu khoá tìm kiếm bằng khoá phan tử giữa thì hiện kết quả và kết thúc tim kiếm nếu khoá nhò hon khoá phần tử giữa thì thực hiện tìm kiếm nhị phân trên nứa thứ nhai của mảng bên trái ngược lại thì tìm kiểm nhị phán trên nửa thứ hai của mảng ben phái . Lưu ý rang dù tìm kiếm nhị phân có độ phức tạp tính toán là O log N nhưng chì dùng được trên màng đã sap. Sau đây là hàm tìm kiếm nhị phân viết trên C C int binarySearch int sorted Array jnt first int last int key Tìm kiếm theo khoá trêu màng đã sắp sortedArray từ phần tử first đến phần tử last iị í VC vị trí cùa phần tứ thích hợp nếu tìm thấy ngược lại trả về -1 key giá trị khoá can tim while first last int mid first last 2 if key sorted Array mid first mid 1 else if key sorledArray mid last mid - 1 else return mid Ị return -1 1 i 203 Tim kiêm nhị phân tòn được thực hiện hiệu quà trên Cây nhị phân tìm kiếm BST . Đó là cây nhị phân mà mồi nút có một khoá và bảo đám sắp xếp các nút sao cho nút con trái có khoá nhò hcm nút cha nút con phải cỏ khoá lớn hcm nút cha xem bài toán 6 chương 1 mục 5 . Việc tìm kiểm trên BST nhu sau Đế tim một nút có khoá X đầu tiên so sánh nó với khoá của nút goc. Neu nhỏ hơn. tiên hành tìm tiếp ờ cây con bên trái neu bang nhau thì dừng quá trình tìrn kiếm nếu lớn hơn thì tiến hành tìm kiếm ơ cây con bên phải. Quá trình tim kiếm trên cây con được lập lại tương tự. Đoạn chương trình minh hoạ struct node int item struct node left struct node right typedef struct node tree tree search int X. tree root int found 0 tree temp root while temp NULL if x temp else if x temp else break return temp 2. Tìm kiếm theo chiều sáu tren đồ thị DFS -