Cắt mảng theo một tỉ lệ – Code bằng free pascal

Cắt mảng theo một tỉ lệ nào đó chẳng hạn tỉ lệ 1:1 tỉ lệ 2:1, hay cắt mảng để độ chênh lệch giữa tổng hai phần nhỏ nhất, …  là một bài toán về mảng một chiều rèn luyện cho ta được nhiều kĩ năng xử lý mảng, thông qua bài toán này các bạn học sinh được củng cố lại kĩ năng cộng dồn, kĩ năng truy vấn tới các phần tử của mảng một chiều. Hãy cùng học tập chia sẻ tìm hiểu bài toán cắt mảng sau nhé

Bài toán: Viết chương trình nhập vào mảng n số nguyên (n < 1000). Hãy cắt mảng thành 2 phần sao cho chênh lệch (giữa tổng các phần tử của hai phần) là nhỏ nhất

VD: Mảng cho:

5 4 6 1 1 7 6 9 9 12

Cắt thành 2 dãy đều có tổng bằng 30

5 4 6 1 1 7 6 9 9 12

 

Dữ liệu vào file: cut.inp Dữ liệu ra file: cut.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

– Dòng 1: chứa phần dãy 1

– Dòng 2: Chứa phần dãy 2

Bài toán cắt mảng này cũng có thể có rất nhiều ý tưởng để code, mình xin đưa ra một ý tưởng không tối ưu nhưng cực dễ hiểu và rất tin học như sau:

  • Mình sẽ dùng một biến để tính tổng tất cả các phần tử của mảng (S), một biến để cộng dồn các phần tử từ phần tử đầu tiên trở đi (S1)
  • Tiến hành cộng dồn đến đâu và kiểm tra độ lệch giữa hai mảng ngay đến đó, chỗ này ta hãy phân tích toán học một chút:
    Nếu độ dài mảng 1 là: S1 thì độ dài mảng 2 là: S – S1,
    như vậy độ lệch giữa hai mảng là GTTĐ((S – S1) – S1) = GTTĐ(S – 2*S1)
    Đầu tiên ta cho độ lệch Min = S và như vậy nếu độ lệch giữa hai mảng nhỏ hơn min thì đặt lại min
  • Cuối cùng Min sẽ chứa độ lệch nhỏ nhất, biến vt lưu lại vị trí cắt

Lưu ý: Bạn có thể tối ưu thuật toán thêm dựa vào nhận xét “Vị trí cắt sẽ loanh quanh S/2” nhé.

Bạn nhớ chạy chương trình để kiểm tra nhiều trường hợp để kiểm tra kết quả xem có chính xác không, đừng quên sinh test tự động để đỡ mất thời gian.

Trả lời

Email của bạn sẽ không được hiển thị công khai.

Back to top button