Thuật toán quy hoạch động với dữ liệu lớn

Qui hoạch động với các bài toán có dữ liệu lớn

Cao Minh Anh

Như chúng ta đã biết khi giải một bài toán thì vấn đễ thời gian và dữ liệu là cốt lõi. Vì thế

trong các kì thi chúng ta thường gặp các bài có dữ liệu lớn. Những bài nay thường rất khó

bởi vì ta vừa phải giải quyết vấn đề dữ liệu, vừa phải giải quyết vấn đề thời gian. Vì thế

khi có được một thuật toán hay tối ưu vẫn chưa chắc giải được những bài này, tối ưu chưa

đủ mà cần phải có phương pháp cài đặt tốt để có thể giải quyết về mặt dữ liệu. Quy hoạch

động tượng trưng cho sự tối ưu hoá về thời gian vì thế tôi xin trình bày một số bài toán dữ

liệu lớn dùng quy hoạch động đễ giải và cách thức xử lý của từng bài toán.

Bài 1: Tìm số lớn nhất.

Cho n số nguyên (n<=232) trong file max.inp, hãy tìm số lớn nhất trong n số nguyên đã

cho. Kết quả được viết vào file max.out gồm 2 số M, P − trong đó M là số lớn nhất và P là

vị trí của nó trong n số nguyên. Nếu có nhiều kết quả đưa ra số lớn nhất có vị trí lớn nhất.

Ví dụ:

Đây là một bài quy hoạch động rất đơn giản, tôi muốn đề cập để các bạn thấy rằng bài toán

tìm max là một bài toán rất cơ bản, ai học cũng biết bài toán này nhưng chắc các bạn sẽ

không nghĩ rằng đây là một bài toán qui hoạch động đơn giản mà ai cũng có thể làm được.

Tôi muốn giới thiệu với các bạn bài toán tìm max với dữ liệu lớn dùng file để chứa các

phần tử thay vì dùng mảng, như thế ta vừa tiết kiệm được dữ liệu vừa giải quyết bài toán

nhanh nhất.

uses crt;

const

fi=’max.inp’;

go=’max.out’;

var max,n,k :longint;

f,g :text;