PGS TS Bùi Thế Tâm – Tim kiem noi suy
Bài toán. Cho danh sách a gồm n phần tử với các giá trị số (hoặc xâu ký tự, hoặc các bản ghi) và giá trị cần tìm là x. Tìm chỉ số của phần tử trong a có giá trị bằng x.
Thuật toán. Thuật toán tìm kiếm nội suy là cải tiến của thuật toán tìm kiếm nhị phân (Binary Search). Độ phức tạp của thuật toán này là Ο(log (log n)), trong khi của Binary Search là Ο(log n).
Trong thuật toán tìm kiếm nhị phân, danh sách cần xét được chia đôi bởi phần tử ở giữa thành hai phần: phần bên trái và phần bên phải, sau đó xét tiếp phần chứa x. Nhược điểm của thuật toán tìm kiếm nhị phân là không tính đến độ lớn của phần tử cần tìm x. Do đó trong thuật toán tìm kiếm nội suy để chia danh sách thành hai phần, chúng ta sử dụng công thức có tính đến độ lớn của x. Nếu phần tử cần tìm có giá trị lớn hơn phần tử ở giữa thì phần tử cần tìm sẽ ở mảng con bên phải phần tử ở giữa và chúng ta lại tiếp tục tính vị trí dò; trái lại phần tử cần tìm sẽ ở mảng con bên trái phần tử ở giữa. Tiến trình này tiến tụp diễn ra trên các mảng con cho tới khi kích cỡ của mảng con giảm về 0.
HỌC TIN HỌC ONLINE MIỄN PHÍ
Đây là kênh chính thức của PGS TS Bùi Thế Tâm, Kênh đào tạo miễn phí về Công nghệ thông tin. Nội dung: Tin học văn phòng, Hướng dẫn sử dụng Microsoft Office, Hướng dẫn dùng Google Drive, Lập trình ngôn ngữ C, Lập trình hướng đối tượng C++ trên Visual Studio, Cấu trúc dữ liệu và giải thuật, Algorithms (Giải thuật), Sorting algorithms, Graph (đồ thi), Các thuật toán toán tối ưu, các bài toán thống kê, Giáo trình tin học văn phòng, Giáo trình ngôn ngữ lập trình C.
Bùi Thế Tâm có nhiều năm kinh nghiệm viết sách và dạy Tin học ở các trường Đại học, làm việc tại Viện Toán học Hà Nội từ 1969 – 2013, là tác giả của một số đầu sách nhiều người dùng: “Giá trình tin học văn phòng”, “Cẩm nang sử dụng máy vi tính”, “Ngôn ngữ lập trình C và lập trình hướng đối tượng”, “Giáo trình Turbo Pascal 7.0”, “Các phương pháp tối ưu hóa” …
Kênh này dành cho các bạn sinh viên, giáo viên dạy môn Tin học, các bạn muốn học Tin học mà không có điều kiện tới các lớp học.
Hãy like và chia sẻ các vidio trên Kênh cho bạn bè và những người bạn quen đang muốn học về Tin học. Mọi hình thức copy và sao chép đều vi phạm bản quyền của youtube nếu không được sự đồng ý của tác giả Bùi Thế Tâm. Đừng quên đăng ký kênh để học thêm các bài mới
Subscribe kênh Youtube Bui The Tam:
Facebook:
Twitter:
Blog:

Nguồn: https://inst-wd.com/

Xem thêm bài viết khác: https://inst-wd.com/tong-hop/

9 COMMENTS

  1. Dạ thầy ơi, em có câu hỏi là liệu điều kiện a[h]!=a[l] có thể thay thành h!=l không ạ? Và mảng a đã được sắp xếp ấy các phần tử có bắt buộc phải là đôi một khác nhau không hay là có thể có các phần tử trùng lặp ạ (như 1,2,3,4,5,6,6,7,8,8,9). Em cảm ơn.

  2. trong bài toán này e thấy điều kiện a[low]!=a[hight] là ko cần thiết khi mảng đã được sắp xếp và số ptu>1

  3. Cho em hỏi nếu mảng chứa các phần tử kiểu string thì sao ạ? Vì các phần tử string đâu có trừ nhau được???

  4. Có thể viết hàm như sau:
    int interpolation_search(int a[], int n, int x)
    {
    int m, l = 0, h = n – 1;
    if (x < a[l] || x > a[h]) return -1;
    do {
    m = l + (h – l)*(x – a[l])/(a[h] – a[l]);
    if (a[m] < x) l = m + 1;
    else if (a[m] > x) h = m – 1;
    else return m;
    } while (l < h);
    if (a[l] == x) return l;
    return -1;
    }

LEAVE A REPLY

Please enter your comment!
Please enter your name here