Các bài toán có dữ liệu vào rất lớn, thường gây cho ta rất nhiều khó khăn. Để giải được
các bài toán đó thì cần phải tìm cấu trúc dữ liệu và giải thuật thật hợp lý. Đa số các bài
toán dạng này thì phải vừa đọc vừa xử lý. Lấy ví dụ bài toán đơn giản sau:
Bài toán: Tìm dòng đặc biệt
Cho một tệp văn bản có n dòng (n <=100000) mỗi dòng có độ dài không quá 255 ký tự..
Trong đó có một dòng chỉ xuất hiện một lần duy nhất, còn các dòng còn lại có số lần
xuất hiện là một số chẵn. Bạn hãy lập trình để chỉ ra dòng đặc biệt đó.
Dữ liệu vào: tệp dacbiet.inp
- Ghi các dòng thông tin và kết thúc tệp bởi 1 dòng có 3 ký tự ###
Dữ liệu ra: tệp dacbiet.out
- Ghi ra dòng đặc biệt tìm được
Ex:
Giải: Với dữ liệu vào rất lớn n <=10000 thì giải thuật đơn giản nhất là cứ đọc một dòng
bất kỳ sau đó so sánh với các dòng tiếp, nếu không thấy xuất hiê.n quá 1 lần thì nó chính
là dòng đặc biệt, ngược lại thì thực hiện với dòng kế tiếp. Nhưng nếu dòng đặc biệtt đó là
dòng cuối cùng thì số lần đọc tệp sẽ rất nhiều nên thời gian chạy chương trình cũng rất
lâu. Mặt khác ta không thể lưu trữ vào mảng đượcc nên ta phải vừa đọc, vừa xử lý.
Thuật toán: sử dụng phép XOR. Như ta đã biết:
Dựa vào tính: Nếu A xor B với số lần thực hiện là số chẵn thì cho ta A nên ta có thuật
toán để giải bài này như sau:
- Dùng một mảng a[1..255] of byte để lưu mã ASCII của các ký tự của dòng
đặc biệt
- Đọc một dòng S vào và gán a[i]:=a[i] xor ord(s[i]) (i chạy từ 1 đến
length(s))
- Viết ra dòng đặc biệt
Chương trình:
Program dong_dac_biet;
Const
fi = 'dacbiet.inp';
fo = 'dacbiet.out';
maxn = 255;
Var
a : array[1..maxn] of byte;
i : integer;
s : String;
f : Text;
Procedure Init;
Begin
Fillchar(a,sizeof(a),0);
Assign(f,fi);
Reset(f);
End;
Procedure Main;
Begin
While not eof(f) do
begin
Readln(f,s);
If s='###' then exit;
For i:=1 to length(s) do a[i]:=a[i] xor ord(s[i]);
end;
End;
Procedure Done;
Begin
Close(f);
Assign(f,fo);
Rewrite(f);
For i:=1 to maxn do
if a[i]<>0 then write(f,chr(a[i]));
Close(f);
End;
BEGIN
Init;
Main;
Done;
END.
Thuật toán này độ phức tạp chỉ có N nên chương trình chạy rất nhanh. Ngoài ra
bài này còn có một thuật toán nữa, không sử dụng phép xor nhưng phải dùng mảng 2
chiều kích thước 255*255. Bạn đọc muốn có chương trình này xin liên hệ với toà soạn
hoặc với tác giả.
Bài tập: Các bạn có thể làm bài số 1 trong đề thi quốc gia 2001 (Bảng B)
Cấp số cộng
Cho một tệp văn bản gồm N (N rất lớn) số nguyên a1, a2, a3,..., an ; với ai <=30000.
Hãy tìm trong dãy a đó mô.t dãy con dài nhất lâ.p thành mô.t dãy cấp số cô.ng.
Dữ liệu vào: CAP.INP
- Dòng đầu ghi số N
- N dòng tiếp ghi các số ứng với dãy A
Dữ liệu ra: CAP.OUT
- Dòng đầu ghi số M là phần tử và công sai của dãy cấp số cộng đó
- M dòng tiếp theo ghi số chỉ số của các số thuộc cấp số cộng.