Đệ quy quay lùi mảng hai chiều
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 (89.66 KB, 5 trang )
Đệ quy quay lui trên mảng 2 chiều và kỹ năng cài đặt
Trương Thị Thu Hường
Duyệt đệ quy là một trong những chiến lược đểgiải quyết nhiều bài toán, đặc biệt là các bài
toán đòi hỏi liệtkê mọi cấu hình thoả mãn. Thuật toán đệ quy và các vần đề xungquanh đệ
quy đã được nhiều tác giả đề cập đến. Trong bài viết này,tôi cũng sẽ trở lại với chủ đề đệ
quy, nhưng là đệ quy quay luitrên mảng hai chiều và kỹ năng cài đặt thông qua một số bài
toán cụthể.
Yếu tố mấuchốt trong một thủ tục đệ quy là điều kiện duyệt và điểm dừng. Vớiđặc trưng
của mảng hai chiều là phần tử mảng được xác định bằnghai giá trị hàng và cột, thông
thường chúng ta vẫn sử dụng cặp giátrị (i,j) (hàng, cột của 1 ô) làm bướcduyệt khi gọi thủ
tục đệ quy.
Một số bàitoán như: tìm đường đi từ ô (i
0
, j
0
) đến ô (i
k
,j
k
) với 4 khả năng đi tới các ô chung
cạnh như bài toán Mãđi tuần đã rất quen thuộc với chúng ta. Mặt khác, các bài toán sửdụng
thuật giải này đều có điều kiện duyệt hay điểm dừng khá rõràng và việc trả lại giá trị cũng
không quá phức tạp nên các bạnsẽ dễ dàng cài đặt được. Sau đây, tôi muốn giới thiệu với
các bạnmột bài toán được giải quyết theo phương pháp duyệt đệ quy quaylui, nhưng trong
khi cài đặt chúng ta cũng có đôi điều cần lưu ý.
Bài toán:
ở một nướcnọ do các đội bóng đá thiếu tinh thần thi đấu nên số trận hoà rấtnhiều. Ban tổ
chức quyết định thay đổi luật để kích thích các độithi đấu tích cực hơn. Giải sẽ tổ chức thi
đấu vòng tròn nghĩa làmỗi đội đều phải thi đấu với tất cả các đội khác đúng một trận.Nếu
hoà, cả hai đội đều bị 0 điểm. Đội thắng sẽ được 3 điểm vàđội thua cũng được 1 điểm. Do
sơ xuất của ban tổ chức, bảng kếtquả thi đấu của tất cả các đội đã bị nhoè, một số chỗ
không đọc được. Bạn hãy giúp ban tổ chức khôiphục lại những thông tin đã mất. Số đội
bóng của giải này là N (N≤20). Bằng kết quả cho bởi mảng số nguyên A[1..N,1..N+1]
trong đó A[i,j]bằng số điểm đội i đạt được trong trận thi đấu với đội j.A[i,N+1] bằng tổng
số điểm của đội i trong toàn giải. Quy ướcA[i,i]=0.
Dữ liệu vàocho trong file văn bản với tên INP.TXT. Dòng đầu là số đội bóng N; Ndòng
tiếp theo là bảng giá trị, những ô bị nhoè được cho bởi giátrị −1.
Dữ liệuđưa ra file văn bản OUT.TXT, liệt kê mọi khả năng có thẻ. Mỗi khả năngcách nhau
một dòng trắng.
Thuật giải:
Chúng ta nhậnthấy bài toán yêu cầu đưa ra mọi cấu hình thoả mãn nên duyệt mọikhả năng
là phương pháp thường được sử dụng. Giả sử sau khi đã khôi phục các thông tin có thẻ, số
ô trốngcòn lại là m ô (trừ ô trống là ô tổng, vì giá trị ô tổng phụ thuộcvào các ô cùng hàng
đó). Từ đó suy ra số khả năng là: 3
m/2
(mỗi ô bịnhoè có khả năng nhận 3 giá trị). Các yếu tố
chính trong thủ tục đệ quy như sau:
Điểm dừng: Mảng A đã được khôi phục đầy đủ có dữ liệu mảng phù hợp đầuvào.
Kết thúc: Khi đã duyệt mọi khả năng hoặc đã đạt đến một ngưỡng nào đó(dùng để kết thúc
chương trình khi số khả năng quá lớn).
Tuy nhiên,việc trả lại giá trị cho mảng A là không dễ dàng. Sau mỗi lần duyệt,số lượng ô
thay đổi giá trị không xác định cụ thể.
Vì vậy, chúngta sẽ sử dụng thêm một mảng trong thủ tục đệ quy. Để trả lại giátrị trước đó
cho mảng A, chúng ta dùng một phép gán. Nhưng việckhai báo mảng này sẽ làm tốn không
gian bộ nhớ, dễ gây tràn Stack.Song cũng rất phức tạp khi trả lại giá trị mà không dùng
thêm mảngnày. Các bạn có thể sử dụng duyệt không quay lui để giải quyết bàitoán này
bằng cách: tìm ra mọi khả năng của tất cả các ô rồi so sánhvới dữ liệu vào. Khi đó, số khả
năng là: 3
N*(N-1)/2
(một con số rất lớn)
Dưới đâylà chương trình cài đặt cụ thể:
Const inp=’INP.TXT’;
out=’OUT.TXT’;
Max=21;
C1:Array[1..3]of byte=(0,1,3);
C2:Array[0..3]of byte=(0,3,0,1);
Type arr=array[1..Max,1..Max] of shortint;
var a: arr; OK: Boolean;
n,io,jo:byte; g: text;
Procedure Docfile;
var i,j: byte;
begin
fillchar(a,sizeof(a),0);
assign(g,inp);reset(g);
readln(g,N);
for i:=1 toN do
begin
for j:=1 to N+1 do read(g,a[i,j]);
Readln(g);
end;
close(g);
end;
Procedure Sualai2(var a:arr);
var i,j,d,vt,s: byte;
Begin fori:=1 to N do
forj:=1 to N do
if A[i,j] in [0,1,3] then a[j,i]:=c2[a[i,j]];
fori:=1 to N do
begin
s:=0; d:=0;
forj:=1 to n do
if a[i,j]=-1 then begin vt:=j; inc(d); end;
if(d=1) and (a[i,n+1] <> -1) then
begin
a[i,vt]:=a[i,n+1]-s;
a[vt,i]:=c2[a[i,vt];
OK:=false;
end;
if(d=0) and (a[i,n+1]=-1) then
begin
a[i,n+1]:=s;
OK:=false;
end;
end;
end;
Procedure Sualai1;
var i,j: byte;
Begin repeat
OK:=True;
Sualai2;
Until OK;
end;
Function thulai(a:arr): Boolean;
var i,j,s: Byte;
Begin thulai:=true;
fori:=1 to N do
begin
s:=0;
for j:=1 to N do
begin
inc(s,a[i,j]);
If (a[i,j]<>0) and (a[i,j]<>1) and (a[i,j] <>3) then
begin
thulai:=false; exit;
end;
end;
if a[i,n+1]<>s then
begin
thulai:=false; exit;
end;
end;
end;
Procedure ghinhan(a:arr);
var i,j: byte;
Begin Ifthulai(a) then
for i:=1 to N do
begin
for j:=1 to N+1 do write(g,a[i,j]:3);
writeln(g);
end;
End;
Function KT(a:arr):Boolean;
var i,j:byte;
Begin KT:=true;
for i:=1 to N do
For j:=1 to N+1 do
If a[i,j]=-1 then beginkt:=false; exit; end;
end;
Procedure Tim(var io,jo: byte);
var i,j:byte;
Begin io:=0;jo:=0;
fori:=1 to N do
forj:=1 to N do
if a[i,j]=-1 then begin io:=i;jo:=j, exit; end;
end;
Procedure Duyet(i,j: byte);
var k,i1,j1: byte; a:arr;
Begin IfKT(a) then ghinhan(a)
Else
for k:=1 to 3 do
begin
a1:=a;
a[i,j]:=C1[k];
a[j,i]:=C2[a[i,j]];
sualai2(a);
Tim(i1,j1);
Duyet(i1,j1);
a:=a1;
end;
end;
BEGIN docfile;
Sualai1;
Assign(g,out);
rewrite(g);
Tim(io,jo);
Duyet(io,jo);
Close(g);
END.
