Thuật toán loang

THUẬT TOÁN LOANG ----------------- I) ĐẶT VẤN ĐỀ: Thuật toán Loang thực chất là thuật toán tìm kiếm theo chiều rộng trên đồ thị (Breadth First Search). Để hiểu rõ bản chất của thuật toán này, ta xét bài toán ‘Thăm các đỉnh của một đồ thị’ như sau: Cho một đồ thị vô hướng G = (V,E), N đỉnh và M cạnh (số hiệu của các đỉnh là 1,2,…,N). Bây giờ ta đưa ra thứ tự duyệt các đỉnh của đồ thị đã cho theo thuật toán tìm kiếm theo chiều rộng; thứ tự duyệt có thể bắt đầu từ một đỉnh v nào đó. Tư tưởng của thuật toán là sử dụng cấu trúc dữ liệu kiểu hàng đợi (QUEUE - vào trước ra trước). Phần tử được nạp vào đầu tiên của QUEUE là đỉnh v. Sau đó cứ mỗi đỉnh p lấy ra khỏi QUEUE là ta thăm đỉnh đó đồng thời nạp vào QUEUE những đỉnh chung cạnh với p (chỉ nạp vào những đỉnh chưa xét đến). Quá trình trên được lặp đi lặp lại cho đến khi nào QUEUE rỗng thì dừng. @ Chương trình mô phỏng: Ban đầu tất cả các đỉnh i (i = 1..n) đều đặt cờ chuaxet[i] = True. Nếu đỉnh nào xét rồi ta đặt cờ của đỉnh đó sang trạng thái False. Procedure BFS(v); Tìm kiếm theo chiều rộng bắt đầu từ đỉnh v Begin QUEUE = ; {Khởi tạo QUEUE ban đầu là rỗng} QUEUE <= v; {Nạp đỉnh v vào QUEUE} Chuaxet[v]:=False;{Đỉnh v nạp vào QUEUE là đã xét rồi => cờ của v là False} While QUEUE ≠ do Begin P <= QUEUE; {Lấy p từ QUEUE} Thăm đỉnh p; For u € Ke(p) do {Những đỉnh u chung cạnh với đỉnh p} If Chuaxet(u) then {Nếu đỉnh u chưa xét đến} Begin QUEUE <= u; {Nạp u vào QUEUE} Chuaxet[u]:=False; {Đỉnh u đã xét rồi =>cờ của u là False } End; End; End; BEGIN {Chương trình chính} For v € V do Chuaxet[v]:=True; For v € V do If Chuaxet[v] then BFS(v); END. Người ta thường dùng dữ liệu kiểu mảng để biểu diễn cấu trúc dữ liệu kiểu hàng đợi QUEUE và sử dụng 2 biến Dau và Cuoi để điều khiển việc nạp vào và lấy phần tử ra (biến Dau điều khiển thao tác lấy ra, biến Cuoi điều khiển thao tác nạp vào). Với bài toán trên ta sử dụng mảng 1 chiều Q: Array[1..N] of Byte để biểu diễn QUEUE. Khi đó thao tác nạp vào và lấy ra được thực hiện như sau: FillChar(Q,SizeOf(Q),0); {Khởi tạo tất cả các phần tử của Q có giá trị 0} Dau:=1; Cuoi:=1; Q[cuoi]:=v; {Ban đầu nạp đỉnh v vào Q} Để nạp thêm đỉnh u nào đó vào Q ta thực hiện: Cuoi:=Cuoi+1; {Hoặc dùng lệnh Inc(Cuoi)} Q[Cuoi]:=u; Để lấy một đỉnh p nào đó ra khỏi Q ta thực hiện: P:=Q[Dau]; Inc(Dau); Lưu ý: Ta nói lấy đỉnh p ra khỏi hàng đợi Q là lấy ra theo cơ chế điều khiển ( vì biến Dau đã tăng lên một đơn vị qua lệnh Inc(Dau)); về mặt vật lý thì p vẫn đang nằm trong mảng Q. Như vậy ta phải hiểu rằng các phần tử trong cấu trúc hàng đợi Q là các phần tử Q[Dau],..,Q[Cuoi]. @ Chương trình đầy đủ: Program Thamdinhdothi; Uses Crt; Const Nmax=253; fi='TKR_DT.INP'; Var f:Text; s:Char; A:Array[1..Nmax,1..Nmax] of 0..1;{Nếu có cạnh giữa đỉnh i và đỉnh j thì A[i,j]=1, ngược lại A[i,j]=0 } Chuaxet:Array[1..Nmax] of Boolean;{Cờ của các đỉnh, có trạng thái True nếu chưa xét, ngược lại False} Q:Array[1..Nmax] of Byte;{Biểu diễn hàng đợi QUEUE} N,i,dem,dau,cuoi:Byte; Procedure Doctep; Begin Assign(f,fi); Reset(f); Readln(f,N); {N:Số đỉnh của đồ thị} For i:=1 to N-1 do Begin dem:=0; While not eoln(f) do Begin Read(f,s); dem:=dem+1; If s='1' then Begin A[i,dem+i]:=1; A[dem+i,i]:=1; End; If s='0' then Begin A[i,dem+i]:=0; A[dem+i,i]:=0; End; End; Readln(f); End; Close(f); End; Procedure BFS(v:Integer);{Tìm kiếm theo chiều rộng bắt đầu từ đỉnh v} Var p,u:Byte; Begin FillChar(Q,Sizeof(Q),0); {Khởi tạo tất cả các phần tử của mảng Q đều bằng 0} dau:=1; cuoi:=1; Q[cuoi]:=v; {Nạp v vao Q} Chuaxet[v]:=False; While dau cuối là Q rỗng } Begin p:=Q[dau]; dau:=dau+1; {Lấy đỉnh p ra khỏi Q } If (dau-1) mod 14 = 0 then Writeln(p:4) {In ra số hiệu đỉnh p - thao tác thăm đỉnh p} Else Write(p:4); {trên màn hình xuất hiện mỗi dòng không quá 14 số} For u:=1 to N do If (A[p,u]=1) and (Chuaxet[u]) then Begin cuoi:=cuoi+1; Q[cuoi]:=u; Chuaxet[u]:=False; End; End; End; BEGIN Clrscr; FillChar(A,Sizeof(A),0); {Khởi tạo tất cả các phần tử của mảng A đều bằng 0} Doctep; FillChar(Chuaxet,Sizeof(Chuaxet),True); {Khởi tạo cờ của tất cả các đỉnh đều ở trạng thái True - Trạng thái chưa xét} Writeln('Thu tu tham cac dinh cua do thi khi tim kiem theo chieu rong la:'); For i:=1 to N do If Chuaxet[i] then BFS(i); Writeln; Readln; END. Chương trình trên thực hiện với dữ liệu vào là tệp TKR_DT.INP có cấu trúc: - Dòng đầu tiên, được gọi là dòng 0: ghi các số nguyên dương N, x cách nhau ít nhất là một ký tự trống (N: Số đỉnh của đồ thị; x: Đỉnh xuất phát); - Trong các dòng tiếp theo: Dòng thứ i (i = 1..N-1) ghi N-i số 0 và 1 liên tiếp nhau cho biết giữa đỉnh i và đỉnh j có cạnh nối với nhau hay không (j = i + 1..N). Nếu số ghi ở vị trí j-i tính từ trái sang phải trên dòng thứ i có giá trị 1 thì có cạnh nối giữa đỉnh i và đỉnh j, nếu là giá trị 0 thì không có cạnh nối. Ví dụ với tệp TKR_DT.INP sau đây: 13 1 101000000010 01000000000 0001000000 011000000 10110000 1000001 000000 10000 0000 110 10 0 Với tệp dữ liệu vào như trên ta phải hiểu như sau: + Ở dòng 0: N=13, x=1; + Ở dòng 1: 101000000010 - giữa đỉnh 1 với đỉnh 2 có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 3 không có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 4 có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 5 không có cạnh nối với nhau .... - giữa đỉnh 1 với đỉnh 11 không có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 12 có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 13 không có cạnh nối với nhau + Ở dòng 2: 01000000000 - giữa đỉnh 2 với đỉnh 3 không có cạnh nối với nhau - giữa đỉnh 2 với đỉnh 4 có cạnh nối với nhau .... + Ở dòng 11: 10 - giữa đỉnh 11 với đỉnh 12 có cạnh nối với nhau - giữa đỉnh 11 với đỉnh 13 không có cạnh nối với nhau + Ở dòng 12: 0 - giữa đỉnh 12 với đỉnh 13 không có cạnh nối với nhau Quan hệ giữa các đỉnh được mô tả qua đồ thị sau: 2 3 5 7 8 4 1 6 9 12 13 10 11 Thứ tự các đỉnh được nạp vào hàng đợi Q và lấy ra tuần tự như sau: Các phần tử nạp vào Q Các phần tử có trạng thái cờ là False Các phần tử trong Q Phần tử lấy ra khỏi Q 1 1 1 2,4,12 (Khi lấy 1 ra) 2,4,12 2,4,12 1 Không nạp phần tử nào khi lấy 2 ra khỏi Q 4,12 2 6,7 6,7 12,6,7 4 10,11 10,11 6,7,10,11 12 5,13 5,13 7,10,11,5,13 6 3 3 10,11,5,13,3 7 Không nạp phần tử nào khi lấy 10 ra khỏi Q 11,5,13,3 10 Không nạp phần tử nào khi lấy 11 ra khỏi Q 5,13,3 11 8,9 8,9 13,3,8,9 5 Không nạp phần tử nào khi lấy 13 ra khỏi Q 3,8,9 13 Không nạp phần tử nào khi lấy 3 ra khỏi Q 8,9 3 Không nạp phần tử nào khi lấy 8 ra khỏi Q 9 8 Không nạp phần tử nào khi lấy 9 ra khỏi Q Rỗng 9 Các phần tử tuần tự được lấy ra khỏi hàng đợi Q chính là các đỉnh được duyệt: 1, 2, 4, 12, 6, 7, 10, 11, 5, 13, 3, 8, 9 Qua đó cho thấy từ một đỉnh ta thăm đến các đỉnh khác liên quan đến nó theo chiều rộng. Chính vì vậy thuật toán tìm kiếm theo chiều rộng được gọi là thuật toán Loang. Lưu ý: + Với những bộ test dữ liệu bé thì ta có thể tạo một cách thủ công. Nhưng với những bộ test dữ liệu lớn thì ta phải tạo bằng chương trình. Sau đây xin giới thiệu chương trình tạo bộ test với số lượng các đỉnh của đồ thị là 253: Program Taotes_baithamdinh; Uses Crt; Const MN=253; fi='TKR_DT.INP'; Var f:Text; Procedure Gen; Var i,j:Integer; Begin Assign(f,fi); Rewrite(f); Writeln(f,MN); Randomize; For i:=1 to MN-1 do Begin For j:=1 to MN-i do Write(f,Random(2)); {Random(2) cho các giá trị ngẫu nhiên tù 0 đến 1} Writeln(f); End; Close(f); End; BEGIN Gen; END. + Đối với dữ liệu vào mà quan hệ giữa các đỉnh có dạng là một ma trận đầy đủ (ma trận đối xứng) và các số ghi trên mỗi dòng cách nhau ít nhất là một ký tự trống thì ta thay thủ tục đọc tệp bởi thủ tục sau đây: Procedure Doctep; Var i,j: Byte; Begin Assign(f,fi); Reset(f); Readln(f,N); For i:=1 to N do Begin For j:=1 to N do Read(f,A[i,j]); Readln(f); End; End; Bạn đọc tự viết thủ tục đọc tệp trong trường hợp dữ liệu vào mà quan hệ giữa các đỉnh có dạng là nữa trên hoặc nữa dưới của một ma trận đầy đủ và các số ghi trên mỗi dòng cách nhau ít nhất là một ký tự trống hoặc liền nhau. II) CÁC BÀI TOÁN ÁP DỤNG: Bài 1: Tìm đường đi qua ít đỉnh nhất Cho đồ thị vô hướng G = (V,E) có N đỉnh và M cạnh (các đỉnh có số hiệu là 1,2,...,N). Mối quan hệ giữa các đỉnh được cho bởi ma trận kề A[i,j]: nếu đỉnh i và đỉnh j có chung cạnh thì A[i,j] = 1, ngược lại A[i,j] = 0. Yêu cầu: Tìm đường đi qua ít đỉnh nhất giữa 2 đỉnh bất kỳ nào đó của đồ thị. Tìm số lượng các thành phần liên thông của đồ thị (các đỉnh thuộc một vùng liên thông nếu luôn tồn tại đường đi giữa 2 đỉnh bất kỳ trong các đỉnh đó) Bàn về dung lượng bộ nhớ: Chương trình trên thực hiện với giá trị tối đa là 253 đỉnh của đồ thị. Vậy với đồ thị có số đỉnh lớn hơn 253 thì ta giải quyết thế nào? Bài toán sau đây đưa ra một giải pháp để xử lý: Bài 2: Đường đi trong đồ thị có nhiều đỉnh Cho một đồ thị vô hướng có N đỉnh (N<=500000), các đỉnh có số hiệu là 1..N. Hãy tìm đường đi qua ít đỉnh nhất giữa 2 đỉnh x và y nào đó cho trước của đồ thị. Dữ liệu vào là tệp văn bản dothi.inp có cấu trúc: - Dòng đầu tiên ghi các số N, x, y; - Các dòng tiếp theo, mỗi dòng ghi 2 số là số hiệu của 2 đỉnh có chung cạnh; - Các số ghi trên mỗi dòng cách nhau ít nhất là một ký tự trống. Dữ liệu ra là tệp văn bản dothi.out ghi số hiệu các đỉnh trong đường đi tìm được giữa 2 đỉnh x và y, mỗi số ghi trên 1 dòng. Nếu không tồn tại đường đi thì ghi thông báo ‘Khong ton tại duong di’. Ví dụ: Tệp dothi.inp Tệp dothi.out Tệp dothi.inp Tệp dothi.out 13 1 6 1 2 1 4 1 12 2 1 2 4 3 7 4 1 4 2 4 7 4 6 6 7 6 4 6 5 6 13 5 6 5 8 5 9 7 3 7 4 7 6 8 5 8 9 9 5 9 8 10 11 10 12 11 10 11 12 12 1 12 10 12 11 13 6 1 4 6 13 1 8 1 2 1 4 1 12 2 1 2 4 3 7 4 1 4 2 4 7 4 6 6 7 6 4 6 5 6 13 5 6 5 8 5 9 7 3 7 4 7 6 8 5 8 9 9 5 9 8 10 11 10 12 11 10 11 12 12 1 12 10 12 11 13 6 1 4 6 5 8 Phân tích: Nhìn dạng bài toán, chúng ta nhận thấy ngay thuật toán tối ưu để xử lý là thuật toán Loang. Nhưng vì số đỉnh của đồ thị nằm trong phạm vi quá lớn (N<=500000) nên ta không thể sử dụng kiểu dữ liệu mảng để lưu trữ thông tin về các đỉnh và biểu diễn cấu trúc hàng đợi. Vậy làm thế nào? Tôi xin đưa ra một giải pháp: Lưu trữ các thông tin trong quá trình xử lý cũng như biểu diễn cấu trúc hàng đợi để ‘Loang’ là bởi các tệp văn bản (vì chúng ta đã biết tệp là kho chứa dữ liệu dường như vô tận). Cụ thể như sau: Sử dụng hệ thống tệp văn bản *.ke để lưu các đỉnh chung cạnh với đỉnh có số hiệu là giá trị số của phần đầu tên tệp: Ví dụ tệp 2.ke sẽ lưu trữ số 1 và số 4, mỗi số ghi trên một dòng. Sử dụng hệ thống các tệp văn bản *.dd chứa số 1 hoặc 0 cho biết đỉnh có số hiệu là giá trị số của phần đầu tên tệp đã bị đánh dấu hay chưa; giá trị 1: đỉnh đó đã xét rồi, ngược lại là chưa xét. Ví dụ tệp 5.dd chứa số 1 có nghĩa là đỉnh 5 đã được xét rồi trong quá trình ‘Loang’ (đã được nạp vào hàng đợi).Hệ thống tệp này khởi tạo ban đầu là chứa số 0. Sử dụng hệ thống tệp văn bản *.tr chứa một số nguyên là số hiệu của đỉnh trước đỉnh có số hiệu là giá trị số của phần đầu tên tệp khi nạp vào hàng đợi. Ví dụ tệp 6.tr chứa số 4 có nghĩa là đỉnh 6 được nạp vào hàng đợi nhờ đỉnh 4. Sử dụng hệ thống các tệp *.que để biểu diễn cấu trúc hàng đợi. Ví dụ dau = 1 và cuoi = 4 thì đỉnh đầu tiên của hàng đợi là đỉnh có số hiệu là số được chứa trong tệp 1.que. Tương tự, với đỉnh thứ 2, thứ 3, thứ 4, ... của hàng đợi. Sử dụng hệ thống các tệp văn bản *.kq để lưu các đỉnh trong quá trình lấy kết quả. Hệ thống các tệp văn bản trên được đưa ra ở phần khai báo hằng: Const ke =’.ke’; dd =’.dd’; tr =’.tr’; que =’.que’; kq =’.kq’ Khởi tạo hệ thống các tệp *.dd và *.tr : {Biến i kiểu Longint, biến s kiểu String} For i:=1 to N do Begin Str(i,s); {Thủ tục chuyển số i sang dạng xâu là s} Assign(f,s+dd); Rewrite(f); Write(f,0); Close(f); Assign(f,s+tr); Rewrite(f); Write(f,0); Close(f); End; Để lấy đỉnh u ra khỏi hàng đợi thực hiện: Str(dau,s); Assign(f,s+que); Reset(f); Read(f,u); Close(f); Inc(dau); Để nạp đỉnh v vào hàng đợi ta thực hiện: Inc(cuoi); Str(cuoi,s); Assign(f,s+que); Rewrite(f); Writeln(f,v); Close(f); Toàn văn chương trình: {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+} {$M 16384,0,655360} Program Timduongdivoisodinhlon; Uses Crt; Const fi='dothi.inp'; fo='dothi.out'; ke='.ke'; que='.que'; dd='.dd'; tr='.tr'; kq='.kq'; Var n,x,y:Longint; time:longint; {Để phục vụ tính thời gian chạy chương trình} f,f1,f2,f3:Text; Procedure Doctep; Var i,u,v:Longint; s:string; Begin Assign(f,fi); Reset(f); Readln(f,n,x,y); For i:=1 to N do Begin Str(i,s); {Thủ tục đổi số u thành dạng ký tự s của nó} Assign(f1,s+ke); Rewrite(f1); Close(f1); Assign(f1,s+tr); Rewrite(f1); Write(f1,0); Close(f1); End; While not seekeof(f) do {Nếu con trỏ tệp chưa di chuyển đến cuối tệp} Begin Readln(f,u,v); Str(u,s); Assign(f1,s+ke); Append(f1); Writeln(f1,v); Close(f1); Assign(f1,s+dd); Rewrite(f1); Writeln(f1,0); Close(f1); Str(v,s); Assign(f1,s+dd); Rewrite(f1); Write(f1,0); Close(f1); End; Close(f); End; Procedure Loang; Var u,v,dau,cuoi:Longint; s1,s2,s3:String; ok:Byte; Begin dau:=1; cuoi:=1; Str(x,s1); Assign(f,s1+dd); Rewrite(f); Write(f,1); {Đánh đấu đỉnh x} Close(f); Assign(f,s1+tr); Rewrite(f); Writeln(f,0); Close(f); Assign(f,'1'+que); Rewrite(f); Writeln(f,x); Close(f); While dau<=cuoi do Begin Str(dau,s1); Assign(f,s1+que); Reset(f); Readln(f,u); {Lấy phần tử đầu tiên trong hàng đợi} Close(f); Inc(dau); Str(u,s1); Assign(f,s1+ke); {Đọc các phần tử kề với u} Reset(f); While not Seekeof(f) do Begin Readln(f,v); Str(v,s2); Assign(f1,s2+dd); Reset(f1); Readln(f1,ok); {Kiểm tra xem v đã bị đánh dấu hay chưa} Close(f1); If ok=0 then Begin Assign(f1,s2+dd); Rewrite(f1); Writeln(f1,1); {Đánh dấu v} Close(f1); Inc(cuoi); Str(cuoi,s3); Assign(f2,s3+que); Rewrite(f2); Writeln(f2,v); {Nạp v vào hàng đợi} Close(f2); Assign(f2,s2+tr); Rewrite(f2); Writeln(f2,u); {Lưu lại đỉnh trước của v} Close(f2); End; End; Close(f); End; End; Procedure Ketqua; Var i,t,dem:Longint; s,s1:String; Begin Assign(f,fo); Rewrite(f); Str(y,s); Assign(f1,s+tr); Reset(f1); Read(f1,t); Close(f1); Assign(f1,'1'+kq); Rewrite(f1); Write(f1,y); {Ghi số y vào tệp 1.kq} Close(f1); If t=0 then Write(f,'Khong ton tai duong di') Else Begin i:=t; dem:=1; While ix do Begin Inc(dem); Str(dem,s1); Assign(f1,s1+kq); Rewrite(f1); Writeln(f1,i); Close(f1); Str(i,s1); Assign(f1,s1+tr); Reset(f1); Read(f1,i); Close(f1); End; Inc(dem); Str(dem,s1); Assign(f1,s1+kq); Rewrite(f1); Writeln(f1,i); Close(f1); For i:=dem downto 1 do Begin Str(i,s1); Assign(f1,s1+kq); Reset(f1); Read(f1,t); Close(f1); Writeln(f,t); End; End; Close(f); End; BEGIN Clrscr; time:=MemL[0:$46C]; {Mốc thời gian bắt đầu chạy chương trình} Doctep; Loang; Ketqua; Writeln((MemL[0:$46C] - time)/18.21:10:10); {Thời gian chạy chương trình} END. Lưu ý: + Vì khi chương trình trên thực hiện với bộ dữ liệu lớn thì sẽ tạo ra rất nhiều tệp văn bản, mà những tệp này đến một lúc nào đó ta phải xoá đi để mở rộng không gian lưu trữ cho thiết bị nhớ. Bởi vậy khi cài đặt nên tạo ra một thư mục để chứa các tệp văn bản đó (khi cần xoá, ta xoá cả thư mục hoặc tất cả các tệp trong thư mục đó). Bạn đọc có thể sử dụng thêm một biến kiểu String chứa đường dẫn để thay đổi một số câu lệnh trong chương trình trên sao cho việc tạo hoặc truy cập các tệp văn bản cho đúng theo thư mục đã tạo. + Ta có thể tham khảo chương trình sau đây để tạo các bộ test dữ liệu lớn: Program Taotes_duongdivoisodinhlon; Uses Crt; Const MN=500000; fi='dothi.inp'; Var f:Text; x,xn,yd:Longint; Procedure Gen; Var i,j:Longint; Begin Assign(f,fi); Rewrite(f); Randomize; xn:=Random(MN+1); If xn=0 then While xn=0 do xn:=Random(MN+1); yd:=Random(MN+1); If (yd=0) or (yd=xn) then While (yd=0) or (yd=xn) do yd:=Random(MN+1); Writeln(f,MN,’ ‘,xn,’ ‘,yd); For i:=1 to MN do Begin x:=Random(MN); If x=i then While x=i do x:=Random(MN); If x0 then Begin For j:=1 to x do Writeln(f,i,’ ‘,x); For j:=1 to x do Writeln(f,x,’ ‘,i); End; End; Close(f); End; BEGIN Repeat Gen; Writeln(‘Hai đinh can tim duong di la:’,xn,’ ‘,yd); Until Readkey = #27; {Khi nào thấy đạt yêu cầu rồi thì ấn phím ESC để dừng} END. + Nếu yêu cầu dữ liệu ra là tệp văn bản như trên nhưng dòng đầu tiên ghi số lượng đỉnh trong đường đi tìm được thì ta xử lý thế nào? Bạn đọc tự giải quyết, coi như là một bài tập. Bài 4: Otomat Có một Otomat được ghép từ các chi tiết có một trong hai trạng thái 0 hoặc 1 như hình 1. Otomat có cấu trúc như hình 2 gồm 8 chi tiết G1, G2,..., G8 với 3 lối vào A,B,C. Mỗi trạng thái của Otomat được được thể hiện bởi xâu nhị phân độ dài 8 là các trạng thái tương ứng của G1, G2,...,G8. Trạng thái 1 Trạng thái 0 Hình 1 A B C G1 G2 G3 G4 G5 G6 G7 G8 Hình 2 Otomat hoạt động như sau: Khi thả một quả cầu vào một lối vào nào đó, sau khi quả cầu đi từ một chi tiết nào đó, chi tiết đó thay đổi trạng thái từ 0 thành 1 hoặc từ 1 thành 0. Hoạt động của Otomat được thể hiện bởi một xâu ký tự S chỉ gồm các chữ cái in hoa A, B, C mà mỗi ký tự trong xâu S thể hiện việc quả cầu vào lối vào với tên ký tự đó. Ví dụ: S=AABC có nghĩa là ta lần lượt thả quả cầu vào các lối A, A, B, C. Bài toán đặt ra như sau: Cho hai trạng thái bất kỳ T1, T2 của Otomat. Hãy tìm một ký tự S ngắn nhất có thể được thể hiện hoạt động của Otomat chuyển từ trạng thái T1 đến trạng thái T2. Dữ liệu vào là tệp otomat.inp cócấu trúc: - Dòng thứ nhất ghi 8 số 0 và 1 biểu diễn trạng thái T1; - Dòng thứ hai ghi 8 số 0 và 1 biểu diễn trạng thái T2; Các số trên mỗi dòng được ghi liên tiếp nhau. Dữ liệu ra là tệp otomat.out ghi xâu ký tự S tìm được. Nếu không tìm được xâu S thì ghi ký tự ‘#’. Ví dụ: Otomat.inp Otomat.out Otomat.inp Otomat.out 10011010 00101001 AAABBC 00010010 00101001 # Phân tích: {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+} {$M 16384,0,655360} Program OTOMAT; Uses Crt; Const Nmax=256; fi='otomat.inp'; fo='otomat.out'; Type otomat=String[8]; Var f:Text; S:string; T1,T2,O:otomat; i,dau,cuoi,dem:Integer; Q:Array[1..Nmax] of otomat; truoc:Array[1..Nmax] of Integer; Procedure Doctep; Begin Assign(f,fi); Reset(f); Readln(f,T1); Readln(f,T2); Close(f); End; Function Ktra(T:otomat;N:integer):Boolean; Var j:Integer; Begin Ktra:=True; For j:=1 to N do If T=Q[j] then Begin Ktra:=False; Exit; End; End; Function Tha_A(T:otomat):otomat; Begin If T[1]='0' then Begin T[1]:='1'; If T[6]='0' then T[6]:='1' else T[6]:='0'; End else {T[1]='1'} Begin T[1]:='0'; If T[4]='0' then Begin T[4]:='1'; If T[6]='0' then T[6]:='1' else T[6]:='0'; End else {T[4]='1'} Begin T[4]:='0'; If T[7]='0' then T[7]:='1' else T[7]:='0'; End; End; Tha_A:=T; End; Function Tha_B(T:otomat):otomat; Begin If T[2]='0' then Begin T[2]:='1'; If T[4]='0' then Begin T[4]:='1'; If T[6]='0' then T[6]:='1' Else T[6]:='0'; End Else {T[4]='1'} Begin T[4]:='0'; If T[7]='0' then T[7]:='1' Else T[7]:='0'; End; End Else {T[2]='1'} Begin T[2]:='0'; If T[5]='0' then Begin T[5]:='1'; If T[7]='0' then T[7]:='1' else T[7]:='0'; End Else {T[5]='1'} Begin T[5]:='0'; If T[8]='0' then T[8]:='1' else T[8]:='0'; End; End; Tha_B:=T; End; Function Tha_C(T:otomat):otomat; Begin If T[3]='0' then Begin T[3]: