HomeLập trình Scratch

Bài tập về dãy con trong pascal – Thường có mặt trong đề thi HSG tin học

Like Tweet Pin it Share Share Email
Like và share giúp mình phát triển website nhé.
  •  
  •  

Hôm nay mình giới thiệu với các bạn một số bài tập về dãy con trong pascal, đây là một trong những dạng bài tập hết sức cơ bản thường được chọn để ra trong đề thi HSG tin học.

Bài tập 1: Viết chương trình nhập vào mảng n số nguyên (n < 1000). Tìm dãy con đơn điệu giảm dài nhất (Dãy đơn điệu giảm là dãy chỉ gồm các phần tử giảm dần)

Có nhiều cách để giải quyết bài toán này, ở đây mình dùng kĩ thuật vét cạn để tìm ra dãy con thỏa điều kiện

Code tìm dãy con trong pascal

Ở trên các bạn có thể thấy mình sử dụng hai vòng lặp để quét tìm hết tất cả các đoạn từ i đến j-i sau đó sử dụng tiếp một vòng lặp for để kiểm tra xem đoạn đó có thỏa mãn điều kiện đầu bài không.

Chương trình viết ở trên do vét hết các trường hợp nên không tối ưu lắm nhưng dễ hiểu.

Bài tập trên có thể biến tấu để trở thành nhiều bài toán khác chẳng hạn:

Bài tập 2: Tìm dãy con đơn điệu tăng dài nhất 

Bài tập 3: Tìm dãy con gồm toàn số lẻ (chẵn) dài nhất 

Hay trong đề thi tin học trẻ tỉnh Bắc Giang 2014 có bài như sau:

Bài tập 4: Tìm dãy con có độ dài lớn nhất chia hết cho K.

Thực ra với dạng bài toán này các bạn chỉ cần nắm vững thuật toán trên sau đó chỉ cần thay đổi điều kiện kiểm tra một chút là ra thôi.

Các bạn để ý mình chỉ thay dòng lệnh số 7 để đọc thêm số k, và dòng lệnh số 17 để kiểm tra các số trong dãy đều chia hết cho k vậy là đã giải quyết xong bài toán.

À mà mình lười sửa lại khai báo kiểu dữ liệu và tên tệp tin nhập xuất cho giống với đề bài các bạn tự điều chỉnh lại cho phù hợp.

Như vậy các bạn thấy đó chỉ cần nắm vững một thuật toán tìm dãy con là ta có thể biến hóa để giải quyết những dạng bài tập tương tự. Vì vậy các bạn hãy nắm thật vững những bài toán cơ bản nhé.

Bạn nào có thuật toán tối ưu hơn để giải quyết dạng toán này vui lòng chia sẻ để các bạn cùng học hỏi.

 

Comments (1)

Trả lời

Your email address will not be published. Required fields are marked *