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.

- Đôi khi chúng ta có thể kết hợp giữa việc lập chương trình và kết hợp sinh ra các dữ liệu
bằng tay để công việc trở nên đơn giản hơn và sẽ ấn định được những dữ liệu theo ý muốn.
- Đối với học sinh khi làm bài có thể (thường) phải làm chương trình sinh dữ liệu và sinh
sẵn các file dữ liệu trước khi bắt tay làm chương trình chính, dữ liệu dùng để chạy và kiểm
tra kịp thời, hoàn thiện chương trình của mình.. Nếu bài nào làm chương trình sinh mất quá
nhiều thời gian thì có thể làm chương trình sinh đơn giản, tương đối, không cần thật đầy đủ
sau đó có thể sửa thêm bằng tay, tránh mất quá nhiều thời gian làm chương trình sinh trong
khi làm bài thi.
Dưới đây trình bày việc sinh dữ liệu trong ngôn ngữ lập trình TURBO PASCAL:
Trong Turbo Pascal có cung cấp các hàm và thủ tục giúp cho việc sinh ngẫu nhiên:
- Thủ tục RANDOMIZE: khởi tạo cho việc lấy ngẫu nhiên.
- Hàm RANDOM(N): cho ngẫu nhiên một số nguyên trong khoảng từ 0 đến (N-1), trong
đó N nguyên dương có kiểu WORD.
- Hàm RANDOM: cho một số thực ngẫu nhiên trong khoảng (0,1).
Ta thấy hàm RANDOM(N) chỉ sinh được các số nguyên không âm trong phạm vi kiểu
word. Vì vậy:
- Muốn sinh số âm ta phải dùng thủ thuật, ví dụ có thể dùng lệnh: if random(2)=0 then
x:= - random(max) Có thể điều chỉnh được tỷ lệ số âm được sinh ra khoảng độ 20% bằng
lệnh: if random(100) < 20 then x:= - random(max);
- Muốn sinh số lớn hơn phạm vi word, ta có thể dùng thêm các phép +, * để nâng giá trị
lên, chẳng hạn: x := y*random(max). (khi đó x, y khai kiểu longint, max là 1 giá trị
nguyên dương được chọn trước)
- Muốn sinh số thực, ta có thể dùng hàm random chẳng hạn: x:= y*random, hoặc sinh tử
số và sinh mẫu số(khác 0) là số nguyên rồi chia cho nhau…
- Muốn sinh ngẫu nhiên được các dữ liệu không phải dạng số thì chúng ta cấn làm các
phép chuyển đổi, thiết đặt mối quan hệ nào đó giữa các số với dữ liệu cần sinh, chẳng hạn
muốn sinh các kí tự A,B,… ta thiết đặt quan hệ: nếu sinh được số 1 thì ghi ra A, số 2 thì
ghi B…
III. Một số ví dụ:
Sinh ma trận trọng số của đồ thị vô hướng:

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);

END.
Sinh ma trận kề cho đồ thị có hướng còn đơn giản hơn vì không cần điều kiện ma trận là
đối xứng, khi đó mỗi lần ta có thể lấy ngẫu nhiên một số rồi ghi ngay vào file bằng lệnh:
write(f, random(2): 2).
2. Sinh xâu ký tự:
Chương trình sau sinh ngẫu nhiên xâu ký tự chỉ gồm các ký tự từ ’A’..’Z’ và ’a’..’z’.
PROGRAM Sinh_Xau_Ky_Tu;
uses crt;
const
finp = ’STRING.INP’;
var
n,i : integer;
st : string;
ch : char;
f : text;
BEGIN
clrscr;
randomize;
assign(f,finp); rewrite(f);
write(’Cho do dai cua xau : N = ’); readln(N);
st:=’’;
for ch:=’A’ to ’Z’ do st:=st+ch;
for ch:=’a’ to ’z’ do st:=st+ch;
for i:=1 to N do write(f, st[random(52)+1]);
close(f);
END.
3. Sinh dữ liệu cho bài Hướng đi (thi HSG Quốc Gia bảng B năm 2003):
Tóm tắt lại bài toán: Rô bốt di chuyển theo lệnh: L(rẽ trái 90
0
và đi theo hướng đó 1 đơn

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;

begin
top:=0;
for i:=j to k-1 do
begin
if s[i]=’(’ then inc(top)
else
if s[i]=’)’ then
begin
dec(top);
if top<0 then begin ok:=false; exit; end;
end;
end;
ok:= (top = 0);
end;
BEGIN
clrscr;
randomize;
s:=’’;
write(’Cho so ki tu: ’ ); readln(N);
for i:=1 to n do s := s + ch[random(3)];
ss:=s;
socap:= 1 + random(length(ss) );
for i:=1 to socap do
begin
repeat
j:= 1+random(length(s)-3);
k:= j + 2 + random(length(s)-j-1);
until ok(j, k);
insert( ’)’, s, k);
insert(’(’, s, j);

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

begin
x:= 2 + random(maxso-1);
str(x, st);
insert(st, s, i);
i:=i+length(st)+1;
if length(s)>200 then
begin
writeln(’Dai > 200 ki tu ! Hay sinh lai ’);
readln; halt;
end;
end
else inc(i);
end;
i:= 1+random(4);
assign(f, fi) ; rewrite(f);
writeln(f,huong[i]);
writeln(f, s);
close(f);