Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Thuật toán tinh chế mã
Nội dung xem thử
Mô tả chi tiết
Một số kỹ thuật tinh chế mã
Đặng Quang Hưng
Mộtphiên bản tốt hơn của tìm nhị phân
Trong số báo tháng trước tôi đã giới thiệu cho các bạnchương Tinh chế mã của tác giả
Jon Bentley trong cuốn 'ProgrammingPearls' (Những viên ngọc trong kỹ thuật lập trình).
Với số này chúng ta sẽ cùng nhau tìm hiểu một trong những ví dụ tinh tế nhấtcủa kỹ thuật
tinh chế mã, đó là kỹ thuật tăng tốc độ cho chươngtrình tìm nhị phân.
Chươngtrình tìm nhị phân nguyên thủy
L:= 1; R := N;
WHILE(L<=R) DO
BEGIN
M:=(L+R) DIV 2;
IF (A[M] < X) THEN
L:=M+1;
ELSE
IF (A[M] > X) THEN
R:=M-1;
ELSE
BREAK;
END;
IF(L<=R) HEN
P:=M;
ELSE
P := 0;
Chươngtrình tìm nhị phân tổng quát này đã rất hiệu quả, hiệu quả đến nỗimọi nỗ lực tinh
chế mã để nhằm tăng tốc nó đều không mang lại mộtsự khác biệt đáng kể nào! Như vậy thì
tại sao chúng ta lại đề cậpđến vấn đề cải thiện chương trình này ở đây? Chúng ta sẽ
khôngtìm cách tinh chế chương trình tìm nhị phân tổng quát với giá trịN không giới hạn,
mà chúng ta sẽ tinh chế chương trình tìm nhị phânvới giá trị N = 1000.
Vềmặt khoa học, bài toán với giá trị N = 1000 có thể được xem là đặcbiệt nhưng trong
thực tế chúng lại thường xảy ra. Chẳng hạn: tìm kiếmmột mã số nhân viên trong một danh
sách mã số nhân viên được sắpthứ tự, trong đó, số lượng nhân viên của một công ty trong
đa sốtrường hợp thường nhỏ hơn 1000!
Phiênbản thứ nhất
ýtưởng cải tiến đầu tiên là giảm bớt số phép so sánh giữa X(phần tử cần tìm) với phần tử
giữa A[M]. Trong chương trình tổng quátở trên, ta nhận thấy rằng trong một vòng lặp, đôi
lúc cần phải thựchiện hai phép so sánh. Chương trình dưới đây sẽ cải thiện đượcđiều này.
L:= 0; R := N+1;
WHILE(L+1 <> N) DO
BEGIN
M:=(L+R) DIV 2;
IF (A[M] < X) THEN