Tính toán trước khi lập trình
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (122.13 KB, 5 trang )
Tính toán trước khi lập trình
Nguyễn Duy Hàm
Trong một bài viết trên tạp chí Tin học và Nhà trường Thầy Nguyễn Xuân Huy đã nói về
vấn đề đặt bút tính toán trước khi lập trình, Thầy đề cập đến bài toán đếm số ô vuông đơn
vị bị cắt bởi 1 đường chéo của 1 hình chữ nhật có kích thước nxm. Qua đó chúng ta có thể
phần nào hiểu được rằng việc tính toán, phân tích bài toán trước khi lập trình là vô cùng
cần thiết, trong nhiều kì thi học sinh, sinh viên giỏi tin học có những bài toán tưởng chừng
rất dễ, song nếu không được tiền xử lý tốt thì chỉ có thể vượt qua một vài test dễ ban đầu
của BGK mà thôi. Lần này tôi cũng xin mạn phép được bàn về cùng vấn đề trong một bài
toán khác, đó là một bài số 3 trong đề thi của khối chuyên tại kì thi OLIMPIC Tin học Sinh
viên Việt Nam 2005 tại Đại học Khoa học Tự nhiên TP.Hồ Chí Minh vừa qua.
Bài toán
Một hệ thống giao thông gồm N nút (các nút được đánh số từ 1 đến N), trong đó bất kỳ hai
nút nào cũng có đoạn đường hai chiều nối chúng. Ta gọi đường đi giữa hai nút là dãy các
đoạn đường kế tiếp nhau, bắt đầu từ một nút và kết thúc tại nút kia, trong đó không có nút
nào trên đường đi được lặp lại.
Yêu cầu: Cần đếm tất cả các đường đi khác nhau giữa hai nút bất kỳ của mạng giao thông
đã cho.
Ví dụ: Với hệ thống giao thông 4 nút trong hình 1, ta có 5 đường đi nối giữa hai nút tô đen
(xem hình 2).
Dữ liệu: Nhập từ file văn bản PCOUNT.INP gồm một số nguyên dương N (N
Kết quả: Ghi ra file PCOUNT.OUT gồm 1 dòng chứa số các đường đi khác nhau đếm
được.
Ví dụ:
Khi đọc bài toán này không ít bạn đã rất loay hoay, không biết phải làm thế nào, nhiều bạn
đã sử dụng ngay đệ quy quay lui để duyệt tất cả các đường đi có thể từ đỉnh đầu đến đỉnh
cuối trên 1 đồ thị ngầm định được xây dựng, vì cứ nói đến hệ thống giao thông là nhiều
người nghĩ ngay tới cấu trúc đồ thị, với cách làm này chương trình không thể vượt qua test
với n>15! (cần chú ý là bài toán này hạn chế thời gian chạy là 1 giây), nên việc duyệt như
trên sẽ là một giải pháp khó có thể chấp nhận. Ta hãy cùng nhau phân tích bài toán
Cách giải quyết
Thuật toán:
Ta dễ thấy rằng: tổng các đường đi từ 2 đỉnh bất kì là tổng các đường đi có độ dài =1, các
đường đi có độ dài =2, các đường đi có độ dài =3…,các đường đi có độ dài n-1. Cũng
chính là tổng các đường đi không đi qua đỉnh trung gian nào, đi qua 1 đỉnh trung gian, qua
2 đỉnh trung gian,…qua n-2 đỉnh trung gian.
Tổng các đường đi không đi qua đỉnh trung gian nào là 1 (chính là đường nối trược tiếp 2
dỉnh đó). Tổng các đường đi đi qua 1 đỉnh trung gian là số cách chọn có thứ tự 1 đỉnh
trong số n-2 đỉnh còn lại (A
1
n-2
), tổng các đường đi qua 2 đỉnh trung gian là số cách chọn có
thứ tự 2 đỉnh trong số n-2 đỉnh còn lại (A
2
n-2
), tổng các đường đi qua 3 đỉnh trung gian là số
cách chọn có tứ tự 3 đỉnh trên n-2 đỉnh còn lại (A
3
n-2
).
Như vậy:
S=1+A
1
n-2
+ A
2
n-2
+ A
3
n-2
+…+A
n-2
n-2
.(1)
(1)=1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n-2)!(2)
(2)=1+(n-2)[1+(n-3)[1+(n-4)[…[1+1]…]]].(3)
(3)=((..(1+1)2+1)3+1)4+1)5+1)…(n-3)+1)(n-2)+1(4)
Như vậy từ công thức (4) ta có thuật toán theo đoạn mã sau:
s:=1;
For i:=1 to n-2 do
Begin
s:=s*i;
s:=s+1;
End;
Cấu trúc dữ liệu:
Qua công thức trên ta thấy S là một số rất lớn (với n=1000 thì S có tới 2563 chữ số), không
có kiểu số nào có thể lưu trữ được, ta phải sử dụng kiểu dữ liệu khác. Tốt nhất trong
trường hợp này ta nên sử dụng mảng kiểu longint, với mỗi phần tử mảng sẽ lưu 1 số có 6
chữ số của chữ số S.
Để đơn giản trong xử lý ta nên lưu ngược, a[1] sẽ chứa 6 chữ số cuối cùng của S, a[2] sẽ
chứa 6 chữ số tiếp theo…
Ví dụ s=1234031809283756.
Thì ta có mảng A như sau: a[1] = 283756; a[2]=031809; a[3]=001234;
Nhưng thực tế a[2] = 31809 và a[3]=1234(loại bỏ các số 0 ở đầu trái), vậy khi ghi kết quả
ra file ta phải xử lý thêm chỗ này để đạt được kết quả đúng (thêm 0 vào trước cho đủ 6 chữ
số rồi mới ghi ra file). Bây giờ vấn đề còn lại là lập trình. Chúng ta cùng theo dõi đoạn mã
sau:
Chương trình
Const stout='PCOUNT.OUT';
stinp='PCOUNT.INP';
k=1000000;
d=6;
Var i,j,n,m,l,nho:longint;
s:string;
f:text;
ok:boolean;
a:array[1..500]of longint;//mảng chứa dãy số
Procedure Khoi_tao;
Begin
assign(f,stinp);
reset(f);
read(f,n);
close(f);
a[1]:=1;m:=1;
End;
Procedure Thuc_hien;
Begin
for i:=1 to n-2 do
begin
nho:=0;
for j:= 1 to m do
begin
nho:=nhơa[j]*i;
a[j]:=nho mod k;
nho:=nho div k ;
end;
if nho>0 then
begin
m:=m+1;
a[m]:=nho;
end;
nho:=1;ok:=true;j:=0;
while ok do
begin
j:=j+1;
nho:=a[j]+nho;
a[j]:=nho mod k;
nho:=nho div k;
if nho=0 then ok:=false;
end;
if j>m then m:=j;
end;
end;
Procedure In_ra;
Begin
assign(f,stout);
rewrite(f);
if n>1 then
begin
for i:=m downto 1 do
begin
str(a[i],s);
if i< br>begin
l:=length(s);
while l< br> begin
insert('0',s,1);
l:=l+1;
end;
end;
write(f,s);
end;
end
else write(f,’0’);
close(f);
End;
Begin
Khoi_tao;
Thuc_hien;
In_ra;
End.
Chú ý khi lập trình
- Không sử dụng các thủ tục inc(),dec() làm chậm chương trình.
- Trong chương trình có đoạn mã thêm số 0 vào trước các phần tử của mảng trước khi ghi
lên file, không nên viết như sau mặc dù nó gọn hơn:
While length(s) < d do insert(‘0’,s,1); vì nó sẽ gọi hàm length(s) liên tục mỗi khi kiểm tra
làm chậm chương trình của chúng ta.
Kết luận
Cuối cùng ta thấy rằng bài toán này không phức tạp, không đòi hỏi phải tư duy thuật toán
cao siêu, chỉ cần nắm vững kiến thức toán tổ hợp, biết cách xử lý trên số lớn, cùng với việc
tính toán phân tích kĩ bài toán trước để tìm ra công thức đơn giản nhất, sao cho phép toán
thực hiện là ít nhất sẽ đảm bảo chương trình chạy nhanh nhất!
Qua phần trình bày trên ta có thể thấy được sự liên quan mật thiết giữa toán học và tin học
như thế nào, việc tính toán, phân tích kĩ bài toán, việc sử dụng thành thạo cấu trúc dữ liệu
quan trọng như thế nào trong việc giải 1 bài toán trong tin học. Mọi góp ý, trao đổi xin gửi
về Xin cảm ơn!
