Sinh dữ liệu vào cho các bài toán
Nguyễn Trịnh Đoàn
Khi lập trình giải một bài toán trong Tin học thì việc kiểm tra chương trình là một việc hết
sức quan trọng, khi làm bài thi thí sinh muốn đạt được điểm cao thì chương trình của mình
phải chạy tốt được các bộ dữ liệu vào của bài toán mà người chấm bài đưa ra. Vì vậy
người làm bài và người chấm bài cần phải biết tạo ra được các bộ dữ liệu vào (hay còn
gọi là bộ test) để kiểm tra chương trình.
I. Các yêu cầu đối với các bộ dữ liệu vào của bài toán Tin học:
- Các dữ liệu cần khách quan, ngẫu nhiên, đa dạng, có những bộ xét trường hợp tổng quát,
nhưng cũng có bộ xét tới các trường hợp riêng đặc biệt hoặc suy biến của bài toán. Tổng
hợp lại thì các bộ dữ liệu cần xét đầy đủ các khả năng các trường hợp của bài toán. Tránh
tình trạng chương trình "vô tình " chạy đúng một số bộ dữ liệu nào đó nhưng thực ra giải
thuật và tổ chức cài đặt chương trình lại chưa đúng, chưa tốt nên khi chạy các bộ dữ liệu
khác thì bị sai.
- Kích thước các bộ dữ liệu cần có từ nhỏ đến lớn, phải có các bộ với kích thước lớn nhất
như giới hạn của đề bài. Kích thước dữ liệu cần quan tâm hai khía cạnh: Số lượng phần tử
và giá trị các phần tử dữ liệu.
- Bộ dữ liệu phải kiểm tra được tính đúng đắn và tốc độ chạy của chương trình: Cần có
một số bộ (thường kích thước nhỏ) để người lập trình dễ kiểm tra được tính đúng của
chương trình đồng thời cần có một số bộ (thường kích thước lớn) để kiểm tra tốc độ chạy
của chương trình qua đó đánh giá được độ phức tạp thời gian của giải thuật.
- Cần có một số bộ dữ liệu lớn hoặc đặc biệt để kiểm tra khả năng tổ chức dữ liệu, tổ chức
bộ nhớ của người lập trình.
- Tóm lại các bộ dữ liệu phải cho phép dùng để kiểm tra được các đặc trưng cơ bản của
một thuật toán tốt.
II. Phương pháp sinh dữ liệu:
- Với những bộ dữ liệu có kích thước nhỏ, chúng ta có thể soạn các trực tiếp từ bàn phím
nhờ hệ soạn thảo của ngôn ngữ lập trình. Còn với những bài toán có kích thước lớn, nếu
nhập dữ liệu từ bàn phím sẽ rất mất thời gian và nhiều khi không thể thực hiện được ví dụ
như cho một dãy số có hàng vạn phần tử hoặc những dữ liệu phức tạp đòi hỏi tính hợp
lệ…, vì vậy chúng ta cần phải lập các chương trình để sinh ra các dữ liệu.

Các giá trị là nguyên (gồm cả số âm) có giá trị tuyệt đối nhỏ hơn hoặc bằng 30000.
PROGRAM Sinh_Do_Thi_Vo_Huong;
uses crt;
const
max = 30001;
maxN = 100;
finp = ’DOTHI.INP’;
var
N,i,j : integer;
a : array[1..maxN, 1..maxN] of Integer;
f : text;
BEGIN
clrscr;
randomize;
assign(f,finp); rewrite(f);
write(’N = ’); readln(N);
writeln(f,N);
for i:=1 to N-1 do
for j:=i+1 to N do
begin
a[i,j]:= random(max);
if random(2)=0 then a[i, j]:= - a[i, j];
a[j,i]:=a[i,j];
end;
for i:=1 to N do
begin
for j:=1 to N do write(f,a[i,j]: 7);
writeln(f);
end;
close(f);

vị), R (rẽ phải 90
0
và đi theo hướng đó 1 đơn vị), C (đi thẳng theo hướng hiện tại 1 đơn vị).
Đường đi của Rô bốt là một xâu nén S: nếu 1 kí tự lặp lại nhiều lần liên tiếp thì nó được
ghi 1 lần với hệ số lặp ở trước, nếu nhóm kí tự lặp lại nhiều lần liên tiếp thì nó được đặt
trong dấu ngoặc tròn với hệ số lặp ở trước.
Biết hướng ban đầu của Rô bốt (E-Đông, W-Tây, S-Nam, N-Bắc) và xâu S mô tả đường
đi. Tìm hướng của Rô bốt khi thực hiện xong dãy lệnh. Dữ liệu vào file văn bản
WHATDIR.INP: dòng đầu chứa một kí tự cho biết hướng ban đầu của Rô bốt, dòng 2 chứa
xâu S mô tả đường đi. Kết quả đưa ra file văn bản WHATDIR.OUT một kí tự duy nhất cho
biết hướng của Rô bốt.
Ví dụ: File WHATDIR.INP :
S
23(L8(30(R30R))L10(20(8(L29C))L))10C17L18C
PROGRAM Sinh_DL_Bai_1_2003;
uses crt;
const fi =’WHATDIR.INP’;
maxso = 999;
maxs = 255;
ngoac= [’(’, ’)’] ;
taplenh = [’L’,’R’,’C’];
tapso =[’0’..’9’];
ch: array[0..2] of char = (’L’,’R’,’C’ );
Huong: string= ’NESW’;
var s, st ,ss: string[maxs];
f: text;
i, j, k, u ,n, x, solenhdon, socap,sm,sd : integer;
ok1: boolean;
function ok(j, k: integer): boolean;
var i, top: integer;

if length(s)>200 then
begin
writeln(’Dai > 200 ki tu ! Hay sinh lai ’);
readln; halt;
end;
end;
solenhdon:= 1 + random(length(ss) - 1);
for i:=1 to solenhdon do
begin
x:= 2 + random(maxso-1);
str(x, st);
repeat
ok1:=false;
j:=1+random(length(s));
if (s[j] in taplenh) and (not (s[j-1] in tapso)) then
begin
insert(st, s, j);
ok1:=true;
if length(s)>200 then
begin
writeln(’Dai > 200 ki tu ! Hay sinh lai ’);
readln; halt;
end;
end;
until ok1;
end;
i:=1;
while i < length(s) do
begin
if s[i] = ’(’ then