Kỹ thuật sử dụng mảng đánh dấu để tỉa mảng trong Pascal

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

  1. Xóa bỏ những số nguyên tố trong mảng một chiều
  2. Tìm và loại bỏ những số chính phương trong mảng
  3. Xuất ra những số trong mảng chia hết cho 3
  4. 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 “

Mảng đánh dấu các số nguyên tố

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

Bây giờ rõ ràng ta chỉ cần xuất những phần tử của mảng a mà phần tử của mảng d (cùng chỉ số) có giá trị là 0. Với cách làm này ta cũng biết ngay được vị trí của các phần tử là số nguyên tố bị loại đi nhờ mảng d phải không nào.

Cách viết chương trình sử dụng kỹ thuật mảng đánh dấu

Để viết chương trình sử dụng mảng đánh dấu để loại bỏ những phần tử thỏa mãn điều kiện nào đó trong mảng một chiều ta có thể sử dụng cấu trúc chung như sau:

  • Viết hàm xác định xem phần tử có bị loại hay không
  • Duyệt qua tất cả các phần tử của mảng, nếu phần tử thỏa điều kiện loại thì đánh dấu

Bây giờ các bạn hãy áp dụng kĩ thuật này để viết chương trình thực hiện 4 bài tập ở đầu bài viết coi nào. Bạn nào có kĩ thuật nào hay vui lòng chia sẽ để các bạn cùng học hỏi.

Share this post:

Related Posts

Leave a Comment