Trong quá trình giải quyết các bài toán ôn thi HSG pascal các bạn rất hay gặp những bài toán liên quan đến tỉa mảng chẳng hạn
- Xóa bỏ những số nguyên tố trong mảng một chiều
- Tìm và loại bỏ những số chính phương trong mảng
- Xuất ra những số trong mảng chia hết cho 3
- Loại bỏ những phần tử trùng nhau trong mảng, mỗi phần tử chỉ xuất hiện một lần
Có nhiều cách để giải quyết các bài toán dạng này. Cách mà các bạn hay dùng đó là tìm phần tử cần loại bỏ sau đó loại nó đi bằng cách dồn các phần tử của mảng phía sau phần tử loại đi lên.
Tuy nhiên cách làm trên thường làm mất vị trí của mảng ban đầu do các phần tử bị dồn lại.
Mình chia sẻ với các bạn một cách làm khác đó là kỹ thuật dùng mảng đánh dấu để đánh đấu những phần tử cần loại và sau đó chỉ xuất ra những phần tử không được đánh dấu.
Minh họa kỹ thuật sử dụng mảng đánh dấu
Để cho dễ hiểu mình sẽ minh họa cho bài tập sau:
“Viết chương trình loại bỏ những số nguyên tố trong mảng n phần tử, xuất ra kết quả là mảng sau khi đã bỏ đi các số nguyên tố và vị trí của các số nguyên tố đã bị bỏ đi trong mảng ban đầu “
Ta lấy ví dụ có dãy số được lưu trong mảng a như trên, trong đó có 2 số nguyên tố là 2 và 5
Ta sử dụng một mảng đánh dấu d mà các phần tử chỉ nhận hai giá trị 0 hay 1 (các bạn cũng có thể chọn kiểu dữ liệu cho mảng đánh dấu này là boolean chỉ nhận hai giá trị true và false cho tiết kiệm bộ nhớ)
- Đầu tiên cho cho tất các các phần tử của mảng đánh dấu d nhận giá trị 0
- Ta duyệt từng phần từ của mảng a nếu phần tử nào là số nguyên tố thì gán giá trị là 1
như vậy sau khi duyệt xong ta được kết quả như hình trên
