BÀI TẬP THỨ 3
DANH SÁCH BÀI TẬP THỨ 7 (16/01/2015) S ố hoàn hảo 2 Chồng gạch Tổng nguyên tố Nguyên tố - nguyên tố cùng nhau
Posts
Bài toán dãy tìm con liên tiếp
Thuật toán chia để trị: ta chia bài toán cần giải quyết thành nhiều bài toán con, giải quyết từng bài toán con, sau đó ta tổng hợp lại để giải bài toán lớn. Thuật toán chia để trị được biết đến tiêu biểu qua giải thuật merge-sort… Mặc dù nó được ứng dụng khá nhiều, nhưng nó không có một cách giải quyết tổng quát cho các bài toán. Ta phải hiểu tư tưởng của nó và áp dụng vào từng trường hợp cụ thể. Trong bài viết này, tôi sẽ trình bày một trường hợp áp dụng thuật toán chia để trị, tuy chỉ là một trường hợp áp dụng, nhưng dạng này ta gặp rất thường xuyên. Ta sẽ đi đi từ bài toán tổng quát, rồi áp dụng vào ví dụ cụ thể. Bài toán tổng quát : ta tìm một dãy con liên tiếp trong dãy đã cho để thỏa mãn một tính chất nào đó. Cách giải quyết : Thông thường với kích thước của dãy khoảng N=10^3, ta dùng hai vòng lặp chạy lồng nhau với độ phức tạp O(N^2) để xét tất cả dãy con và tìm ra dãy con phù hợp nhất. Khi N lớn hơn một chút, tầm khoảng N=10^5, ta phải có một giải thuậ...
Kỹ thuật xử lý BIT
Mọi số tự nhiên đều có thể biểu diễn được dưới dạng nhị phân. Đối với máy tính, các giá trị số được lưu bởi các biến dưới dạng chuỗi nhị phân có độ dài tương ứng với kiểu biến đó. Trong ngôn ngữ Pascal, một số kiểu phổ biến như: – byte : độ dài 8 BIT – integer : độ dài 2*8 = 16 BIT – longint : độ dài 4*8 = 32 BIT Các BIT của biến được đánh số từ phải sang trái bắt đầu từ 1. Ưu điểm của xử lý BIT: 1/ Bộ nhớ: Xử lý BIT có thể được dùng làm mảng đánh dấu. Thay vì sử dụng 1 biến Boolean chỉ đánh dấu được 1 phần tử là True hay False, ta có thể xử lý BIT để đánh dấu 8 BIT tương ứng với 8 phần tử. 2/ Tốc độ: Các phép xử lý BIT có tốc độ nhanh hơn các phép xử lý khác....
Kỹ thuật BITMASKS
BITMASKS Mình chắc chắn ai từng lập trình đều đã dùng kĩ thuật này, nhưng mọi người có thể gọi bằng những tên gọi khác nhau hoặc chẳng thèm gọi tên là gì. Ta bắt đầu làm rõ kĩ thuật này. Chẳng hạn ta có 3 bóng đèn. Mỗi bóng đèn có 2 trạng thái là bật hay tắt. Để biểu diễn trạng thái của 3 bóng đèn, ta có thể dùng một dãy có 3 phần tử để biểu diễn, ví dụ bool a[3] . Nếu số bóng đèn ít, ta có thể dùng một cách khác để biểu diễn: ta dùng duy nhất một số nguyên để biểu diễn chúng . Giả sử hai bóng đầu bật và bóng cuối tắt, ta có thể biểu diễn 110 (cơ số 2) = 6 (cơ số 10) . Như vậy với một số 6 ta có thể biết được trạng thái hiện tại của ba bóng đèn, tương tự 7 = 111 2 biểu diễn cả 3 bóng đều bật. Bitmask: Để biểu diễn trạng thái cho nhiều đối tượng, ta phải dùng nhiều biến để lưu lại trạng thái của chúng. Thay vào đó ta dùng duy nhất một biến để biểu trạng thái cho tất cả. Chắc chắn là bạn đã dùng kĩ thuật này rồi? Khi làm web, người ta cũng hay dùng...