HomeLập trình pascal

Tìm dãy con thỏa mãn điều kiện – code bằng pascal

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

Trong những bài toán về mảng một chiều thì bài toán tìm dãy con thỏa mãn điều kiện nào đó là một bài toán tương đối hay, thường được chọn làm bài cấp độ 2 trong đề thi học sinh giỏi tin học vòng huyện hay vòng tỉnh. Dạng bài toán này đòi hỏi học sinh khi lập trình phải có kĩ năng tương đối thành thạo trong việc xử lí mảng một chiều. Xin giới thiệu với các bạn một trong những bài toán dạng này:

Bài toán: 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)

Dữ liệu vào file: day_con.inp Dữ liệu ra file: day_con.out
– Dòng 1: chứa số n

– Dòng 2 chứa n số cách nhau ít nhất 1 khoảng trắng

Chứa dãy con dài nhất

 

VD: n = 11

2 ; 7 ; 5 ; 8 ; 6 ; 4 ; 12 ; 8 ; 7 ; -4 ; 6

Kết quả: 12 ; 8 ; 7 ; -4
Ý tưởng: Tìm tất cả các dãy đơn điệu giảm và chọn ra dãy dài nhất:

[2]; [7 ; 5 ]; [8 ; 6 ; 4] ; [12 ; 8 ; 7 ; -4] ; [6]

–  Dùng 1 biến lưu vị trí đầu tiên của các dãy đơn điệu giảm

– 1 biến đếm số phần tử của các dãy giảm

– 1 biến lưu độ dài dãy giảm lớn nhất

– 1 biến để đánh dấu vị trí đầu tiên của dãy dài nhất khi được chọn (biết vị trí đầu tiên và số phần tử sẽ biết được dãy từ đâu tới đâu)

Trên đây là một ý tưởng của mình để giải quyết bài toán Tìm dãy con đơn điệu giảm dài nhất, bài toán này có rất nhiều cách giải quyết, nhưng mình chọn cách viết như trên bởi nó chỉ đơn thuần sử dụng những kĩ thuật thông thường trong xử lý mảng một chiều.

Chú ý: Bài toán có thể thay cách hỏi (tìm dãy giảm dài nhất, tìm dãy không tăng dài nhất, dãy các số âm (dương) dài nhất, …)

Mình nghĩ đây là một bài toán hay tương đương với bài toán tỉa mảng một chiều trong pascal các bạn nên nắm vững thuật toán để chủ động khi gặp phải.

Code Tìm dãy con đơn điệu giảm dài nhất  bằng Pascal

Comments (2)

Trả lời

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