Công thức toán học không thể tải, để xem trọn bộ tài liệu hoặc in ra làm bài tập, hãy tải file word về máy bạn nhé

A / KHÁI NIỆM CHUNG

I / KHÁI NIỆM VỀ ĐỆ QUI :

Một đối tượng gọi là có tính đệ qui nếu nó được định nghĩa thông qua chính nó .

Một hàm , một thủ tục có tính đệ qui nếu trong thân chương trình của hàm , thủ tục này lại có lời gọi tới chính nó .

Thí dụ 1:

Định nghĩa giai thừa của một số nguyên không âm là định nghĩa có tính đệ qui. Thật vậy:

⎧ 1 Nếu N=0

(N)! = ⎨

⎩ N * (N-1)! Nếu N>0

Để định nghĩa N giai thừa , phải thông qua định nghĩa giai thừa ( của N-1).

Thí dụ 2:

Xây dựng hoán vị của N phần tử cũng có tính chất đệ qui . Thật vậy :

Giả sử có 1 hoán vị là S (A₁ ,A ₂ , ... A _i-1 ,Ai ,..... A_n-1 ,A_n ), sau đó đổi chỗ 2 phần tử S[i] và S[j] của hoán vị đó ta sẽ được một hoán vị mới .Sau đây là sơ đồ hình thành dần các hoán vị tiếp theo nhau của hoán vị S(1,2,3)

123

B1 : i =1 123 213 312

j = 1,2,3

B2 : i = 2 123 132 213 231 312 321 j=2,3

B3 : i =3 123 132 213 231 312 321

j=3

Vậy để xây dựng các hoán vị sau ta phải dựa vào các hoán vị đã sinh ra trước đó.

Thí dụ 3: Xây dựng tổ hợp chập K của N phần tử 1,2,3,...,N cũng theo phương thức đệ qui :

Ta sẽ xây dựng dần từng phần tử từ vị trí thứ 1 đến vị trí thứ K của tổ hợp .Để xây dựng phần tử thứ i ( sau khi đã xây dựng xong các phần tử từ 1 đến i-1 của tổ hợp này ) , ta sẽ cho phần tử thứ i nhận 1 trong các giá trị từ (A_i-1 +1) đến giá trị cao nhất có thể được của nó đó là giá trị (N-K)+i vì sau phần tử thứ i này còn (K-i) phần tử ,do đó nếu phần tử thứ i nhận giá trị cao nhất là (N-K)+i thì các phần tử tiếp theo vẫn còn khả năng nhận các giá trị : (N-K)+i +1 , (N-K)+i +2 , ...., (N-K)+i + (K-i) = N .

Vậy để xây dựng phần tử thứ i của 1 tổ hợp , ta phải dựa vào kết quả đã xây dựng tới phần tử thứ i-1 . Tất nhiên để xây dựng phần tử thứ 1 , ta phải dựa vào ‘phần tử hàng rào ‘ là phần tử ở vị trí thứ ‘0’ ,ta gán cho phần tử này giá trị nào cho phù hợp qui luật nêu trên ? rõ ràng đó là giá trị 0 ,nhằm cho nó quyền được bình đẳng như mọi phần tử khác .Phần tử 0 này chịu một trách nhiệm rất nặng nề ,bắt đầu từ nó mới xây dựng dần được các phần tử tiếp theo của mọi tổ hợp , song ta cũng đừng quên nó phải ‘ngậm ngùi’ vì ‘không được đứng trong tổ hợp ‘ .

Sau đây là sơ đồ minh hoạ việc xây dựng tổ hợp chập 3 của 5 phần tử 1,2,3,4,5

0 * * *

i=1 ; n-k+i = 3 0 1 * * 0 2 * * 0 3 * *

i=2 ; n-k+i = 4 012* 013* 014* 023* 024* 034*

i=3 ; n-k+i = 5 0123 0124 0125 0134 0135 0145 0234 0235 0245 0345

II / LƯU Ý VỀ THỦ TỤC VÀ HÀM ĐỆ QUI :

Lưu ý 1 + Trong thủ tục và hàm đệ qui cần chứa các lệnh thể hiện tính dừng của đệ qui .Nghĩa là các thủ tục , hàm đệ qui chỉ gọi tới chính nó một số hữu hạn lần rồi gặp điều kiện thoát ( để nó không gọi tới chính nó nữa )

Thí dụ 1 :

Function Giaithua(N: Byte) : LongInt;

Begin

If N=0 then giaithua := 1

Else

Giaithua := N*Giaithua(N-1);

End;

Trong hàm Giaithua , điều kiện dừng là 0! = 1 , vì mỗi lần gọi tới hàm Giaithua thì N giảm đi 1 đơn vị nên sẽ dẫn tới trường hợp N=0 .

Thí dụ 2 :

Function Fibonaci(N : Integer) : LongInt;

Begin

If (N=1) or (N=2) then Fibonaci := 1

Else

Fibonaci:= Fibonaci(N-1)+ Fibonaci(N-2);

End;

Trong hàm Fibonaci , điều kiện dừng là :

If (N=1) or (N=2) then Fibonaci := 1

vì mỗi lần gọi tới hàm Fibonaci thì N giảm đi 1 , sẽ dẫn tới tình trạng N=3

==> Fibonaci(3) = Fibonaci(2)+ Fibonaci(1) = 1+1 =2.

Lưu ý 2 Thủ tục và hàm đệ qui phải thể hiện tính đệ qui : Nó gọi tới chính nó

Trong 2 thí dụ nêu trên các lệnh

Giaithua := N*Giaithua(N-1); { Thí dụ 1 }

hoặc

Fibonaci:= Fibonaci(N-1)+ Fibonaci(N-2); { Thí dụ 2 }

thể hiện tính đệ qui .

III / MỘT SỐ BÀI TẬP CƠ BẢN :

Bài 1 : Xây dựng các hoán vị của tập N phần tử 1,2,3,...,N bằng đệ qui :

Bài 2 : Xây dựng các tổ hợp chập K của N phần tử 1,2,3,...,N ( 0<K<N )

Bài 3 : Xây dựng các chỉnh hợp chập K của N phần tử 1,2,3,...,N ( 0<K<N )

Bài 4 : Xây dựng các chỉnh hợp lặp chập K của N phần tử 1,2,3,...,N ( 0<K<N ) (còn gọi là bộ mẫu N phần tử )

IV / BÀI TẬP VỀ NHÀ

Bài 5 : Tạo xâu kí tự có độ dài không quá 20 , chỉ chứa 3 kí tự A,B,C có tính chất : Không có 2 xâu con liền nhau bằng nhau

Gợi ý :

+ Xây dựng hàm KT kiểm tra 2 xâu con liền nhau có bằng nhau không ?

+ Giả sử đã tạo được xâu A có i-1 kí tự , chọn kí tự thứ i là 1 trong 3 kí tự A,B,C nối thêm vào xâu A mà A vẫn thoả mãn KT thì tìm tiếp kí tự i+1 , nếu không thoả mãn thì xâu A trở lại như trước (có i-1 kí tự cũ ) để chọn kí tự thứ i của xâu là 1 trong 2 kí tự còn lại ....

Bài 6 :

Lập trình thể hiện trò chơi Tháp Hà Nội : Trên cọc 1 có N đĩa và xếp đĩa nhỏ ở trên đĩa lớn ; cọc 2 và cọc 3 chưa có đĩa . Hãy chuyển hết đĩa ở cọc 1 sang cọc 3 theo qui luật sau :

Chuyển từng đĩa ở trên cùng của một trong 3 cọc sang cọc khác sao cho đĩa lớn không đặt trên đĩa nhỏ .

Gợi ý :

+ Nếu cọc 1 chỉ có 1 đĩa thì chuyển nó sang cọc 3

+ Giả sử đã giải được bài toán trong trường hợp có N-1 đĩa ; không mất tính chất tổng quát ,ta giả sử cọc 2 chứa N-1 đĩa ( đĩa nhỏ trên đĩa lớn ) và sẽ chuyển hết được sang cọc 3 nhờ cọc trung gian là cọc 1 .Ta sẽ chứng minh bài toán cho N đĩa xếp ở cọc 1 , chuyển sang cọc 3 nhờ cọc trung gian là cọc 2 sẽ giải được. Thật vậy :

a) Tìm cách chuyển N-1 đĩa từ cọc 1 sang cọc 2 ( cọc phụ : 3 );

b) Chuyển 1 đĩa còn lại (đĩa lớn nhất ) ở cọc 1 sang cọc 3

c) Tìm cách chuyển N-1 đĩa từ cọc 2 sang cọc 3 (cọc phụ là cọc 1 )

Bài 7 :

Lập trình bài toán : Tính số cách chia M vật thành N phần theo qui luật :

S₁ ≥ S₂ ≥ ..... ≥ S_N-1 ≥ S_N ≥0 ( S_i là số vật của phần thứ i )

Gợi ý : + Nếu số đồ vật M=0 thì coi như có 1 cách chia : đó là cách chia mỗi người không được vật nào .

+ Nếu số người N=0 thì không thể chia được

+ Nếu 0<M<N thì trong mọi cách chia , luôn có ít nhất N-M người không được chia , do vậy các cách chia khác nhau ở chỗ : chia có khác nhau cho M người còn lại hay không ? Nói cách khác số cách chia trong trường hợp này bằng số cách chia của bài toán chia M vật cho M người .

+ Nếu M>=N>0 thì các cách chia thuộc 2 loại :

Loại 1 : Mọi người đều có phần , vậy mọi cách chia có chỗ giống nhau là mọi người đều có ít nhất 1 vật , các cách chia chỉ khác nhau ở chỗ phân chia M-N vật còn lại cho N người như thế nào ?

Loại 2 : Có 1 người không được chia vật nào . Nghĩa là chỉ chia M vật cho N-1 người

Bài 8 : Vẽ các đường HilBert cấp 5 , biết các đường HilBert cấp 1, cấp 2, cấp 3 như hình vẽ dưới đây :

Các đường cấp 1

Các đường cấp 2 Đường A3

A2 B2

C2 D2

Đường A5

Bài 1 :

Uses Crt;

Const N = 8;

TF = 'hoanvi.txt';

Type TS = String[N];

Var S : TS;

d,Lt : Longint;

F : Text;

T : LongInt Absolute $0000:$046C;

Procedure Doi(Var a,b : Char);

Var p : Char;

Begin

p := a; a := b; b := p;

End;

Procedure Hien(S : TS);

Begin

Inc(d); Write(F,S,' ');

If (d mod 10 = 0) then Writeln(F);

End;

Procedure Tao(S : String;i : Byte);

Var j : Byte;

p : Char;

Begin

If i=N then Hien(S);

For j:=i to N do

Begin

Doi(S[i],S[j]);

Tao(S,i+1);

End;

End;

BEGIN

Clrscr;

S := '123456789';

S := Copy(S,1,N);

d := 0;

LT := T;

Assign(F,TF);

ReWrite(F);

Tao(S,1);

Close(F);

Writeln(#13#10,'So hoan vi la : ',d);

Writeln('Mat thoi gian la : ',((T-Lt)/18.2):10:2,' giay');

Readln;

END.

Chương trình trên chạy trên máy DX2-486 , N =8 , mất thời gian khoảng 4 giây .

N= 9 , mất khoảng 37 giây .

Bài 2 :

Uses Crt;

Var X : Array[0..20] of Byte;

K,N : Byte;

C : LongInt;

Procedure Init;

Begin

Write('k,n = ');

Readln(k,n);

X[0] := 0;

C := 0;

End;

Procedure Inkq;

Var i : Byte;

Begin

Inc(C);

Write(C:5,' : ');

For i:=1 to k do Write(x[i]:3);

Writeln;

End;

Procedure Thu(i : Byte);

Var j : Byte;

Begin

For j:= x[i-1]+1 to n-k+i do

Begin

x[i] := j;

If i= k then Inkq Else Thu(i+1);

End;

End;

BEGIN

Clrscr;

Init;

Thu(1);

Readln;

END.

Bài 3 :

Uses Crt;

Var

Cx : Array [1..10] of Boolean;

A : Array [1..10] of Byte;

N,k : Byte;

dem : LongInt;

Procedure Nhap;

Begin

Write('NHap N,k : ');

Readln(N,k);

End;

Procedure Tao;

Begin

Fillchar(Cx,Sizeof(Cx),True);

dem := 0;

End;

Procedure Hien;

Var j : Byte;

Begin

Inc(dem);Write(dem:5,' : ');

For j:=1 to k do Write(a[j]:3);

Writeln;

End;

Procedure Try(i : Byte);

Var j : Byte;

Begin

For j:=1 to n do

If Cx[j] then

Begin

A[i]:=j;

Cx[j]:=False;

If i=k then Hien Else Try(i+1);

Cx[j]:=True;

End;

End;

Begin

Clrscr;

Nhap;

Tao;

Try(1);

Readln;

End.

Bài 4 :

Uses Crt;

Const Max = 20;

Var X : Array[0..Max] of Byte;

K,N : Byte;

dem : LongInt;

Procedure Init;

Begin

Write('k,n (k<=n) = ');

Readln(k,n);

X[0] := 0;

dem := 0;

End;

Procedure Inkq;

Var i : Byte;

Begin

Inc(dem);

Write(dem:10,' : ');

For i:=1 to k do Write(x[i]:2);

Writeln;

End;

Procedure Thu(i : Byte);

Var j : Byte;

Begin

For j:= 1 to n do

Begin

x[i] := j;

If i = k then Inkq Else Thu(i+1);

End;

End;

BEGIN

Clrscr;

Init;

Thu(1);

Readln;

END.

Bài 5 :

Uses Crt;

Const N = 20;

Var S : String;

Function Kt(S : String) : Boolean;

Var i,j : Byte;

Begin

Kt := True;

For i:=1 to Length(S) div 2 do

For j:=1 to Length(S)- 2*i+1 do

If Copy(S,j,i)=Copy(S,j+i,i) then

Begin

Kt := False;

Exit;

End;

End;

Procedure Tao(S : String);

Var ch : Char;

Begin

If Length(S)=N then

Begin

Writeln(S);

Readln;

Halt;

End;

For ch:='A' to 'C' do { Khởi tạo mọi khả năng }

Begin

S := S+ch; { Thử chọn 1 khả năng }

If Kt(S) then Tao(S) {Nếu thoả mãn điều kiện thì tìm tiếp }

Else Delete(S,Length(S),1); {Nếu không thì trả về trạng thái cũ}

End;

End;

BEGIN

Clrscr;

S := '';

Tao(S);

END.

Bài 6 :

Uses Crt;

Const C1 = '1';

C2 = '2';

C3 = '3';

Max = 20;

Var Sodia,i,h1,h2,h3 : Byte;

A,B,C : Array[1..100] of Byte;

Procedure Khoitri;

Begin

Write('Nhap so luong dia (<=20) : ');

Repeat

{$I-} Readln(Sodia);{$I+}

Until (IoResult=0) and (sodia<=Max) and (Sodia>0);

Textcolor(14);

For i:=sodia downto 1 do

Begin

Gotoxy(40,24-i);

Writeln('**');

End;

Textcolor(12);

For i:=sodia downto 1 do

Begin

Gotoxy(50,24-i);

Writeln('**');

End;

Textcolor(9);

For i:=sodia downto 1 do

Begin

Gotoxy(60,24-i);

Writeln('**');

End;

{ Readln; }

Textcolor(15);

For i:=sodia downto 1 do

Begin

Gotoxy(40,24-i);

Writeln((sodia-i+1):2);

A[i] := sodia-i+1;

B[i] := 0;

C[i] := 0;

End;

{ Readln;}

h1 := sodia;

h2 := 0;

h3 := 0;

End;

Procedure Hien(X,Y : Char);

Begin

Case X of

'1' : Begin

Gotoxy(40,24-h1);

Textcolor(14);Write('**');Textcolor(15);

Case Y of

'2' : Begin

Inc(h2);B[h2] :=A[h1];

Gotoxy(50,24-h2); Write(B[h2]:2);

End;

'3' : Begin

Inc(h3);C[h3] := A[h1];

Gotoxy(60,24-h3); Write(C[h3]:2);

End;

End;

Dec(h1);

End;

'2' : Begin

Gotoxy(50,24-h2);

Textcolor(12);Write('**');Textcolor(15);

Case Y of

'1': Begin

Inc(h1);A[h1] := B[h2];

Gotoxy(40,24-h1); Write(A[h1]:2);

End;

'3' : Begin

Inc(h3);C[h3] := B[h2];

Gotoxy(60,24-h3); Write(C[h3]:2);

End;

End;

Dec(h2);

End;

'3' : Begin

Gotoxy(60,24-h3);

Textcolor(9);Write('**');Textcolor(15);

Case Y of

'1': Begin

Inc(h1);A[h1] := C[h3];

Gotoxy(40,24-h1); Write(A[h1]:2);

End;

'2' : Begin

Inc(h2);B[h2] :=C[h3];

Gotoxy(50,24-h2); Write(B[h2]:2);

End;

End;

Dec(h3);

End;

End;

End;

Procedure Chuyen(N : Byte;A,B,C : Char);

Begin

If N=1 then { Writeln('Chuyen ',A,' --> ',C);}

Begin Hien(A,C);{Readln;}End

Else

Begin

Chuyen(N-1,A,C,B);

Chuyen(1,A,B,C);

Chuyen(N-1,B,A,C);

End;

End;

BEGIN

Repeat

Clrscr;

Khoitri;

Chuyen(sodia,C1,C2,C3);

Gotoxy(1,24);Writeln('ESC : thoat ');

Until ReadKey=#27;

END.

Bài 7 :

Uses Crt;

Var M,N,sc : LongInt;

Procedure Nhap;

Begin

Write('Nhap so do vat : ');

Readln(M);

Write('Nhap so nguoi : ');

Readln(N);

End;

Function Chia(M,N : LongInt) : LongInt;

Begin

If M=0 then Chia := 1

Else {M>0}

If N=0 then Chia := 0

Else {N>0}

If M<N then Chia := Chia(M,M)

Else

Chia := Chia(M-N,N)+Chia(M,N-1);

End;

BEGIN

Clrscr;

Nhap;

sc := Chia(M,N);

If sc=0 then

Begin

Writeln('Khong the chia cho 0 nguoi ');

Readln;

Halt;

End

Else Writeln('So cach chia la : ',sc);

Readln

END.

Bài 8 :

Uses Crt,graph;

Const N = 4;

h0 = 512;

Var i,h,x,y,x0,y0 : Integer;

Gd, Gm : Integer;

Procedure D(i:integer);forward;

Procedure B(i:integer);forward;

Procedure C(i:integer);forward;

Procedure A(i:integer);forward;

Procedure A;

Begin

If i>0 then

Begin

D(i-1); x:=x-h; lineto(x,y);

A(i-1); y:=y-h; lineto(x,y);

A(i-1); x:=x+h; lineto(x,y);

B(i-1);

End

End;

Procedure B;

Begin

If i>0 then

Begin

C(i-1); y:=y+h; lineto(x,y);

B(i-1); x:=x+h; lineto(x,y);

B(i-1); y:=y-h; lineto(x,y);

A(i-1);

End

End;

Procedure C;

Begin

If i>0 then

Begin

B(i-1); x:=x+h; lineto(x,y);

C(i-1); y:=y+h; lineto(x,y);

C(i-1); x:=x-h; lineto(x,y);

D(i-1);

End

End;

Procedure D;

Begin

If i>0 then

Begin

A(i-1); y:=y-h; lineto(x,y);

D(i-1); x:=x-h; lineto(x,y);

D(i-1); y:=y+h; lineto(x,y);

C(i-1);

End

End;

BEGIN

Gd := Detect; InitGraph(Gd, Gm, 'C:\tp97\tp\bgi');

If GraphResult <> grOk then Halt(1);

i:=0;

h:=h0;

x0:=h div 2;

y0:=x0;

Repeat

inc(i);

h:=h div 2;

x0:=x0+(h div 2);

y0:=y0+(h div 2);

x:=x0;

y:=y0;

Moveto(x,y);

A(i);

Until i=n;

Readln;

CloseGraph;

END.

Chú ý : Chương trình trên dùng đệ qui gián tiếp (với từ ForWard )

Thủ tục D gọi tới các thủ tục A và C ở dưới nó

Thủ tục B gọi tới các thủ tục C và A ở dưới nó

Ngoài ra , để dùng các lệnh vẽ ( chế độ đồ hoạ ) ta sử dụng Unit Graph .

B / QUAY LUI + VÉT CẠN + LỰA CHỌN TỐI ƯU

KẾT HỢP ĐỆ QUI

I / Ý nghĩa :

Trong nhiều trường hợp , nghiệm của bài toán là dãy các phần tử được xác định không theo một luật tính toán nhất định, muốn tìm nghiệm phải thực hiện từng bước ,tìm kiếm dần từng phần tử của nghiệm .Để tìm mỗi phần tử ,phải kiểm tra “đúng,sai” các khả năng có thể chấp nhận của phần tử này.

+ Nếu khả năng nào đó không dẫn tới giá trị chấp nhận được của phần tử đang xét thì phải loại bỏ khả năng đó , chuyển sang chọn khả năng khác ( chưa được chọn ) . Chú ý : mỗi khi chọn một khả năng cho một phần tử thì thông thường trạng thái bài toán sẽ thay đổi vì thế khi chuyển sang chọn khả năng khác , phải trả lại trạng thái như trước khi chọn khả năng vừa loại bỏ (nghĩa là phải quay lui lại trạng thái cũ ).

+ Nếu có 1 khả năng chấp nhận được ( nghĩa là gán được giá trị cho phần tử đang xét của nghiệm ) và chưa là phần tử cuối cùng thì tìm tiếp phần tử tiếp theo .

+ Nếu bài toán yêu cầu chỉ tìm 1 nghiệm thì sau khi chọn được 1 khả năng cho 1 phần tử của nghiệm , ta kiểm tra phần tử này đã là phần tử cuối cùng của 1 nghiệm hay chưa ( gọi là lệnh kiểm tra kết thúc 1 nghiệm ). Nếu đúng là phần tử cuối cùng của nghiệm thì : Hiện nghiệm và thoát hẳn khỏi thủ tục đệ qui bằng lệnh Halt;

Nếu bài toán yêu cầu tìm tất cả các nghiệm thì không có lệnh kiểm tra kết thúc 1 nghiệm

+ Trong việc thử mọi khả năng của 1 phần tử của nghiệm , nếu biết tìm những điều kiện để nhanh chóng loại bỏ những khả năng không thể chấp nhận được thì việc thử sẽ nhanh chóng hơn. Việc thử mọi khả năng của 1 phần tử của nghiệm cũng giống như một người đi đường , mỗi khi đến ngã N-đường , lần lượt chọn 1 đường thích hợp trong các con đường của ngã N-đường đó , nếu biết chắc chắn những đường nào đó trong các đường của ngã N-đường là đường “cụt” không thể đi tới đích thì người đi đường sẽ loại ngay những đường đó ; hoặc ngược lại nếu nhìn thấy trước những điều kiện cho phép chỉ cần đi theo một số con đường nhất định trong N đường mà vẫn tới đích nhanh chóng thì người đi đường sẽ dùng những điều kiện ấy như “la bàn “ chỉ phương hướng đi của mình Tất nhiên khi khẳng định điều này là “đúng” ,điều kia là “sai” phải hết sức thận trọng.Nếu những khẳng định” chắc chắn” chỉ là điều “ngộ nhận” thì có thể bỏ sót một số con đường tới đích, hoặc chệch hướng không thể tới đích . Một trí khôn vừa “táo bạo” vừa “chắc chắn” là trí khôn của một chương trình sáng giá !

+ Nếu tìm 1 nghiệm tốt nhất ( theo điều kiện ) thì mỗi khi tìm được 1 nghiệm , ta so sánh với nghiệm tốt nhất đã tìm được cho đến lúc này( gọi là nghiệm tối ưu ) . Nếu nghiệm vừa tìm được tốt hơn nghiệm tối ưu thì gán lại nghiệm tối ưu là nghiệm mới

Quá trình tiếp diễn cho đến khi duyệt hết các nghiệm của bài toán ta sẽ được nghiệm tối ưu của bài toán .

Tóm lại thuật toán “duyệt trên cơ sở tìm kiếm và quay lui ” - Thuật toán BackTracking - có chứa các nội dung sau :

+ Vét cạn mọi nghiệm bằng tìm kiếm tiến dần về đích đồng thời biết quay lui khi không thể tiến

+ Có thể đặt các “mắt lọc” để việc tìm kiếm nhanh chóng hơn : hoặc loại bỏ hoặc chỉ chọn một số hướng .

+ Có thể so sánh các nghiệm để có nghiệm tối ưu

+ Tuỳ theo yêu cầu , có thể chỉ tìm 1 nghiệm , cũng có thể tìm mọi nghiệm

Do thuật toán BackTracking xây dựng trên cơ sở tìm kiếm dần ,kết quả sau hình thành từ kết quả trước, nên có thể dùng các hàm, thủ tục đệ qui để thực hiện thuật toán Cụ thể có 3 dạng dàn bài thường gặp sau đây :

II / Ba dạng đệ qui thường gặp để thực hiện thuật toán BackTracking

DẠNG 1 : Tìm mọi nghiệm

Procedure Tim(k : Integer);

Begin

Vòng lặp đề cử mọi khả năng của bước thứ k trong tìm kiếm 1 nghiệm

Begin

+ Thử chọn 1 đề cử cho bước k

+ Nếu đề cử này chấp nhận được thì

Begin

* Ghi nhận giá trị đề cử;

* Lưu trạng thái mới của bài toán sau đề cử;

* Nếu chưa phải bước cuối cùng thì Tim(K+1)

Else {là bước cuối cùng} thì Hiện Nghiệm;

* Trả lại trạng thái của bài toán trước khi đề cử;

End;

End;

End;

Cũng có thể viết dưới dạng sau :

Procedure Tim(k : Integer);

Begin

Nếu bước k là bước sau bước cuối cùng thì Hiện nghiệm ;

Vòng lặp đề cử mọi khả năng của bước thứ k trong tìm kiếm 1 nghiệm

Begin

+ Thử chọn 1 đề cử cho bước k

+ Nếu đề cử này thoả mãn bài toán thì

Begin

* Ghi nhận giá trị đề cử;

* Lưu trạng thái mới của bài toán sau đề cử;

* Tim(k+1);

* Trả lại trạng thái của bài toán trước khi đề cử;

End;

End;

End;

Thí dụ : Bài toán con mã đi tuần ( Hiện tất cả các nghiệm)

Cách 1 :

Program Madequy;

Uses Crt;

Const Max = 8;

Fi = 'madq.inp';

D : Array [1..8] of -2..2 = (-2,-2,-1,1,2,2,1,-1);

C : Array [1..8] of -2..2 = (-1,1,2,2,1,-1,-2,-2);

Var

F : Text;

T1,T2 : longint;

A : Array[1..Max,1..Max] of Integer;

x,y,k,dem,n,nsq : Integer;

Procedure DocFi;

Begin

Assign(F,Fi);

{$I-} Reset(F); {$I+}

If Ioresult<>0 then

Begin Writeln('Loi File '); Readln; Halt; End;

Readln(F,N);

Nsq := N*N;

Readln(F,x,y);

Close(F);

End;

Procedure Hien;

Var i,j : Integer;

Begin

Inc(dem);

Assign(F,Fi);

Append(F); {Ghi nghiệm ngay cuối File dữ liệu Input }

Writeln(F,'Nghiem thu ',dem);

For i:=1 to N do

Begin

For j:=1 to N do

Write(F,A[i,j]:3);

Writeln(F);

End;

Close(F);

End;

Procedure Try(k:Integer;x,y: Integer);

Var i,j,u,v : Integer;

Begin

If k > nsq then Hien Else

For i:=1 to 8 do

Begin

u:=x+D[i]; v:=y+C[i];

If (u in [1..n]) and (v in [1..n]) and (A[u,v]=0) then

Begin

A[u,v]:=k;

try(k+1,u,v);

A[u,v]:=0;

End;

End;

End;

BEGIN

Clrscr;

Fillchar(A,Sizeof(A),0);

dem:=0;

DocFi;

A[x,y]:=1;

Try(2,x,y);

END.

Cách 2 : ( Chuyển mảng 2 chiều sang 1 chiều , hiệu suất hơn )

Uses Crt;

Const N = 12;

Type Mt = Array[1..(n+4)*(n+4)] of Integer;

Var x : Mt;

K : Array[1..8] of Integer;

db,spt,d,c,L,z : Integer;{db :so o dau bang }

Procedure Khoitao;

Var i,j,all : Integer;

Begin

db := 2*(L+4)+2;

all := (L+4)*(L+4);

For i:=1 to all do X[i] := 1;

For i:=1 to L do

For j:=1 to L do

X[db+(i-1)*(L+4)+j] := 0;

X[db+(d-1)*(L+4)+c] := 1;

K[1] := 2*L+9; K[2] := 2*L+7;

K[3] := L+6; K[4] := L+2;

K[5] := -K[4]; K[6] := -K[3];

K[7] := -K[2]; K[8] := -K[1];

z := 0; { So nghiem }

spt:= L*L;

End;

Procedure Hien;

Var i,j : Integer;

Begin

Inc(z);

Writeln('Nghiem : ',z);

For i:=3 to L+2 do

Begin

For j:=3 to L+2 do

Write(X[(i-1)*(L+4)+j]:3);

Writeln;

End;

End;

Procedure Tim(t,p : Integer);{ Di toi o thu t,ma dang o o thu p cua x }

Var i : Integer;

Begin

If t=spt then Hien ;

For i:=1 to 8 do

If x[p-k[i]]=0 then

Begin

x[p-k[i]] := t+1;

Tim(t+1,p-k[i]);

x[p-k[i]] := 0;

End;

End;

BEGIN

Clrscr;

Write('Kich thuoc ban co : ');

Readln(L);

Write('Nhap 2 toa do o xuat phat : ');

Readln(d,c);

Khoitao;

Tim(1,db+(d-1)*(L+4)+c);

If z=0 then Writeln('Khong co nghiem ');

END.

DẠNG 2 : Tìm một nghiệm :

Procedure Tim(k : Integer);

Begin

Vòng lặp đề cử mọi khả năng của bước thứ k trong tìm kiếm 1 nghiệm

Begin

+ Thử chọn 1 đề cử

+ Nếu đề cử này chấp nhận được thì

Begin

* Ghi nhận giá trị đề cử

* Lưu trạng thái mới của bài toán sau đề cử

* Nếu là bước cuối cùng thì

Begin

Hiện Nghiệm

Thoát

End

* Trả lại trạng thái trước khi đề cử

End;

End;

End;

Hoặc có thể viết dưới dạng sau :

Procedure Tim(k : Integer);

Begin

Nếu là bước sau bước cuối cùng thì

Begin

Hiện Nghiệm

Thoát

End

Còn không :

Tạo vòng lặp đề cử mọi khả năng của bước thứ k trong tìm kiếm 1 nghiệm

Begin

+ Thử chọn 1 đề cử

+ Nếu đề cử này thoả mãn bài toán thì

Begin

* Ghi nhận giá trị đề cử

* Lưu trạng thái mới của bài toán sau đề cử

* Nếu chưa phải bước cuối cùng thì Tim(K+1)

* Trả lại trạng thái của bài toán trước khi đề cử

End;

End;

End;

Trong bài toán tìm 1 nghiệm , người ta thường đưa thêm vào các điều kiện đối với các khả năng đề cử để bỏ bớt đi 1 số khả năng đề cử hoặc làm cho khả năng đề cử thu hẹp lại

Thí dụ :

+ Điều kiện cần để một khả năng được chấp nhận ở bước thứ i là bước i+1 cũng có khả năng chấp nhận một đề cử của nó và bước thứ i chưa phải bước cuối cùng . Vì vậy có thể nhanh chóng tới đích nếu đưa ra qui luật chọn đề cử của bước thứ i như sau :

ở bước thứ i ta sẽ chọn đề cử nào mà theo nó đưa ta tới bước i+1 có ít khả năng chấp nhận nhất ( nghĩa là bước thứ i+1 vẫn có khả năng đề cử của nó , nhưng số đề cử ít )

+ Một cách khác : Khi chấp nhận một khả năng đề cử cho bước thứ i , có thể sẽ tác động tới trạng thái bài toán . Vì vậy ta tính toán trước nếu chọn đề cử này thì trạng thái bài toán có thay đổi quá mức giới hạn cho phép hay không ?.Nghĩa là có vượt qua cận trên hoặc cận dưới của bài toán hay không ? Nếu vượt qua thì ta không chọn đề cử ấy Trong nhiều bài toán những cận này cũng thu hẹp dần theo từng bước , nếu ta tìm được sự thay đổi của cận theo từng bước thì các khả năng đề cử ngày càng hẹp dần , bài toán nhanh chóng kết thúc .

Trở lại bài toán con mã đi tuần nhưng với yêu cầu chỉ hiện 1 nghiệm

Cách 1 : ( Thông thường )

Uses Crt;

Const Max = 7;

Fi = 'madq.inp';

D : Array [1..8] of -2..2 = (-2,-2,-1,1,2,2,1,-1);

C : Array [1..8] of -2..2 = (-1,1,2,2,1,-1,-2,-2);

Var

F : Text;

T1,T2 : longint;

A : Array[1..Max,1..Max] of Integer;

x,y,Lx,Ly,k,dem,n,nsq : Integer;

Procedure DocFi;

Begin

Assign(F,Fi);

{$I-} Reset(F); {$I+}

If Ioresult<>0 then

Begin

Writeln('Loi File ');

Readln;

Halt;

End;

Readln(F,N);

Nsq := N*N;

Readln(F,x,y);

Lx := x;

Ly := y;

Close(F);

End;

Procedure Hien;

Var i,j : Integer;

Begin

Inc(dem);

Assign(F,Fi);

Append(F);

Writeln(F,'Nghiem thu ',dem);

For i:=1 to N do

Begin

For j:=1 to N do

Write(F,A[i,j]:3);

Writeln(F);

End;

Close(F);

End;

Procedure Try(k:Integer;x,y: Integer);

Var i,j,u,v : Integer;

Begin

If k>nsq then Hien Else

Begin

If dem=1 then

Begin

Writeln('Da xong . Moi an phim Enter ');

Readln;

Halt;

End;

For i:=1 to 8 do

Begin

u:=x+D[i];

v:=y+C[i];

{Writeln(u,' ',v);}

If (u in [1..n]) and (v in [1..n]) and (A[u,v]=0) then

Begin

A[u,v]:=k;

try(k+1,u,v);

A[u,v]:=0;

End;

End;

If (u=Lx) and (v=Ly) then

Begin

Writeln('Vo nghiem ');

Readln;

Halt;

End

End;

End;

BEGIN

Clrscr;

Fillchar(A,Sizeof(A),0);

dem:=0;

DocFi;

A[x,y]:=1;

k:=1;

Try(2,x,y);

END.

Cách 2 :{ Đặt mắt chọn hướng đi nhanh chóng tới đích là chọn ô có bậc thấp nhất }

{Hiệu suất chương trình tăng đáng kể - Lời giải : Trương Vũ Hưng 12CT 1996}

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+}

{$M 16384,0,655360}

Uses crt;

Const

Max = 20;

dx : Array[1..8] of integer=(-2,-1,1,2, 2, 1,-1,-2);

dy : Array[1..8] of integer=( 1, 2, 2,1,-1,-2,-2,-1);

Var N,x,y : Byte;

A : Array[-1..max+2,-1..max+2] of Integer;

Procedure Nhap;

Begin

Write('Nhap kich thuoc ban co = ');

Readln(n);

Write('Nhap toa do xuat phat x,y = ');

Readln(x,y);

End;

Procedure Hien;

Var

i,j : Integer;

Begin

For i:=1 to n do

Begin

For j:=1 to n do write(a[i,j]:4);

Writeln;

End;

End;

Procedure Hangrao;

Var i,j : Integer;

Begin

Fillchar(a,sizeof(a),0);

For i:=-1 to n+2 do

For j:=1 to 2 do

Begin

A[i,1-j]:=-1;

A[i,n+j]:=-1;

A[1-j,i]:=-1;

A[n+j,i]:=-1;

End;

End;

Function Bac(x,y:integer) : Integer;

Var i,dem : Byte;

Begin

dem:=0;

For i:=1 to 8 do

If a[x+dx[i],y+dy[i]]=0 then inc(dem);

Bac:=dem;

End;

Procedure Vet(so,i,j:integer);

Var k,lk ,Ldem,p : Byte;

Begin

If so>n*n then

Begin

Clrscr;

Hien;

Readln;

Halt;

End;

Ldem:=9;

For k:=1 to 8 do

If A[i+dx[k],j+dy[k]]=0 then

Begin

P := Bac(i+dx[k],j+dy[k]);

If {( P>=0 ) and} ( Ldem>P ) then

Begin

Lk := k;

Ldem := p;

End;

End;

If Ldem = 9 then exit; {Ldem =9: ô (i,j) tắc nghẽn, nên Exit }

{Ldem<9 : Sẽ chọn đề cử là ô có bậc nhỏ nhất}

A[i+dx[Lk],j+dy[Lk]] := So;

Vet(so+1,i+dx[Lk],j+dy[Lk]);

A[i+dx[Lk],j+dy[Lk]] := 0;

End;

Procedure Lam;

Begin

Hangrao;

A[x,y]:=1;

Vet(2,x,y);

End;

BEGIN

Clrscr;

Nhap;

Lam;

END.

Lời bình : Ngoài việc sử dụng đệ qui kết hợp quay lui , chương trình còn dựa trên thuật toán “Háu ăn ‘ : có lợi thì làm để nhanh chóng đạt đích . Cụ thể là ở mỗi bước SO sẽ chọn ô của bước (S0+1) tiếp theo nếu từ ô ấy có ít hướng đi tiếp tới ô kháccủa bước (S0+2) .Cây phân nhánh sẽ ít nhánh đi đáng kể . Tất nhiên phải chứng minh rằng, với cách thức đi như thế vẫn bảo đảm có ít nhất 1 nghiệm.

Ta thấy :Bằng cách chọn ô có bậc thấp và phải xuất phát từ ô (1,1) nên cứ đi vòng quanh bàn cờ dần vào trong luôn có đường đi vào trong ruột bàn cờ , vì bậc các ô bên ngoài lớn hơn bậc các ô bên trong, và bậc các ô bên trong còn lớn hơn 1 khi mã chưa vào sâu trongbàn cờ .Chỉ khi gần kết thúc mới nảy sinh vấn đề : có đường đi tiếp nữa hay không ( còn ô có bậc lớn hơn 1 hay không ) , nghĩa là khi đó ta mới biết cách đi này có đúng đắn không ? ( Các em hãy tự chứng minh , hoặc ít nhất hãy thử nghiệm với các giá trị N=5,6,7,8,..20 nếu vẫn có nghiệm thì rõ ràng cách đi như thế đã đúng với các trường hợp này ) và như thế kết quả thu được cũng đã quá bất ngờ so với lập trình bình thường Vậy ‘Háu ăn’ nhiều khi cũng có lợi lắm đấy .

*

Một khó khăn khác của loại toán hiện 1 nghiệm là : trường hợp bài toán vô nghiệm cần viết chương trình như thế nào ? Phải duyệt hết mọi khả năng mới rõ kết luận vô nghiệm hay không vô nghiệm . Nghĩa là đã đi theo mọi nhánh nhưng nhánh nào cũng đều không tới đích ,do đó theo quy luật cứ quay lui mãi để tìm kiếm thì đến lúc nào đó dẫn đến tình trạng phải trở về ô xuất phát Vậy khi gặp ô đề cử mới trùng với ô xuất phát thì bài toán vô nghiệm .(xem lại bài giải trang 330) .

Ta chỉ cần thêm vào mẫu 1 (Dạng tìm mọi nghiệm ) một chút “gia vị” là có ngay dạng tương ứng với bài toán vô nghiệm :

Procedure Tim(k : Integer);

Begin

Vòng lặp đề cử mọi khả năng của bước thứ k trong tìm kiếm 1 nghiệm

Begin

+ Thử chọn 1 đề cử cho bước k

+ Nếu đề cử này chấp nhận được thì

Begin

* Ghi nhận giá trị đề cử;

* Lưu trạng thái mới của bài toán sau đề cử;

* Nếu chưa phải bước cuối cùng thì Tim(K+1)

Else {là bước cuối cùng} thì Hiện Nghiệm;

* Trả lại trạng thái của bài toán trước khi đề cử;

End;

End;

Nếu đề cử cuối cùng ra khỏi vòng lặp trùng với giá trị của bước thứ nhất thì

Begin

Thông báo vô nghiệm

Thoát

End;

End;

Cũng có thể viết dưới dạng sau :

Procedure Tim(k : Integer);

Begin

Nếu bước k là bước sau bước cuối cùng thì Hiện nghiệm ;

Vòng lặp đề cử mọi khả năng của bước thứ k trong tìm kiếm 1 nghiệm

Begin

+ Thử chọn 1 đề cử cho bước k

+ Nếu đề cử này thoả mãn bài toán thì

Begin

* Ghi nhận giá trị đề cử;

* Lưu trạng thái mới của bài toán sau đề cử;

* Tim(k+1);

* Trả lại trạng thái của bài toán trước khi đề cử;

End;

End;

Nếu đề cử cuối cùng ra khỏi vòng lặp trùng với giá trị của bước thứ nhất thì

Begin

Thông báo vô nghiệm

Thoát

End;

End;

Hoặc có thể xử lý bài toán vô nghiệm như chương trình sau :

Uses Crt;

Const N =5; nsq=n*n;

A : Array[1..8] of integer=(2,1,-1,-2,-2,-1,1,2);

B : Array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1);

Type Index=1..n;

Var i,j : Index;

q : Boolean;

h : Array[index,index] of integer;

Procedure Try(i:integer;x,y:index;Var q:Boolean);

Var k,u,v : Integer;

q1 : Boolean;

Begin

k:=0;

Repeat

Inc(k);

q1:=false;

u :=x+a[k];

v :=y+b[k];

If (1<=u) and (u<=n) and (1<=v) and (v<=n) then

If h[u,v]=0 then

Begin

h[u,v]:=i;

If i< nsq then

Begin

Try(i+1,u,v,q1);

If not q1 then h[u,v]:=0;

End

Else q1:=true;

End

Until q1 or (k=8);

q:=q1;

End;

BEGIN

Clrscr;

q:=False;

For i:=1 to n do

For j:=1 to n do h[i,j]:=0;

h[1,1]:=1;

Try(2,1,1,q);

If q then

For i:=1 to n do

Begin

For j:=1 to n do Write(h[i,j]:5);

Writeln;

End

Else Writeln(' Không có nghiệm ');

END.

Người lập trình đã đưa thêm vào thủ tục đệ qui một tham biến q với chức năng làm nhiệm vụ thông báo tình trạng đã có nghiệm hay chưa ? q chỉ nhận giá trị TRUE khi bước tiếp theo là bước cuối cùng . Do đó nếu sau khi đã vét cạn mọi khả năng vẫn không đi tới bước cuối cùng , tham biến q sau khi thoát khỏi thủ tục đệ qui Try sẽ có giá trị FALSE ban đầu . Vậy sau thủ tục đệ qui Try , nếu q=TRUE thì có nghiệm , nếu q =FALSE là vô nghiệm .Nhiệm vụ của q như cái gậy dò dẫm tìm đường vậy ! Có thể tăng độ dài của gậy lên không, để nó thông báo kết thúc sớm hơn không ? ( Các em hãy chạy chương trình với N=4 ).

DẠNG 3 : Tìm nghiệm tối ưu

Có 3 cách thường dùng :

Cách 1 :

Procedure Tim(k : Integer);

Begin

Nếu bước k là bước sau bước cuối cùng thì

Begin

Nếu tìm được nghiệm mới thì So sánh nghiệm mới với nghiệm lưu tối ưu trước để chọn lại nghiệm lưu tối ưu

End;

Vòng lặp đề cử mọi khả năng của bước thứ k trong tìm kiếm 1 nghiệm

( Chú ý nên kết hợp với nghiệm lưu tối ưu đã có để thu hẹp diện đề cử )

Begin

+ Thử chọn 1 đề cử cho bước k

+ Nếu đề cử này thoả mãn bài toán thì

Begin

* Ghi nhận giá trị đề cử;

* Lưu trạng thái mới của bài toán sau đề cử;

* Tim(k+1);

* Trả lại trạng thái của bài toán trước khi đề cử;

End;

End;

End;

Thí dụ trong bài toán du lịch : Tìm đường đi qua N thành phố , mỗi thành phố chỉ qua 1 lần , sao cho tốn ít chi phí vận chuyển nhất . Mỗi nghiệm của bài toán là 1 véc tơ N thành phần đó là dãy tên có thứ tự chọn của N thành phố . Giả sử đã tìm được 1 số nghiệm , và trong đó nghiệm tốt nhất có chí phí tương ứng là CPMax đồng , bây giờ tìm tiếp các nghiệm còn lại .Đặt tình huống ta đang xây dựng tới thành phần thứ i (i<N) của nghiệm tiếp theo ,gọi CP2 là tổng chi phí tối thiểu của N-i thành phố còn lại , CP1 là tổng chi phí qua i thành phố đã chọn

Nếu một đề cử nào đó của bước i mà CP1+CP2 > CPMax thì đề cử này bị loại .

Như vậy biết kết hợp với nghiệm tối ưu của các nghiệm trước đó thì việc tìm kiếm nghiệm tiếp theo được nhanh chóng hơn .

Cách 2 :

Procedure Tim(k : Integer);

Begin

Vòng lặp đề cử mọi khả năng của bước thứ k trong tìm kiếm 1 nghiệm

( Chú ý nên kết hợp với nghiệm lưu tối ưu đã có để thu hẹp diện đề cử )

Begin

+ Thử chọn 1 đề cử cho bước k

+ Nếu đề cử này chấp nhận được thì

Begin

* Ghi nhận giá trị đề cử;

* Lưu trạng thái mới của bài toán sau đề cử;

* Nếu chưa phải bước cuối cùng thì Tim(K+1)

Else {là bước cuối cùng} thì

Begin

So sánh nghiệm mới với nghiệm tối ưu trướcđể chọn lại nghiệm tối ưu

End;

* Trả lại trạng thái của bài toán trước khi đề cử

End;

End;

End;

Cách 3 : Thường dùng trong các bài toán chọn một số phần tử trong N phần tử cho trước để tạo thành 1 nghiệm .Thủ tục dưới đây thực hiện thử chọn dần phần tử i cho nghiệm tốt nhất , S : điều kiện chấp nhận của các phần tử i sẽ chọn , F là cận trên của hàm mục tiêu cần tối ưu ( Xem lời giải bài toán cái túi - Trang 343 )

Procedure Tim( i : Integer; S ,F: LongInt)

Begin

* Nếu phần tử i thoả mãn điệù kiện chấp nhận S thì

Begin

+ Ghi phần tử thứ i vào tập nghiệm

+ Nếu i chưa phải phần tử cuối cùng then Tim(i+1,S _mới ,F)

Còn không :

Nếu cận trên còn lớn hơn so với Lưu cận là LF thì

Begin LF := F; LưuNghiệm := Nghiệm ; End;

+ Trả lại trạng thái cũ : Loại bỏ phần tử i khỏi tập nghiệm .

End;

* Giảm Cận trên của hàm mục tiêu : chọn cận mới là F_mới

* Nếu F_Mới > LF thì

Begin

Nếu i chưa là phần tử cuối cùng thì Tim(i+1,S,F_Mới)

Còn không :

Begin LưuF := F_Mới; Lưunghiệm := Nghiệm; End;

End;

End;

Bài toán 1:

Bài toán người du lịch : Cho N thành phố , giá cước phí vận chuyển từ thành phố i tới thành phố j là C ij . Yêu cầu :

File dữ liệu vào là ‘DULICH.INP’ như sau

Dòng đầu là N , XP , Dich ( N số thành phố , XP : th/ phố xuất phát , Dich : th/phố đích )

N dòng tiếp theo :

Số đầu dòng là i , các cặp số tiếp theo là j và C ij của ma trận C(N,N)

File dữ liệu ra là ‘DULICH.OUT’

Dòng đầu : Liệt kê hành trình tốn ít chi phí nhất , lần lượt qua N thành phố ( Mỗi thành phố chỉ 1 lần )

Dòng tiếp theo : Tổng chi phí .

TEST :

DULICH.INP

10 1 8

1 2 3 5 2 7 3 9 3 10 7

2 5 1 6 6 10 3

3 1 7 8 1 10 7

4 1 3 2 2 5 3 9 7

5 1 2 3 7 4 5 6 1 7 8 8 2 9 3

6 1 8 2 7 3 5 7 6 8 1 10 8

7 1 1 3 3 5 2 6 5 8 6 10 1

8 2 2 3 7 6 4 9 2

9 2 5 6 1

10 2 1 4 6 5 2 7 3 8 6

DULICH.OUT

1 5 8

6

Bài chữa : Bài toán du lịch

Uses Crt;

Const MN = 100;

TF1 = 'DULICH.INP';

TF2 = 'DULICH.OUT';

Var F : Text;

C : Array[1..MN,1..MN] of Integer;

KQ,LKQ : Array[1..MN] of Byte;

D : Array[1..MN] of Boolean;

N,Lcs,cs,xp,Dich : Byte;

Tong,LTong : LongInt;

Procedure Batdau;

Begin

FillChar(C,Sizeof(C),0);

FillChar(D,Sizeof(D),False);

FillChar(KQ,Sizeof(KQ),0);

FillChar(LKQ,Sizeof(LKQ),0);

End;

Procedure TaoF;

Var F : Text;

i,j,k : Byte;

Begin

Write('Nhap so thanh pho : ');Readln(N);

Write('Nhap thanh pho xuat phat : ');Readln(xp);

Write('Nhap thanh pho se toi : ');Readln(Dich);

Assign(F,TF1);

ReWrite(F);

Writeln(F,N,' ',Xp,' ',Dich);

Randomize;

For i:=1 to N do

Begin

Write(F,i:4);

For j:=1 to N do

Begin

k := Random(2);

If i=j then k:=0;

If k=1 then Write(F,j:4,(Random(8)+1):2);

End;

Writeln(F);

End;

Close(F);

End;

Procedure DocF;

Var i,j : Byte;

F : Text;

Begin

Assign(F,TF1);

Reset(F);

Readln(F,N,XP,Dich);

While Not SeekEof(F) do

Begin

Read(F,i);

While Not Eoln(F) do

Begin

Read(F,j);

Read(F,C[i,j]);

End;

End;

Close(F);

Tong := 0;

LTong:= MaxInt div 2;

cs := 1;

KQ[cs] := xp;

D[xp] := True;

End;

Procedure Hien;

Var i,j : Byte;

Begin

For i:=1 to n do

Begin

For j:=1 to N do

If C[i,j]>0 then Write(C[i,j]:2)

Else Write('*':2);

Writeln;

End;

End;

Procedure Tim (i: Byte;Tong : LongInt);

Var j : Byte;

Begin

For j:=1 to N do

If (Not D[j]) and (i<>j) then

If (C[i,j]>0) and (Ltong-Tong>=C[i,j]) then

Begin

Inc(cs);

KQ[cs] := j;

D[j] := True;

Tong := Tong + C[i,j];

If (j<>dich) then Tim(j,Tong)

Else

If (Tong<Ltong) or ((Tong=Ltong) and (cs<Lcs)) then

Begin

Ltong := Tong;

LKQ := KQ;

Lcs := cs;

End;

Dec(cs);

D[j] := False;

Tong := Tong - C[i,j];

End;

End;

Procedure HienKQ;

Var i : Byte;

Begin

For i:=1 to Lcs do

Write(LKQ[i]:4);

Writeln;

Writeln('Tong chi phi la : ',LTong);

End;

BEGIN

Clrscr; {TaoF;}

Batdau; DocF; Nhonhat := Min;

If XP= Dich then

Begin Writeln(Xp); Writeln(‘Khong di chuyen ‘);Readln;Halt;End;

Tim(xp,Tong); {Hien;Chi goi khi N<=10}

Writeln;

HienKq;

Readln;

END.

Bài toán 2 ( Bài toán cái túi ) :

Tìm cách chọn các đồ vật trong N đồ vật (mỗi loại đồ vật chỉ chọn 1), xếp vào va li sao cho tổng giá trị của các đồ vật trong va ly là lớn nhất nhưng tổng trọng lượng của chúng không vượt quá giới hạn qui định là LimW. Giả sử N, Wi , Vi đều nguyên dương ( Wi : trọng lượng vật i , Vi : giá trị vật i )

Dữ liệu vào : cho trong File ‘VALY.INP’ tổ chức như sau

Dòng đầu : 2 số N LimW

N dòng tiếp theo : Mỗi dòng 2 số Wi Vi

Dữ liệu ra : File ‘VALY.OUT’

Dòng đầu : số LimW

Các dòng tiếp theo : Mỗi dòng 3 số : i Wi Vi là số thứ tự ,trọng lượng,giá trị của các đồ vật được chọn vào va ly.

Bài giải

Uses Crt;

Const MN = 30;

TF = 'Valy.inp';

TF2 = 'Valy.out';

Type Index = 1..MN;

Dovat = Record

W,V : Integer; { W Trong luong ,V Gia tri }

End;

Var i,N : Index;

A : Array[Index] of Dovat;

KQ,LKQ : Set of Index;

LimW,LCanV,CanV : Integer;

Procedure DocF;

Var i : Index;

F : Text;

Begin

Assign(F,TF);

Reset(F);

Readln(F,N,LimW);

For i:=1 to N do

With A[i] do

Begin

Readln(F,W,V);

CanV := CanV+V;

End;

Close(F);

End;

Procedure Try(i : Index;Tw,CanV : Integer);

Var CanV1 : Integer;

Begin

If Tw + A[i].w <= LimW then

Begin

KQ := KQ+[i];

If i<N then Try(i+1,Tw+ A[i].w,Canv)

Else

If CanV > LCanV then

Begin

LCanV := Canv;

LKQ := KQ;

End;

KQ := KQ-[i];

End;

CanV1:= CanV - A[i].v;

If CanV1>LCanV then

Begin

If i<N then Try(i+1,Tw,CanV1)

Else

Begin

LCanV := CanV1;

LKQ := KQ;

End;

End;

End;

Procedure GhiF;

Var i : Index;

F : Text;

Begin

Assign(F,TF2);

ReWrite(F);

Writeln(F,'Gioi han trong luong : ',LimW);

For i:=1 to N do

If i in LKQ then

With A[i] do

Writeln(F,i:4,' : TrLG = ',W:4,', GT = ',V:4);

Close(F);

End;

BEGIN

DocF;

LCanV := 0;

Try(1,0,CanV);

GhiF;

Writeln('Da xong ');

Readln;

END.

BÀI TẬP ĐỆ QUI CÙNG THUẬT TOÁN TÌM KIẾM BẰNG VÉT CẠN VÀ QUAY LUI BACKTRACKING

C11-B-01 Lập trình đặt 8 quân hậu lên bàn cờ sao cho không quân nào ăn được quân nào ( Bài toán tương đương : 8 quân hậu khống chế hết các ô của bàn cờ )

C11-B-02 Điền các số từ 1 đến N*N vào các ô của hình vuông N*N (N<=5) ô vuông theo qui cách : Nếu ô (x,y) có số k thì hoặc ô (x+2,y-2) hoặc ô (x+2,y+2) hoặc ô (x-2,y+2) hoặc ô (x-2,y-2) hoặc ô (x+3,y) hoặc ô (x-3,y) hoặc ô (x,y+3) hoặc ô (x,y-3) chứa số K+1 . Nhập từ bàn phím số N và toạ độ x,y của ô xuất phát Hiện các cách sắp xếp theo dạng ma trận vuông trên màn hình , và tổng số cách sắp xếp .

C11-B-03 Trong hình vuông 4*4 ô vuông hãy sắp xếp 16 chữ cái : 4 chữ a, 4 chữ b, 4 chữ c , 4 chữ d sao cho mỗi dòng cũng như mỗi cột , mỗi chữ cái chỉ có mặt đúng 1 lần .

C11-B-04 (Tìm đường trong mê cung )

Mê cung gồm N phòng ( N<100) có các hành lang nối với nhau đó là nơi trú ngụ của quái vật Minotau ( Nửa bò , nửa người ) . Ban ngày quái vật thường ra khỏi mê cung phun lửa giết chóc tàn phá với sức mạnh không ai địch nổi . Ban đêm quái vật ngủ trong mê cung và hòn than lửa của nó được cất ở phòng “Dich”; ai lấy được hòn than lửa ấy thì chinh phục được quái vật. Theo lời thỉnh cầu của công chúa Arian , anh hùng Têđê nhận lời sẽ vào mê cung thu phục quái vật . Têđê xuất phát từ phòng XP và quyết định dùng thuật toán tìm kiếm bằng vét cạn và quay lui (cùng cuộn chỉ của nàng Arian tặng chàng để quay lui thuận tiện ) . Trong mê cung tối om dầy đặc phòng và hành lang - chàng đã tìm được được phòng “Dich” và thu phục quái vật .

Em hãy lập trình hiện đường đi của Têđê .

Dữ liệu vào : File ‘MECUNG.TXT’ tổ chức như sau :

+ Dòng đầu là 3 số N XP Dich

+ N dòng tiếp theo :

Dòng thứ i : Đầu tiên là số i ( 1≤ i ≤ N ) tiếp theo là các số j ( hai số liền nhau cách nhau ít nhất 1 khoảng trống ) thể hiện có hành lang một chiều từ phòng i sang phòng j .

Thông tin ra :

Đường đi của Têđê : liệt kê lần lượt các phòng chàng sẽ đi qua ( không kể những đoạn phải quay lại )

C11-B-05 Trong biểu thức (...(1?2)?3)?4)?5)...)?N , hãy thay các dấu ? bằng 1 trong 4 phép tính sau : + , - , * , / sao cho giá trị của biểu thức đã cho bằng S . Gọi số lượng các biểu thức tạo ra là d .

Yêu cầu :

Dữ liệu vào ( gọi là dữ liệu Input ) :

Nạp từ bàn phím số N và S nguyên dương thoả mãn 1<N<255 ; -10⁹ <S< 10⁹

Dữ liệu ra ( gọi là dữ liệu Output ) :

File ‘BIEUTHUC.TXT’

+ Nếu d=0 thì dòng đầu ghi số 0

+ Nếu d>0 thì

Ghi d dòng , mỗi dòng là 1 biểu thức tìm được

Dòng cuối cùng là số d

Thí dụ :

Vào : N=5 S=1

Ra :

(((1+2)-3)-4)+5)

(((1+2)*3)-4)/5)

(((1+2)/3)+4)/5)

(((1-2)+3)+4)-5)

(((1*2)-3)*4)+5)

(((1/2)*3)*4)-5)

6

C11-B-06

Nhập phân số T/M ( 0<T<M<969696 ; T,M nguyên ) . Lập trình thực hiện các yêu cầu :

a) Biểu diễn phân số dưới dạng phân số tối giản.

b) Biểu diễn phân số này dưới dạng tổng các phân số có tử số bằng 1 . Tổng càng ít số hạng càng tốt .

( Đề thi Olempic sinh viên Việt Nam - khối không chuyên 1996 )

C11-B-07

Cho N quả cân có các khối lượng tương ứng là : d₁, d₂,..., d_N ( nguyên) và có 1 cân 2 đĩa (khi cân có thể đặt một số quả cân trên đĩa nào cũng được )

a) Bộ quả cân đó có thể cân được những vật có khối lượng bao nhiêu ?

b) Cho vật có khối lượng M , cân nó bằng những quả cân nào ?

C11-B-08

Bài toán đổi tiền : Cho biết trong kho còn những loại tiền lẻ L₁, L₂,..., L_K vói số lượng tương ứng là S₁, S₂,..., S_K tờ mỗi loại . Tìm cách đổi số tiền ST thành các loại tiền lẻ có trong kho . Giả thiết các số L₁, L₂,..., L_K, S₁, S₂,..., S_K nguyên dương.

C11-B-09

Bài toán khôi phục hiện trạng cũ : Xét một ô đất hình chữ nhật M*N ô vuông . Mỗi ô đất có thể có 1 ngôi nhà đã xây hoặc chưa có ngôi nhà nào .Người ta mô tả miếng đất này bằng 1 bảng hình chữ nhật M*N ô vuông , mỗi ô chứa 1 số nguyên bằng tổng số nhà đã xây ở các ô xung quanh nó ( các ô có chung đỉnh hoặc cạnh ) . Hãy nêu rõ bản đồ về tình trạng các nhà đã xây ở khu đất đó : Ô nào có nhà thì ghi số 1 ô nào chưa có nhà thì ghi số 0 .

Thí dụ :

Khu đất với số liệu mô tả ban đầu Khu đất được khôi phục lại số liệu

C11-B-10

Bài toán du lịch qua đủ N thành phố ( mỗi thành phố chỉ qua 1 lần , trừ thành phố xuất phát ) rồi quay trở lại thành phố xuất phát

Coi như đường đi 2 chiều. Tìm đường đi tốn ít cước phí nhất và càng ngắn càng tốt

( cước phí là ưu tiên số một ) .

File dữ liệu : ‘Dulich2.inp’

Dòng đầu N , XP

Các dòng tiếp theo :

Số đầu của 1 dòng là i , các số tiếp theo : tạo thành từng nhóm 3 số j,Cij ,Hij ( j>i) và có ý nghĩa : Từ i có thể đi tới j với cước phí Cij và khoảng cách là Hij

File dữ liệu ra : ‘Dulich2.out’

Một số dòng đầu : các mã số các thành phố nêu hành trình

Dòng tiếp : 2 số : Tổng chi phí , Tổng đường dài của hành trình .

C11-B-11

Bài toán phát hành tem :

Trong một nước người ta phát hành N loại tem khác nhau về giá trị ( chẳng hạn loại tem 1 đồng , 3 đồng , . . . ) Người ta không cho phép dán trên mỗi vật phẩm quá M con tem ( có thể dán tem cùng loại ) . Giá cước mỗi vật phẩm là một số nguyên đồng . Nhập M,N từ bàn phím . Xác định tất cả các bộ giá trị của các loại tem cần phát hành sao cho dãy giá cước của các vật phẩm được gửi là một dãy dài các số nguyên liên tiếp dài nhất 1,2,3...,s

Thí dụ :

Số lại tem : N = 4

Số tem nhiều nhất trên 1 vật phẩm : M = 5

thì dãy giá cước gửi được dài nhất là 1,2,3, . . . , S = 71 với bộ tem {1,4,12,21} hoặc bộ {1,5,12,28 }

C11-B-12

Bài toán điều hành ôtô buýt :

Ông A ở bến ô tô buýt ghi lại thời điểm các ô tô đến bến thành 1 dãy số . Biết có nhiều tuyến xe cùng đến bến này . Hai ôtô liên tiếp của cùng 1 tuyến luôn cách nhau một khoảng thời gian cố định và mỗi tuyến có ôtô chạy đều đặn trong khoảng cả giờ ( tính theo đơn vị nguyên phút , từ 0 phút đến 59 phút ). Tại cùng một thời điểm có thể có nhiều ôtô của các tuyến khác nhau tới bến , cũng có thể khoảng thời gian cố định của 2 xe ôtô liên tiếp trên 2 tuyến nào đó như nhau

Hãy tìm số tuyến xe ít nhất theo dãy số của ông A

Yêu cầu :

File dữ liệu vào gồm 1 dòng là dãy số của ông A

File dữ liệu ra đặt tên là ‘OTO.OUT’ mỗi dòng là 1 tuyến ôtô gồm 2 con số : thời điểm ôtô đầu tiên tuyến tới bến , sau đó là khoảng thời gian cố định của 2 xe ôtô liên tiếp của tuyến này .

C11-B-13

Bài toán tô màu

Trên mặt phẳng cho N điểm , một số điểm trong chúng được nối với nhau bởi các đoạn thẳng. Hãy dùng số màu ít nhất để tô màu các điểm theo qui luật : 2 điểm có chung đoạn thẳng nối chúng với nhau thì được tô bằng 2 màu khác nhau .

Thí dụ :

Điểm 2 và 5 sẽ tô màu số 1

Điểm 1,3,4 sẽ tô màu số 2

Vậy số màu cần dùng là : 2

C11-B-14

Bài toán giao thông

Tại một đầu mối giao thông người ta quản lý các tuyến đường qua nó . Ta coi 1 tuyến đường như 1 điểm trên mặt phẳng . Nếu 2 tuyến không được đồng thời cùng thông đường (nghĩa là không cùng cho xe chạy một lúc ) thì 2 điểm tương ứng được nối với nhau bằng 1 đoạn thẳng . Các điểm được tô màu theo qui tắc : 2 tuyến không cùng thông đường được tô bằng 2 màu khác nhau ,nghĩa là 2 điểm có chung đoạn thẳng nối chúng thì khác màu nhau . Hãy tô màu các điểm sao cho số màu dùng ít nhất . ( Việc tô màu các điểm , tương đương với việc dựng cột đèn màu tại đầu mối giao thông này với số màu ít nhất , để số tuyến được cùng thông đường càng nhiều càng ít tắc nghẽn giao thông)

Thí dụ :

Trong hình vẽ dưới đây tuyến EC là đường 1 chiều ,còn lại các tuyến khác là đường 2 chiều

Tuyến số : 1 2 3 4 5 6 7 8 9 10 11 12 13

Tên tuyến : AB AC AD BA BC BD DA DB DC EA EB EC ED

Mạng tuyến đường này được mô tả trong File GT.DAT như sau :

13

D

C E

B A

1 4 5 6 7 10

2 4 6 7 8 10 11

3 4 7 8 9 10 11 12

4 1 2 3 8 11

5 1 8 11

6 1 2 7 8 9 11 12

7 1 2 3 6 8 11 12 13

8 2 5 6 12 13

9 3 6 13

10 1 2 3

11 2 3 4 5 6 7

12 3 6 7 8

13 7 8 9

Dòng 1 là số tuyến : 13 tuyến

Các dòng tiếp theo : số ở đầu dòng là tuyến không cùng thông đường với các tuyến số tiếp theo cùng dòng . Thí dụ dòng 6 : 5 1 8 11 có ý nghĩa tuyến 5 không cùng thông đường với các tuyến 1,8,11

Yêu cầu kết quả trênmàn hình :

Dòng đầu : số màu ít nhất

Các dòng tiếp theo : mỗi dòng 1 tuyến gồm 2 con số : số của tuyến , màu của tuyến

Thí dụ với dữ liệu vào như trên , thì dữ liệu ra trên màn hình là :

4

1 1

2 1

3 1

4 2

5 2

6 2

7 3

8 3

9 3

10 2

11 4

12 4

13 2

C11-B-15 Bài toán ghép cặp

Có N thợ và N công việc . Mỗi thợ yêu thích từng công việc với mức độ khác nhau ,mức yêu thích cho bằng điểm từ 1 đến N. Ngược lại mỗi công việc sẽ đạt hiệu quả với các mức độ khác nhau , khi giao cho từng người thợ làm công việc ấy (mức hiệu quả cũng cho bằng điểm từ 1 đến N). Hãy phân công sao cho mỗi thợ 1 việc mà tổng hiệu quả công việc lớn nhất ,đồng thời hạn chế 2 tình trạng éo le :

Tình trạng 1 : Công việc V1 sẽ giao cho thợ T1 , nhưng thợ T2 làm V1 hiệu quả hơn

Tình trạng 2 : Công việc V1 sẽ giao cho thợ T1 , nhưng thợ T1 thích V2 hơn.

C11-B-16

Cho M,N là 2 số tự nhiên (M,N<=15) .Cho một bảng M dòng,N cột ,chứa M*N số nguyên có giá trị từ 0 đến 99 . Cho một số k . Tìm k phần tử trong bảng nói trên để tổng các phần tử được lấy ra là lớn nhất với điều kiện trên mỗi hàng , mỗi cột chỉ được chọn nhiều nhất 1 phần tử .

Dữ liệu vào : File ‘TONGK.INP’

Dòng đầu 3 số M,N,K

M dòng tiếp theo : mỗi dòng là 1 dòng của bảng ( gồm N số )

Dữ liệu ra : File ‘TONGK.OUT’

Dòng đầu 2 số K , T ( T là tổng các số được chọn )

K dòng tiếp theo: Mỗi dòng 3 số : i,j,Aij (i,j : chỉ số dòng, cột của số Aij lấy ra từ bảng )

Thí dụ :

File ‘TONGK.INP’

15 20 12

23 36 8 7 74 43 81 96 69 15 30 70 4 66 58 99 58 77 73 25

58 45 27 46 39 7 62 34 39 42 94 22 67 28 12 34 22 15 4 41

55 61 98 72 37 34 71 48 39 76 83 36 25 95 19 50 69 55 5 71

7 51 3 10 15 80 75 26 27 30 70 63 95 96 25 79 64 94 37 39

41 95 78 8 45 29 6 39 2 1 13 17 59 45 12 72 25 48 43 92

67 40 32 34 95 18 34 20 61 48 76 74 20 78 73 69 44 94 88 13

1 52 72 37 74 73 15 16 91 40 8 47 43 29 49 77 37 78 37 98

35 95 85 91 88 1 41 84 34 49 46 15 40 74 90 61 87 25 72 63

66 88 16 36 18 65 74 60 78 92 34 79 84 50 63 58 24 92 37 81

65 96 87 42 97 94 25 93 65 66 17 17 69 56 1 66 86 84 73 40

97 24 6 55 42 95 42 84 93 4 73 15 76 46 91 69 33 89 83 25

29 4 84 29 70 25 51 82 1 99 44 81 4 38 92 96 26 25 23 60

35 83 45 79 98 42 11 25 60 61 0 51 39 48 81 64 47 97 72 28

12 24 55 34 65 47 49 91 28 36 17 99 2 66 70 36 64 78 98 18

90 79 90 38 7 20 82 41 94 74 22 39 95 24 80 68 85 89 55 74

File ‘TONGK.OUT’

12 1164

12 10 26

14 12 12

1 16 96

7 20 60

3 3 90

10 5 36

11 1 39

13 18 20

8 2 58

4 14 79

15 13 2

2 11 92

ĐỀ BÀI TRÊN CÓ THỂ CHO DƯỚI DẠNG SAU :

(Bài số 3 Đề thi Quốc gia chọn Học sinh giỏi Phổ thông năm học 1994-1995 Bảng A )

Kết quả thi đấu quốc gia của N vận động viên ( đánh số từ 1 đến N ) trên M môn ( đánh số từ 1 đến M ) được đánh giá bằng điểm ( giá trị nguyên không âm ) . Với vận động viên , ta biết điểm đánh giá trên từng môn của vận động viên ấy . Các điểm này được ghi trong File văn bản có cấu trúc :

+ Dòng đầu ghi số vận động viên và số môn .

+ Các dòng tiếp theo . mỗi dòng ghi các điểm đánh giá trên tất cả m môn của một vận động viên theo thứ tự môn thi 1,2,..,m . các dòng này được ghi theo thứ tự vận động viên 1.2,..,N

+ Các số ghi trên một dòng cách nhau một dấu cách .

Cần chọn ra k vận động viên và k môn để lập một đội tuyển thi đấu Olypic quốc tế , trong đó mỗi vận động viên chỉ được thi đấu 1 môn ( 1<=k<=M,N) , sao cho tổng số điểm của các vận động viên trên các môn đã chọn là lớn nhất .

Yêu cầu :

Đọc bảng điểm từ 1 File văn bản ( Tên File vào Từ bàn phím ), sau đó cứ mỗi lần nhận một giá trị k nguyên dương từ bàn phím , chương trình đưa lên màn hình kết quả tuyển chọn dưới dạnh k cặp (i,j) với nghĩa vận động viên i được chọn thi đấu môn j và tổng số điểm tương ứng với cách đã chọn . Chương trình kết thúc khi nhận được giá trị k=0

Các giá trị giới hạn 1<=M,N<= 20

Điểm đánh giá từ 0 đến 100 .

Thí dụ :

File dữ liệu

3 3

1 5 0

5 7 4

3 6 3

Mỗi khi nạp giá trị k ta nhận được :

Nạp k=1 , máy trả lời (2,2) Tổng điểm = 7

Nạp k=2 , máy trả lời (2,1) (3,2) Tổng điểm = 11

Nạp k=3 , máy trả lời (1,2) (2,1) (3,3) Tổng điểm = 13

Nạp k=0 , Kết thúc

C11-B-17 ( Bộ lọc Sắp xếp theo phương tiện song song )

Một “Bộ lọc cỡ 2 “ để sắp xếp lại 2 phần tử là thiết bị với 2 đầu vào x1,x2 và hai đầu ra y1,y2 có dạng như hình vẽ 1 với mọi (x1,x2) qua bộ lọc cỡ 2 nhận được y1=Min(x1,x2) và y2=Max(x1,x2) . Với bộ lọc cỡ 2 bất kỳ đường ra chỉ số cao luôn là y2 . Bộ lọc cỡ N (N<=8) là thiết bị được xây dựng từ các bộ lọc cỡ 2 (coi như các bộ lọc cỡ 2 đã có ) mà N tuyến thẳng từ lối vào tới lối ra , nó gồm N đầu vào là x1,x2,...,xn và N đầu ra là y1,y2,..,yn với y1<=y2<=...<=yn là dãy sắp tăng của dãy x1,x2,...,xn . Bộ lọc cỡ N được đánh giá bởi 2 chỉ tiêu :

+ Số bộ lọc cỡ 2 là S(N) càng ít càng tốt

+ Thời gian qua bộ lọc là T(N) càng ít càng tốt ( lấy thời gian qua 1 bộ lọc cỡ 2 làm đơn vị thời gian ) , vậy cần bố trí có nhiều bộ lọc cỡ 2 đồng thời hoạt động càng tốt ,

Hãy lập trình chứng minh cách 1 thiết kế bộ lọc cỡ N (số cho trước) là đạt yêu cầu nêu trên .

Hình 1 : Bộ lọc cỡ 2 Hình 2 : Bộ lọc cỡ 4 ( S(4)=5, T(4)=3 )

x2 y2

x1 y1

x4 y4

x3 y3

y2

x2

x1 y1

Bảng tham khảo

Chú ý : Một bộ lọc cỡ N được chấp nhận nếu mọi hoán vị của 1,2,..,N qua bộ lọc đều được lọc thành dãy tăng 1,2,..,N. Một bộ lọc cỡ N được chấp nhận và được gọi là tối ưu nếu không thể giảm S(N) và T(N).

C11-B-18 ( Xếp hình ) Cho 3 hình với kích thước như sau :

và một hình chữ nhật H có kích thước 6x9 ô vuông . Ta có thể một cách tuỳ ý các hình thuộc 3 loại trên lấp đầy hình H . Ví dụ sau đây là một cách xếp :

1- Nhập mảng A từ File văn bản có tên TT.TXT trong đó mỗi dòng của File ghi một dòng của mảng A dưới dạng 1 xâu kí tự độ dài là 9 gồm các kí tự thuộc tập {U,I,T,C } {Không cần kiểm tra lại dữ liệu }

2- Khôi phục lại ít nhất 1 cách sắp xếp 3 loại hình nói trên lấp đầy hình H phù hợp với mảng A . Thông báo ra File văn bản có tên XEP.TXT theo qui cách viết mảng A

3- Nếu có thể , hãy tìm thêm càng nhiều càng tốt cách xếp 3 loại hình nói trên lấp đầy hình H phù hợp với mảng A .và ghi tiếp vào File XEP.TXT . Hai cách xếp liên tiếp cách nhau bởi 1 dòng trống .

Giả sử có một cách sắp xếp các hình thuộc 3 loại trên lấp đầy hình H nhưng thông tin về cách sắp xếp đó không đầy đủ và được cho bởi mảng A[1..6,1..9] of char , trong đó A[i,j] nhận 1 trong 4 giá trị U,I,T,C tương ứng tuỳ theo ô đó thuộc hình chữ U , hình chữ T , hình chữ I hay bị mất thông tin .

Ví dụ

C11-B19 ( Bài 3 - Đề thi chọn đội tuyển tin học quốc gia 1994 )

Cho bàn cờ tổng quát NxN ô vuông , N<=10 .Các ô màu trắng và màu đen được phân bố một cách tuỳ ý , nhưng phải thoả mãn hai điều kiện sau đây :

i) Mỗi cột có ít nhất một ô màu trắng .

ii) Có ít nhất một cột chỉ gồm các ô màu trắng

Cần xếp các con xe vào bàn cờ , sao cho :

1) Các con xe chỉ ở các ô màu trắng

2) Trên mỗi dòng và trên mỗi cột có không quá 1 con xe

3) Mỗi ô trắng không có xe nếu bị khống chế bởi một con xe khác trên cùng một cột

Yêu cầu : a ) Đọc từ File kiểu TEXT ( tên File được cho từ bàn phím ) , giá trị N và hình trạng của bàn cờ NxN gồm N xâu các kí tự 1 và 0 trong đó 1 biểu diễn ômàu trắng và 0 biểu diễn ô màu đen , mỗi xâu ứng với một hàng trên bàn cờ

b) Xếp lên bàn cờ càng nhiều con xe càng tốt , sao cho các điều kiện (1),(2),(3) nói trên thoả mãn .

c) Ghi ra File CHESS.SOL số lượng M các con xe đã xếp được và hình trạng của bàn cờ sau khi xếp xe ( ô có xe xếp được đanhs dấu bằng kí tự X )

Giả thiết dữ liệu vào là chuẩn xác nên không cần kiểm tra .

C11-B20 ( Bài 2 - NETWORK OF SCHOOLS -Bài thi Quốc tế 1996 tại Hung Ga ri )

Một số trường học được nối với nhau bằng một mạng máy tính . Có một sự thoả thuận giữa các trường học này : mỗi trường có một danh sách các trường học ( gọi là danh sách các trường “nhận” ) . và mỗi trường khi nhận được một phần mềm từ một trường khác trong mạng hợc từ bên ngoài , cần phải chuyển phần mềm nhận được cho các trường trong danh sách các trường nhận của nó .Cần chú ý rằng nếu B thuộc danh sách các trường nhận của trường học A thì A nhất thiết phải xuất hiện trong danh sách các trường nhận của trường học B .

Người ta muốn gửi một phần mềm đến tất cả các trường học trong mạng . Bạn cần viết chương trình tính số ít nhất các trường học cần gửi bản sao của phần mềm này để cho phần mềm đó có thể chuyển đến tất cả các trường học trong mạng theo thoả thuận trên ( Câu a ) . Ta muốn chắc chắn rằng khi bản sao phần mềm được gửi đến một trường học bất kỳ , phần mềm này sẽ được chuyển tới tất cả các trường học trong mạng . Để đạt mục đích này , ta có thể mở rộng các danh sách các trường nhận , bằng cách thêm vào các trường mới . Tính số ít nhất các mở rộng cần thực hiện sao cho khi ta gửi một phần mềm mới đến một trường bất kỳ trong mạng , phần mềm này sẽ được chuyển đến tất cả các trường khác ( Câu b ) . Ta hiểu một mở rộng là việc thêm một trường mới vào trong danh sách các trường nhận của một trường học nào đó .

Dữ liệu vào : Dòng đầu tiên của File INPUT.TXT chứa số nguyên N : số trường học trong mạng ( 2<=N<=100 ) . Các trường được đánh số bởi N số nguyên dương đầu tiên . Mỗi một trong N dòng tiếp theo mô tả một danh sách các trường nhận . Dòng thứ i+1 chứa số hiệu các trường nhận của trường i .

Mỗi danh sách kết thúc bởi số 0 . Dòng tương ứng với danh sách rỗng chỉ chứa 1 số 0

Dữ liệu ra :Chương trình của bạn cần ghi hai dòng ra File OUTPUT.TXT . Dòng thứ nhất ghi một số nguyên dương là lời giải của câu a ) . Dòng thứ hai ghi lời giải của câu b .

OUTPUT.TXT

1

2

Ví dụ :

INPUT.TXT

5

2 4 3 0

4 5 0

0

0

1 0

PHẦN LỜI GIẢI

DÙNG ĐỆ QUI THỂ HIỆN THUẬT TOÁN VÉT CẠN ( 20 BÀI )

C11-B01

Uses crt;

Var i,dem : Integer;

A : Array[1..8] of Boolean;

B : Array[2..16] of Boolean;

C : Array[-7..7] of Boolean;

x : Array[1..8] of integer;

Procedure Print; { Hiện mọi nghiệm }

Var k:integer;

Begin

b[5] b[9]

1 2 3 4 5 6 7 8

1

2

3

4

5

6 c[-2]

7

8

c[7] c[3]

a[4] a[8]

For k:=1 to 8 do Write(x[k]:4);

Writeln;

Inc(dem);

If dem mod 24 =0 then Readln;

End;

Procedure Try(i:integer);

{Đặt hậu vào dòng i }

Var j:integer;

Begin

For j:=1 to 8 do {Chọn cột }

If a[j] and b[i+j] and c[i-j] then

Begin

x[i]:=j;

a[j]:=False;

b[i+j]:=False;

c[i-j]:=False;

If i<8 then Try(i+1) Else Print;

a[j]:=True;

b[i+j]:=true;

c[i-j]:=true;

End;

End;

BEGIN

dem:=0;

For i:=1 to 8 do a[i]:=True;

For i:=2 to 16 do b[i]:=True;

For i:=-7 to 7 do c[i]:=True;

Try(1);

Write(' Tong so nghiem la : ', dem );

Readln;

END.

C11-B-02

Uses Crt;

Const N = 5;

SqrN = N*N;

C : Array[1..8] of Integer = (-3,3,0,0,2,-2,2,-2);

D : Array[1..8] of Integer = (0,0,3,-3,2,-2,-2,2);

Type K = Array[1..N,1..N] of Byte;

Var A : K;

Sn : Integer;

x,y : Byte;

Procedure Khoitri;

Begin

Writeln('Nhap toa do o xuat phat : ');

Write('Dong y = '); Readln(y);

Write('Cot x = '); Readln(x);

FillChar(A,Sizeof(A),0);

Sn := 0;

A[x,y] := 1;

End;

Procedure Hien;

Var i,j : Byte;

Begin

Inc(sn);

Writeln('Nghiem thu ',sn,' : ');

For i:=1 to N do

Begin

For j:=1 to N do Write(A[i,j]:3);

Writeln;

End;

End;

Procedure Vet(y,x : Byte);

Var k : Byte;

Function Chapnhan(x,y,k : Byte) : Boolean;

Begin

If (x+C[k]>0) and (x+C[k]<N+1) and

(y+D[k]>0) and (y+D[k]<N+1) and (A[y+D[k],x+C[k]]=0) then

Chapnhan := True Else Chapnhan := False;

End;

Begin

For k:=1 to 8 do

Begin

If chapnhan(x,y,k) then

Begin

A[y+D[k],x+C[k]] := A[y,x] +1;

If A[y+D[k],x+C[k]]< sqrN then

Vet(y+D[k],x+C[k]) Else Hien;

A[y+D[k],x+C[k]] := 0;

End;

End;

End;

BEGIN

Clrscr;

Khoitri;

Vet(x,y);

If sn=0 then Writeln('Khong co nghiem ')

Else Writeln('So nghiem : ',sn);

Readln;

END.

C11-B-03

Uses Crt;

Const N = 5;

M = N*N;

Var A : Array[1..M] of Char;

H,C : Array[1..M] of 1..N;

TH,TC : Array[1..N] of set of char;

i : Byte;

dem : LongInt;

Procedure Khoitri;

Var i : Byte;

Begin

For i:=1 to M do

Begin

H[i] := (i-1) div N +1;

C[i] := i mod N;

If C[i]=0 then C[i]:=N;

End;

For i:=1 to N do

Begin

TH[i] := [];

TC[i] := [];

End;

dem := 0;

End;

Procedure Hien;

Var i : Byte;

Begin

Inc(dem);

{For i:=1 to M do

Begin

Write(A[i]:2);

If i mod N =0 then Writeln;

End;

Writeln; }

End;

Procedure Tim(i : Byte);

Var j : Byte;ch : Char;

Begin

For ch:='A' to Char(64+N) do

Begin

If (Not (ch in TH[H[i]]))and(Not (ch in TC[C[i]])) then

Begin

A[i] := ch;

TH[H[i]] := TH[H[i]]+[ch];

TC[C[i]] := TC[C[i]]+[ch];

If i=M then Hien Else Tim(i+1);

TH[H[i]] := TH[H[i]]-[ch];

TC[C[i]] := TC[C[i]]-[ch];

End;

End;

End;

BEGIN

Clrscr;

Khoitri;

Tim(1);

Writeln('So nghiem la : ',dem) ;

Readln;

END.

N=4 So nghiem : 576 N=5 So nghiem : 161.280

C11-B-04

Uses Crt;

Const Max = 20;

TF = 'mecung.inp';

Var A : Array[1..Max*Max] of Byte;

T : Array[1..Max*Max] of Byte;

D : Array[1..Max] of Boolean;

KQ : Array[1..Max] of Byte;

cs : Integer;

F : Text;

N,XP,Dich : Byte;

Procedure DocF;

Var i : Byte;

Begin

Assign(F,TF);

Reset(F);

Readln(F,N,Xp,Dich);

k := 0;

T[k] := 0;

While Not SeekEoF(F) do

Begin

Read(F,i);

While Not SeekEoln(F) do

Begin

Inc(k) ;

Read(F,A[k]);

End;

Readln(F);

T[i] := k;

End;

Close(F);

End;

Procedure Hienkq; {Hiện 1 nghiệm }

Var i : Integer;

Begin

For i:=1 to cs do Write(kq[i]:4);

Readln;

Halt;

End;

Procedure Tim(i : Byte);

Var j : Integer;

Begin

For j:=T[i-1]+1 to T[i] do

Begin

If Not D[A[j]] then

Begin

Inc(cs);

Kq[cs] := A[j];

D[A[j]] := True;

If A[j] <> Dich then Tim(A[j])

Else Hienkq;

Dec(cs);

D[A[j]] := False;

End;

End;

End;

BEGIN

Clrscr;

FillChar(D,Sizeof(D),False);

FillChar(Kq,Sizeof(KQ),0);

DocF;

Cs :=1;

Kq[cs] := Xp;

D[Xp] := True;

Tim(Xp);

Hienkq;

Readln

END.

C11-B-05

Uses Crt;

Const Tf = 'Thi10b2.txt';

Type Mang = Array[1..254] of Byte;

Tro = ^Mang;

Var i,N : Integer;

S,SS : Real;

d : LongInt;

A : Tro;

F : Text;

T : LongInt Absolute $0000:$046C;

Lt : LongInt;

Procedure Nhap;

Begin

Write('Go N=1 la thoat . Nhap N = ');

Repeat

Gotoxy(28,1); Clreol;

{$I-} Readln(N); {$I+}

Until (IoResult=0) and (N>0) and (N<255);

If N=1 then Halt;

Write('Nhap so ket qua da cho S = ');

Repeat

Gotoxy(28,2);{$I-} Readln(S); {$I+}

Until (IoResult=0) and (S>-1.E+9) and (S<1.E+9);

End;

Procedure Hien;

Var i,j : Integer;

Begin

Inc(d);

For i:=1 to N-2 do Write(F,'(');

Write(F,1);

For i:=1 to N-1 do

Case A^[i] of

1: Write(F,'+',i+1,')');

2: Write(F,'-',i+1,')');

3: Write(F,'*',i+1,')');

4: Write(F,'/',i+1,')');

End ;

Case A^[N] of

1: Write(F,'+',i+1);

2: Write(F,'-',i+1);

3: Write(F,'*',i+1);

4: Write(F,'/',i+1);

End ;

Writeln(F);

End;

Procedure Dondep;

Begin

Gotoxy(1,1);

Writeln(F,d,' nghiem : ');

Gotoxy(1,25);

Close(F);

Writeln('Da xong trong thoi gian : ',((T-Lt)/18.2):10:0);

End;

Procedure Dithuan(i : Integer;Var SS : Real);

Var j : Integer;

Begin

If ((T-Lt)/18.2 >30 )then

Begin Dondep; Halt; End;

If (Abs(SS-S)<1.0E-4) and (i=N) then Hien ;

If (i=N) and (SS<>S) then Exit;

If (SS>1.7E+37) or (SS<-1.7E+37) then

Begin Writeln('So qua Max '); Readln; Halt; End;

If (i<=N-1) and (A^[i]=0) then

For j:=1 to 4 do

Case j of

1: Begin

SS := SS+i+1; A^[i]:= 1;

Dithuan(i+1,SS);

SS := SS-(i+1); A^[i]:= 0;

End;

2: Begin

SS := SS-(i+1); A^[i]:= 2;

Dithuan(i+1,SS);

SS := SS+(i+1); A^[i]:= 0;

End;

3: Begin

SS := SS * (i+1); A^[i]:= 3;

Dithuan(i+1,SS);

SS := SS/(i+1); A^[i]:= 0;

End;

4: Begin

SS := SS/(i+1); A^[i]:= 4;

Dithuan(i+1,SS);

SS := SS *(i+1); A^[i]:= 0;

End;

End;

End;

BEGIN

Repeat

Clrscr;

New(A);

Nhap;

Lt := T;

d := 0;

Clrscr;

Gotoxy(1,2);

FillChar(A^,Sizeof(A^),0);

If N>1 then

Begin

Assign(F,Tf);

ReWrite(F);

SS := 1;

Dithuan(1,SS);

End;

Dondep;

Readln;

Until False ;

END.

C11-B-06

{Phuong phap De qui }

Uses Crt;

Const TF = ‘Phanso.out’;

Type Kkq = Array[1..1000] of LongInt;

Var F : Text;

Kq : Kkq;

i,T,M,dem : LongInt;

Procedure Nhap;

Begin

Repeat

Write('Nhap tu so T ,mau so M (0<T<M<=969696) ');

{$I-} Readln(T,M); {$I+}

Until (IoResult=0) and (T>0) and(M>T) and(M<=969696);

End;

Function UCLN(a,b : LongInt) : LongInt; {a,b > 0}

Var d : LongInt;

Begin

d := a mod b;

Repeat

a := b;

b := d;

d := a mod b;

Until d=0;

UCLN := b;

End;

Procedure Hienkq;

Var i : LongInt;

Begin

Assign(F,TF);

Append (F);

For i:=1 to dem do Write(F,KQ[i],’ ‘);

Writeln(F);

Writeln(F,‘Tong gom ‘,dem,' so hang ');

Close(F);

End;

Procedure Toigian(Var T,M : LongInt);

Var u : LongInt;

Begin

u := UCLN(T,M);

If u=1 then Exit;

T := T div u;

M := M div u;

End;

Procedure Thu(i,T,M : LongInt);

Begin

If T=1 then

Begin

Inc(dem);

Kq[dem] := M;

Hienkq;

Halt;

End

Else {T>1}

If (T/M<1/i) then

Begin

Inc(dem);

Kq[dem] := M;

Dec(T);

Toigian(T,M);

Thu(i+1,T,M);

End

Else {T/M>=1/i}

Begin

Inc(dem);

kq[dem] := i;

T := T*i-M;

M := M *i;

Toigian(T,M);

Thu(i+1,T,M);

End;

End;

Procedure Cau1;

Begin

Assign(F,TF);

ReWrite(F);

Toigian(T,M);

Write(F,T,’ ‘,M);

Close(F);

End;

Procedure Cau2;

Begin

Dem := 0;

Toigian(T,M);

Thu(2,T,M);

End;

BEGIN

Clrscr;

Nhap;

{Cau1;}

Cau2;

Writeln(‘Da xong ‘);

Readln

END.

Lời bình :Chương trình trên dùng đệ qui kết hợp “háu ăn” nên kết quả phân tích phân số chưa ngắn nhất . Nội dung của thuật toán như sau :

Mỗi lần cho số nguyên dương i tăng dần , phân số T/ M sau khi tối giản có 2 dạng :

+ a) Lớn hơn 1/ i

+ b) Không lớn hơn 1/ i

Nếu dạng a) thì phân tích T/M = 1/ i + ( T/M - 1/ i )

Nếu dạng b) thì phân tích T/M = 1/M + ( T-1 ) / M

Chương trình sau kết hợp 2 chương trình đệ qui và không đệ qui để chọn nhiệm tốt hơn ( song vẫn chưa hẳn là tối ưu ) vì trong bài toán này các khả năng phân tích một phân số quá nhiều , nên cũng đành chấp nhận sự chưa tối ưu hoàn toàn này vậy thôi ! . Hy vọng chờ đợi bài giải thành công của các em trong thời gian tới .

Uses Crt;

Const TF = 'Phanso.out';

Type Kkq = Array[1..10000] of LongInt;

Var LT,LM,T,M,d1,d2 : LongInt;

kq : Kkq;

F : Text;

Procedure Nhap;

Begin

Repeat

Write('Nhap tu so T ,mau so M (0<T<M<=969696) ');

{$I-} Readln(T,M); {$I+}

Until (IoResult=0) and (T>0) and(M>T) and(M<=969696);

LT := T;

LM := M;

End;

Function UCLN(a,b : LongInt) : LongInt; {a,b > 0}

Var d : LongInt;

Begin

d := a mod b;

Repeat

a := b;

b := d;

d := a mod b;

Until d=0;

UCLN := b;

End;

Procedure Hienkq;

Var i : LongInt;

Begin

Writeln(F,'Cach 2 ');

For i:=1 to d2 do

Begin

Write(F,Kq[i],' ');

If i mod 12 =0 then Writeln(F);

End;

Writeln(F);

Writeln(F,d2);

End;

Procedure Toigian(Var T,M : LongInt);

Var u : LongInt;

Begin

U := UCLN(T,M);

If U=1 then Exit;

T := T div u;

M := M div u;

End;

Procedure Thu(i,T,M : LongInt);

Begin

If T=1 then

Begin

Inc(d2);

Kq[d2] := M;

Hienkq;

If d1<d2 then Writeln(F,'Ket qua : Chon cach 1 ')

Else Writeln(F,'Ket qua : Chon cach 2 ');

Close(F);

Halt;

End

Else {T>1}

If (T/M<1/i) then

Begin

Dec(T);

Inc(d2);

Kq[d2] := M;

Toigian(T,M);

Thu(i+1,T,M);

End

Else {T/M>=1/i}

Begin

Inc(d2);

kq[d2] := i;

T := T*i-M;

M := M *i;

Toigian(T,M);

Thu(i+1,T,M);

End;

End;

Procedure Cau2_Cach1;

Var i : LongInt;

Begin

D1 := 0;

Toigian(T,M);

Writeln(F,'Cach 1 : ');

i := M div T;

While T>0 do

Begin

If (M mod i = 0 ) and (T*i>=M) then

Begin

T := T - M div i;

Write(F,i,' ');

Inc(d1);

If d1 mod 12 =0 then Writeln(F);

If T=0 then

Begin

Writeln(F);

Writeln(F,d1);

Exit;

End;

End

Else Inc(i);

End;

End;

Procedure Cau2_Cach2;

Begin

d2 := 0;

Toigian(T,M);

Thu(2,T,M);

End;

BEGIN

Clrscr;

Nhap;

d2 := 0;

Assign(F,TF);

ReWrite(F);

Cau2_Cach1;

T := Lt;

M := Lm;

Append(F);

Cau2_Cach2;

Readln

END.

Chương trình trên còn một hạn chế là trong File kết quả ghi cả 2 cách chọn , nếu chỉ nêu 1 cách chọn tối ưu hơn thì ban đầu ghi tạm cả 2 kết quả vào 1 File Nháp “PHANSO.BAK” . Sau đó tổ chức đọc File này và tìm kiếm chuyển kết quả tốt sang File chính thức “PHANSO.OUT” .

C11-B-07 ( Bài toán cân trên 2 đĩa )

Uses Crt;

Const TF = 'Can2dia.inp';

TF2 = 'Can2dia.out';

MN = 20;

Var i,y,vc : Integer;

KQ,QC : Array[1..MN] of Integer;

N,dem : Integer;

Ok : Boolean;

F : Text;

T : LongInt Absolute $0000:$046C;

LT,Maxvc : LongInt;

X : Array[0..MN] of Integer;

D : Array[1..1000] of Boolean;

Procedure Khoitri;

Begin

Clrscr;

FillChar(KQ,Sizeof(KQ),0);

Maxvc := 0;

X[0] := 0;

Dem := 0;

End;

Procedure DocF;

Var i : Integer;

F : Text;

Begin

Assign(F,TF);

Reset(F);

Readln(F,N,VC);

For i:=1 to N do

Begin

Read(F,QC[i]);

Maxvc := Maxvc+QC[i];

End;

Close(F);

End;

Procedure Cau1;

Var stt : LongInt;

Procedure Inkq;

Var i : Integer;

y : Longint;

Begin

y := 0;

For i:=1 to N do y := y+x[i]*qc[i];

If (y>0) and (Not D[y]) then D[y] := True;

End;

Procedure Thu(i : Integer);

Var j : Integer;

Begin

For j:= -1 to 1 do

Begin

x[i] := j;

If i = N then Inkq Else Thu(i+1);

End;

End;

Begin

Lt := T;

Assign(F,TF2);

ReWrite(F);

Writeln(F,'Can duoc cac vat sau : ');

Thu(1);

For i:=1 to Maxvc do

If D[i] then

Begin

Write(F,i:4,' ');Inc(stt);

If stt mod 10 = 0 then Writeln(F);

End;

Writeln(F);

Writeln('Da xong cau 1 .Mat thoi gian : ',((T-Lt)/18.2):10:0);

End;

Procedure Cau2;

Procedure HienKQ;

Begin

Inc(dem);

Write(F,'Cach',dem:5,' ** Dia trai : ');

For i:=1 to N do If KQ[i]=1 then Write(F,QC[i]:3);

Write(F,' ':9,' Dia Phai : ');

For i:=1 to N do If KQ[i]=-1 then Write(F,QC[i]:3);

Writeln(F);

End;

Procedure Chon(i : Integer);

Var k,Ly : Integer;

Begin

For k:=-1 to 1 do

Begin

Ly := y;

y := y+k*QC[i];

KQ[i] := k;

If y=vc then Hienkq

Else If (i<N) then Chon(i+1);

KQ[i] := 0;

y := Ly;

End;

End;

Begin

Lt := T;

Dem := 0;

If (vc>Maxvc) or (Not D[vc]) then

Begin

Writeln(F,'Khong the can duoc vat nang ',vc);

Close(F);

Exit;

End;

Writeln(F,'Cac cach can vat nang ',vc,' : ');

Chon(1);

Close(F);

Writeln('Da xong cau 2 .Mat thoi gian : ',((T-Lt)/18.2):10:0);

End;

BEGIN

Khoitri;

DocF;

Cau1;

Cau2;

Readln;

END.

C11-B-08 ( Bài toán đổi tiền )

Uses Crt;

Const Max = 5000;

TF = 'DOITIEN.INP';

Type Toanhang = Array[0..Max] of Integer;

Kho = Array[1..Max] of Integer;

Var A : Toanhang;

Loai,slg : Kho;

Co : Array[1..Max] of Boolean;

Tien,Dem,Soloai,k : Integer;

Procedure Khoitri;

Begin

FillChar(A,Sizeof(A),0);

FillChar(Co,Sizeof(Co),False);

A[0] := 1;

End;

Procedure DocF;

Var F : Text;

i : Integer;

Begin

Assign(F,TF);

Reset(F);

Readln(F,Tien,soloai); Writeln(Tien,' ',Soloai);

For i:=1 to soloai do

Begin

Readln(F,Loai[i],Slg[i]);

Writeln(Loai[i]:4,' ',Slg[i]:4);

Co[Loai[i]] := True;

End;

Close(F);

End;

Function Vitri(T : Integer):Integer;{Dong tien T la dong tien loai thu may}

Var i : Integer;

Begin

i := 1;

While (i<=Soloai) and (T<>Loai[i]) do Inc(i);

Vitri := i;

End;

Function SoLuong(T,k : Integer): Integer;

Var phu ,i : Integer;

Begin {Dong tien T co mat bao nhieu lan trong k so hang }

Phu := 0;

For i:=1 to k do

If A[i] = T then Inc(phu);

Soluong := Phu;

End;

Procedure Phantich(T,k : Integer);

Var j,T1 : Integer;

Ok : Boolean;

Procedure Hien;

Var j ,phu : Integer;

TH : Set of Byte;

Begin

If k>=1 then

Begin

TH := [];

Inc(Dem);

Write('Cach ',dem,' : ');

phu := 0;

For j:=1 to k do

If Not(A[j] in TH) then

Begin

Inc(phu);

If phu=1 then Write(A[j],'*',SoLuong(A[j],k))

Else Write('+',A[j],'*',SoLuong(A[j],k));

TH := TH + [A[j]];

End;

Writeln;

End;

End;

Begin

If T=0 then Hien

Else

Begin

T1 := A[k];

For j:= T1 to T do

If Co[j] then

If (Soluong(j,k)<Slg[Vitri(j)]) then

Begin

Inc(k);

A[k] := j;

T := T-j;

Phantich(T,k);

Dec(k);

T := T+j;

End;

End;

End;

BEGIN

Clrscr;

Khoitri;

DocF;

k :=0;

Phantich(Tien,k);

If Dem=0 then Writeln('Khong co cach phan tich ');

Writeln('Da xong ');

Readln;

END.

C11-B-08 ( Cách 2 : Đơn giản và hiệu suất hơn . Lời giải TDH 2/1999)

uses crt;

const max = 5000;

fi = 'doitien.inp';

fo = 'doitien.out';

type k1 = array[1..max] of integer;

var g,s,kq : k1;

n,m : integer;

sn : longint;

f : text;

procedure docf;

var f : text;

i : integer;

begin

for i:=1 to max do kq[i] := 0;

assign(f,fi);

reset(f);

readln(f,n,m);

writeln(n,' ',m);

for i:=1 to m do

begin

readln(f,g[i],s[i]);

writeln(g[i],' ',s[i]);

end;

close(f);

end;

procedure hien;

var i,dem : integer;

begin

inc(sn);

write(f,'nghiem ',sn,' : ',n,' = ');

dem := 0;

for i:=1 to m do

if kq[i]>0 then

begin

inc(dem);

if dem=1 then write(f,g[i],'*',kq[i])

else write(f,'+',g[i],'*',kq[i])

end;

writeln(f);

end;

Procedure doi(T,i : integer); {Doi so tien con la T ra cac dong tien tu g[i] tro len}

var j : integer;

begin

for j:=0 to s[i]-kq[i] do

begin

inc(kq[i],j);

T := T-g[i]*j;

if T=0 then hien else

if (T>0) and (i<m) then doi(T,i+1);

dec(kq[i],j);

T := T+g[i]*j;

end;

end;

BEGIN

clrscr;

docf;

assign(f,fo);

rewrite(f);

doi(n,1);

writeln(f,sn);

close(f);

writeln('da xong ');

readln;

END.

C11-B-09 ( Bài toán khôi phục lại tình trạng cũ )

Uses Crt;

Const Max = 100;

Fi = 'Khoiphuc.Inp';

Fo = 'Khoiphuc.Out';

Fn = 'Khoiphuc.Nhp';

D : Array [1..8] Of -1..1 = (-1,-1,-1,0,1,1,1,0);

C : Array [1..8] Of -1..1 = (-1,0,1,1,1,0,-1,-1);

Var

A : Array [0..Max,0..Max] Of Integer;

B : Array [0..Max,0..Max] Of Integer;

M,N : Integer;

F : Text;

Ok : Boolean;

Procedure Taofile;

Var i,j,u,v,k,Dem : Integer;

Begin

Write('Nhap N,M : '); { Tạo File đáp số }

Readln(N,M);

Assign(F,Fn);

Rewrite(F);

Randomize;

For i:=1 to N do

Begin

For j:=1 to M do

Begin

A[i,j]:=Random(2);

Write(F,A[i,j]:2);

End;

Writeln(F);

End;

Close(F);

Assign(F,Fi); { Từ File đáp số , tạo File dữ liệu vào là File KHOIPHUC.INP }

Rewrite(F);

Writeln(F,N,' ',M);

For i:=1 to N do

Begin

For j:=1 to M do

Begin

Dem:=0;

For k:=1 to 8 do

Begin

u:=i+D[k];

v:=j+C[k];

If (u>=1) and (v>=1) and (u<=N)and (v<=M)

and (A[u,v]=1) then Inc(Dem);

End;

Write(F,Dem,' ');

End;

Writeln(F);

End;

Close(F);

FillChar(A,Sizeof(A),0); {Xoá mảng A}

End;

Procedure Docfile; { Lấy dữ liệu từ File KHOIPHUC.INP vào Mảng A }

Var i,j : Integer;

Begin

Assign(F,Fi);

Reset(F);

Readln(F,N,M);

For i:=1 to N do

Begin

For j:=1 to M do

Begin

Read(F,A[i,j]);

Write(A[i,j]:3);

End;

Writeln;

Readln(F);

End;

Close(F);

End;

Function Kt(i,x,y : Integer): Boolean; {Kiểm tra có giảm ô (x,y) i đơn vị được không }

Var k : Integer;

Begin

Kt:=True;

For k:=1 to 8 do

If ( A[x+D[k],y+C[k]] - i < 0 ) and (B[x+D[k],y+C[k]]<>-1) then

Begin

Kt:=False;

Exit;

End;

End;

Function Dem(x,y : Integer):Byte;{Đếm xem xung quanh ô (x,y) đã khôi phục được bao nhiêu}

Var i,t :Integer;

Begin

t:=0;

For i:=1 to 8 do

If ( B[x+D[i],y+C[i]] =1 ) then Inc( t );

Dem:=t;

End;

Function Duoc: Boolean; {Kiểm tra bảng B tạo ra có chấp nhận được không }

Begin

Duoc := A[N,M-1]-Dem(N,M-1))=(A[N-1,M]-Dem(N-1,M)) ;

End;

Procedure Init;

Var i,j : Integer;

Begin

For i:=0 to N+1 do

For j:=0 to M+1 do B[i,j]:=-1;

For i:=0 to N+1 do A[i,0]:=0;

For i:=0 to M+1 do A[0,i]:=0;

End;

Procedure Inkq; { Ghi kết quả vào File KHOIPHUC.OUT }

Var i,j : Integer;

F : Text;

Begin

Ok:=True; { Theo dõi bài toán có nghiệm }

Assign(F,Fo);

Rewrite(F);

For i:=1 to N do

Begin

For j:=1 to M do Write(F,B[i,j]:2);

Writeln(F);

End;

Close(F);

End;

Procedure Vet(x,y : Integer);

Var k,phu : Integer;

Begin

If (x=1) or (y=1) then

Begin

For k:=0 to 1 do

If Kt(k,x,y) then

Begin

B[x,y]:=k;

If y<M then Vet(x,y+1)

Else

If x<N then Vet(x+1,1)

Else

If Duoc then Inkq;

B[x,y]:=-1;

End;

End

Else

Begin

B[x,y]:=A[x-1,y-1]-Dem(x-1,y-1);

If (B[x,y]=0) or (B[x,y]=1) then

If y<M then Vet(x,y+1)

Else

If x<N then Vet(x+1,1)

Else

If Duoc then Inkq;

B[x,y]:=-1;

End;

End;

BEGIN

Clrscr;

Ok:=False;

{Taofile;}

Docfile;

Init;

Vet(1,1);

If Not ok then Write('Vo nghiem ');

Readln;

END.

C11-B-10 ( Bài toán du lịch 2 )

Uses Crt;

Const MN = 101;

TF1 = 'DULICH2.INP';

TF2 = 'DULICH2.OUT';

Var F : Text;

C,H : Array[1..MN,1..MN] of Integer;

N : Byte;

KQ,LKQ : Array[1..MN] of Byte;

D : Array[1..MN] of Boolean;

Lcs,cs,xp : Byte;

Conghiem : Boolean;

Tong,LTong,nhonhat,KC,LKC : LongInt;

Procedure Batdau;

Begin

Conghiem := False;

FillChar(C,Sizeof(C),0);

FillChar(D,Sizeof(D),False);

FillChar(KQ,Sizeof(KQ),0);

FillChar(LKQ,Sizeof(LKQ),0);

End;

Procedure TaoF;

Var F : Text;

i,j,r,k,ph : Byte;

Begin

Write('Nhap so thanh pho : ');Readln(N);

Write('Nhap thanh pho xuat phat : ');Readln(xp);

Assign(F,TF1);

ReWrite(F);

Writeln(F,N,' ',Xp);

Randomize;

For i:=1 to N do

Begin

Write(F,i:4);

For j:=i+1 to N do

Begin

r := Random(2);

If r=1 then

Begin

k := Random(8)+1;

ph := Random(8)+1;

Write(F,j:4,k:2,ph:2);

End;

End;

Writeln(F);

End;

Close(F);

End;

Procedure DocF;

Var i,j : Byte;

F : Text;

Begin

Nhonhat := MaxInt div 2 ;

Assign(F,TF1);

Reset(F);

Readln(F,N,XP);

While Not SeekEof(F) do

Begin

Read(F,i);

While Not Eoln(F) do

Begin

Read(F,j);

Read(F,C[i,j],H[i,j]);

C[j,i] := C[i,j];

H[j,i] := H[i,j];

If nhonhat>C[i,j] then nhonhat:= C[i,j];

End;

End;

Close(F);

For i:=1 to N do

Begin

C[i,N+1] := C[i,xp];

H[i,N+1] := H[i,xp];

C[N+1,i] := C[i,xp];

H[N+1,i] := H[i,xp];

End;

Tong := 0;

LTong := MaxInt div 2;

KC := 0;

cs := 1;

KQ[cs] := xp;

D[xp] := True;

End;

Procedure Hien;

Var i,j : Byte;

Begin

For i:=1 to N+1 do

Begin

For j:=1 to N+1 do

If C[i,j]>0 then Write(C[i,j]:2)

Else Write('*':2);

Writeln;

End;

Writeln;

For i:=1 to N+1 do

Begin

For j:=1 to N+1 do

If C[i,j]>0 then Write(H[i,j]:2)

Else Write('*':2);

Writeln;

End;

End;

Procedure Tim (i: Byte;Tong,KC : LongInt);

Var j : Byte;

Begin

For j:=1 to N do

If (Not D[j]) and (i<>j) then

If (C[i,j]>0) and (Ltong-Tong>=C[i,j]+(N-cs-1)*nhonhat)then

Begin

Inc(cs);

KQ[cs] := j;

D[j] := True;

Tong := Tong + C[i,j];

KC := KC + H[i,j];

If (cs=N) then

Begin

If C[j,xp]>0 then

Begin

Tong := Tong + C[j,xp];

KC := KC + H[j,xp];

If (Tong<Ltong)

or((Tong=Ltong) and (KC<LKC)) then

Begin

If Not conghiem then conghiem := True;

Ltong := Tong;

LKQ := KQ;

LKC:= KC;

End;

End Else

Begin

Tong := Tong - C[j,xp];

KC := KC - H[j,xp];

End;

End

Else Tim(j,Tong,KC) ;

Dec(cs);

D[j] := False;

Tong := Tong - C[i,j];

KC := KC - H[i,j];

End;

End;

Procedure HienKQ;

Var i : Byte;

Begin

For i:=1 to N do Write(LKQ[i]:4);

Writeln(Xp:4);

Writeln('Tong chi phi la : ',LTong);

Writeln('Tong duong di : ',LKC);

End;

BEGIN

Clrscr;

{TaoF;}

Batdau;

DocF;

Tim(xp,Tong,KC);

Hien;{Chi goi khi N<=10}

Writeln;

If conghiem then HienKq Else Writeln('Vo nghiem ');

Readln;

END.

C11-B-11 ( Bài toán con tem )

Uses Crt;

Const Max = 10000;

Type Giatri = Array[0..Max] of Integer;

Tem = Array[1..10] of Byte;

Var M,N : Integer;

Lt,T : Tem;

GT : Giatri;

S,Ls : Integer;

Procedure Nhap;

Begin

Write('Nhap so loai tem la N = ');Readln(N);

Write('So tem dan toi da tren 1 vat pham M = ');Readln(m);

End;

Function MaxGt(x : Integer) :Integer;{Dãy giá cước liên tục, do các tem từ 1 đến x sinh ra}

Var i,h : Integer;

Procedure TimGt(i,j: Integer;Var h : Integer);{Tìm các giá trị sau giá trị h , chúng được sinh ra do có thể dán thêm không quá j tem i }

Var p : Byte; Lh : Integer;

Begin

For p:=0 to j do

Begin

Lh := h;

Inc(h,T[i]*p);

If (h < Max) and (GT[h]=0) then GT[h]:=1;

If (i < x) then Timgt(i+1,j-p,h);

h := Lh;

End;

End;

Begin

Fillchar(GT,Sizeof(GT),0);

h:=0;

Timgt(1,m,h);

i:=h+1;

While GT[i]<>0 Do Inc(i);

MaxGt:=i-1;

End;

Procedure Vet(k : Byte); {Bài toán xét tới tem thứ k }

Var i,L : Integer;

Begin

L := MaxGt(k-1); { Day gia tri do cac tem 1->k-1 tao ra dai 1->L}

For i:=T[k-1]+1 to L+1 do { i : du kien Gia tri cua tem moi }

Begin

T[k]:=i;

If k<N then Vet(k+1)

Else

Begin

S:=MaxGt(k);

If S>Ls then

Begin

Ls := S;

Lt := T;

End;

End;

End;

End;

Procedure Lam;

Var i : Byte;

Begin

Ls:=0;

T[1]:=1;

Vet(2);

Writeln('Day gia cuoc tu 1 --> ',Ls);

Write('Bo tem can phat hanh la : ');

For i:=1 to N do Write(Lt[i]:3);

End;

BEGIN

Clrscr;

Nhap;

Lam;

END.

C11-B-12 ( Bài toán ôtô buýt và các tuyến đường )

Uses Crt;

Const Max = 60;

Input = 'Otobuyt.txt';

Type Mang = Array [0..59] of Byte;

Var A,Batdau,Congsai : Mang;

N,Sotuyen : Byte;

Procedure Nhap;

Var F : Text;

i,j : Word;

Begin

Fillchar(a,sizeof(a),0);

Assign(F,input);

Reset(F);

Readln(F,N);

For i:=1 to N do

Begin Read(f,j);inc(a[j]);End;

Close(F);

Sotuyen:=31;

End;

Function KiemTra(xp,t : Byte) : Boolean;

Begin

KiemTra:=false;

Repeat

If a[xp]=0 then exit;

Inc(xp,t);

Until (xp>59) ;

KiemTra:=true;

End;

Function DauTien: byte;

Var

i : byte;

Begin

For i:=0 to 59 do

If a[i]<>0 then

Begin

Dautien:=i;

Exit;

End;

Dautien:= Max;

End;

Procedure Giam(xp,t : Byte);

Begin

While xp<=59 do

Begin

Dec(a[xp]);

Inc(xp,t);

End;

End;

Procedure Tang(xp,t : Byte);

Begin

While xp<=59 do

Begin

Inc(a[xp]);

Inc(xp,t);

End;

End;

Procedure Hien;

Var i : Byte;

Begin

Writeln('So tuyen xe la : ',sotuyen);

For i:=1 to sotuyen do writeln(Batdau[i],' ',Congsai[i]);

End;

Procedure Vet( i : Byte);

Var j,k : Byte;

Begin

k := Dautien;

If k = Max then

Begin

Hien;

Readln;

Halt; {Được nghiệm đầu tiên là thoát ngay, vì nghiệm này tốt nhất rồi }

End

Else

For j:=1 to 59-k do {Thuật ‘Háu ăn’ : chọn công sai từ nhỏ đến lớn}

Begin {tốt nhất vì phải lần lượt xét các tuyến theo thứ tự thời gian của điểm xp}

If kiemtra(k,j) then

Begin

Giam(k,j);

Batdau[i] := k;

Congsai[i] := j;

Sotuyen := i;

Vet(i+1);

Tang(k,j);

End;

End;

End;

BEGIN

ClrScr;

Nhap;

Vet(1);

END.

Sau đây là một cách viết chuẩn mực , không ‘bay bướm ‘ và ‘liều lĩnh ‘ như cách viết trên . Hãy test 2 lối viết này bằng các bộ Test hữu hiệu,mong các em sẽ có thêm một số kinh nghiệm nào đó khi lập trình ‘ thi đấu ! ‘

Uses Crt;

Const Max = 59;

Fi = 'oto.inp';

Fo = 'oto.out';

Type Mang = Array[0..max] of Byte;

Ta = Array[0..31] of Record Tg,Cs :Byte; End;

Var LT : LongInt;

T : Longint Absolute $0:$046C;

A : Mang;

Kq,Lkq: Ta;

N,St,MinSt,dem,i : Byte;

Procedure Nhap;

Var i,j : Byte;

F : Text;

Begin

Assign(F,Fi);{$i-} Reset(F) {$i+};

If (Ioresult<>0) then

Begin

Write('Error file data ',Fi,' .Enter to quit');

Readln;Halt;

End;

Readln(F,N);

Fillchar(A,Sizeof(A),0);

For i:=1 to N do

Begin

Read(F,j);

Inc(A[j]);

End;

Close(F);

End;

Function Tim : Byte;

Var i : Byte;

Begin

For i:=0 to Max do

If A[i]>0 then

Begin

Tim := i;

Exit;

End;

Tim := Max+1;

End;

Function Kt(tg1,cs1,k1:Byte):Boolean;

Begin

Kt := False;

While tg1<=max do

Begin

If A[tg1]=0 then Exit;

tg1 := tg1+ cs1;

End;

[With kq[k1] do

If (Tg=tg1) and (Cs>cs1) then Exit;]

KT:=True;

End;

Procedure DoiTT(tg,cs,chieu : Integer);

Begin

While tg<=max do

Begin

Dec(A[tg],chieu);

tg := tg+cs;

End;

End;

Procedure Vet(k:Byte);

Const tam = 45;

Var cs1,tg1: Byte;

Procedure Toiuu;

Begin

Inc(dem);

St := k-1;

If St<MinSt then

Begin

MinSt := St;

Lkq := Kq;

End;

End;

Procedure Ghitam;

Var F : Text;

Begin

If dem>0 then

Begin

Assign(F,Fo);

ReWrite(F);

Writeln(' Tong So Tuyen tuong doi it nhat = ',MinSt);

For i:=1 to MinSt do Writeln(F,Lkq[i].Tg,Lkq[i].Cs:3);

Close(F);

Readln;

Halt;

End

Else

Begin

Writeln('Ch/tr khong chay duoc du lieu nay trong ',tam,' giay ');

Readln;

Halt;

End;

End;

Begin

If (T-Lt)/18.2>Tam then Ghitam

Else

Begin

tg1 := Tim;

If tg1 = Max+1 then Toiuu

Else

For cs1:=1 to Max-tg1 do

If KT(tg1,cs1,k) then

With kq[k] do

Begin

DoiTT(tg1,cs1,1);

Tg := tg1;

Cs := cs1;

If k<St then Vet(k+1);

DoiTT(tg1,cs1,-1);

End;

End;

End;

Procedure Ghinghiem;

Var F : Text;

Begin

Assign(F,Fo);

ReWrite(F);

If dem>0 then

Begin

Writeln(F,' Tong So Tuyen it nhat = ',MinSt);

For i:=1 to MinSt do

Writeln(F,Lkq[i].Tg:7,Lkq[i].Cs:3);

End

Else Writeln('Vo nghiem ');

Close(F);

End;

Procedure Khoitri;

Begin

LT := T; { Theo doi thoi gian bat dau chay chuong trinh }

St := 31;MinSt := 31;

Dem := 0;

FillChar(Kq,Sizeof(kq),0);

Lkq := kq;

End;

BEGIN

Clrscr;

Nhap;

Khoitri;

Vet(1);

Ghinghiem;

Writeln('Da xong ');

Readln;

END.

17

0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

File ‘Otobuyt.inp’

17

0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

File ‘Otobuyt.out’

0 13

3 12

5 8

C11-B-13 ( Bài toán tô màu )

Uses Crt;

Const Max = 14;

Fi = 'c:\tp97\soan\dequi\Tomau.txt';

Var A : Array[1..Max,1..Max] of 0..1;

Mau,LMau : Array[1..Max] of Byte;

N,i,Minmau,MaxMau : Integer;

Procedure NhapFile;

Var i,j : Integer;

F : Text;

Begin

FillChar(A,Sizeof(A),0);

Assign(F,Fi);

Reset(F);

Readln(F,N);

While not Eof(F) do

Begin

Read(F,i);Readln(F,j);

A[i,j] := 1;

A[j,i] := 1;

End;

End;

Procedure Hien;

Var i,j : Integer;

Begin

Writeln;

For i:=1 to N do

Begin

For j:=1 to N do Write(A[i,j]:4);

Writeln;

End;

End;

Function Kt(x,m : Integer): Boolean;{ Mau m gan cho dinh x }

Begin

Kt := False;

For i:=1 to N do

If (A[x,i]=1) and (m=Mau[i]) then Exit;

Kt := True;

End;

Procedure Tomau(x : Integer); { To mau cho dinh x }

Var

m,luu : Integer;

Begin

If x=N+1 then

Begin { Được 1 nghiệm , đổi lại cận trên MaxMau }

LMau := Mau;

MaxMau := MinMau;

Exit

End;

m := 1;

While m<Maxmau do

Begin

If KT(x,m) then

Begin

Mau[x] := m;

Luu := Minmau;

If Minmau<m then Minmau := m;

Tomau(x+1);

Minmau := Luu;

Mau[x] := 0;

End;

Inc(m);

End;

End;

Procedure Khoitri;

Begin

FillChar(Mau,sizeof(Mau),0);

Maxmau := N;

Minmau := 0;

Mau[1] := 1;

End;

Procedure Thongbao;

Var i : Integer;

Begin

For i:=1 to N do Writeln( ' Diem ',i:2,' to mau : ',LMau[i]);

End;

BEGIN

Clrscr;

NhapFile;

Hien;

Khoitri;

Tomau(2);

Thongbao;

END.

C11-B-14 ( Bài toán giao thông )

Uses Crt;

Const Max = 100;

Fi = 'Gthong.txt';

Fo = 'Gthong.out';

Type M1 = Array[1..Max,1..Max] of Byte;

M2 = Array[1..Max*Max+1] of Byte;

M3 = Array[0..Max] of Byte;

Var N : Byte;

A : ^M1;

B : M2;

T : M3;

MinM,MaxM : Integer;

M,Lm : M3;

Procedure DocF;

Var F : Text;

i,j,so : Byte;

Begin

Assign(F,Fi);

{$I-} Reset(F); {$I+}

If Ioresult <>0 then

Begin

Writeln('Loi File ');

Readln;

Halt;

End;

Readln(F,N);

New(A);

For i:=1 to N do

For j:=1 to N do A^[i,j] := 0;

While Not SeekEof(F) do

Begin

Read(F,i);

While Not Seekeoln(F) do

Begin

Read(F,j);

A^[i,j] := 1;

End;

Readln(F);

End;

Close(F);

End;

Procedure Chuyen_dl;

Var i,j : Byte;

so : Integer;

Begin

T[0] := 0;

so := 0;

For i:=1 to N do

Begin

For j:=1 to N do

If A^[i,j] = 1 then

Begin

Inc(so);

B[so] := j;

End;

T[i] := so;

End;

End;

Function KT(x,mau : Byte) :Boolean;

Var p : Integer;

Begin

Kt := False;

For p:= T[x-1]+1 to T[x] do

If M[B[p]]=mau then Exit;

Kt := true;

End;

Procedure Inkq;

Var F : Text;

i : Byte;

Begin

Assign(F,Fo);

Rewrite(F);

Writeln(F,'So mau can dung : ',MaxM);

For i:=1 to N do Writeln(F,'Tuyen ',i,' to mau ',Lm[i]);

Close(F);

End;

Procedure GhiToiuu;

Begin

Lm := M;

MaxM := MinM;

End;

Procedure Tomau(i : Byte);

Var j,Luu : Byte;

Begin

If i=N+1 then Ghitoiuu

Else

Begin

j := 1;

While j<MaxM do

Begin

If Kt(i,j) then

Begin

M[i] := j;

Luu := MinM;

If MinM<j then MinM := j;

Tomau(i+1);

MinM := Luu;

M[i] := 0;

End;

Inc(j);

End;

End;

End;

Procedure Khoitri;

Begin

MinM := 0;

MaxM := N;

FillChar(M,Sizeof(M),0);

End;

BEGIN

Clrscr;

DocF;

Chuyen_dl;

Khoitri;

M[1] := 1;

Tomau(2);

Inkq;

END.

C11-B-15 ( Bài toán ghép cặp)

Uses Crt;

Const N = 8;

Fi = 'c:\tp97\soan\dequi\chonviec.inp';

Fo = 'chonviec.out';

Type Mang = Array[1..N] of 1..N;

Qhe = Array[1..N,1..N] of 1..N;

Var Gheptho,GhepCV : Mang;

ChonTho,ChonCV,NgvTho,HqCV : Qhe;

Thodxet : Array[1..N] of Boolean;

F1,F2 : Text;

Yeucau,Congviec,Tho,TongNv,Tonghieuqua : Integer;

Procedure Hien;

Var Congviec : Integer;

Begin

TongNv := 0;

Tonghieuqua := 0;

For Congviec := 1 to N do

Begin

TongNv := TongNv+NgvTho[Gheptho[Congviec],Congviec];

Tonghieuqua := Tonghieuqua+HqCV[Congviec,Gheptho[Congviec]];

End;

Writeln(F2,'Tong nguyen vong cua tho : ',TongNv);

Writeln(F2,'Tong hieu qua Congviec : ',Tonghieuqua);

Writeln(F2,'Phuong an hieu qua toi uu (Congviec,Tho) : ');

For Congviec:=1 to n do

Writeln(F2,'(',Congviec,',',Gheptho[Congviec],')=',HqCV[Congviec,Gheptho[Congviec]]);

End;

Procedure Ghep(Congviec : Byte); { xet tung Congviec }

Var yeucau : Byte;

Tho : Byte;

Function Benvung : Boolean;

Var CVx,Thox,i,Lim : Byte;

Ok : Boolean;

Begin

Ok := True;

Lim := NgvTho[Tho,Congviec];

i := 1;

While (i<Lim) and Ok do

Begin

CVx := ChonCV[Tho,i];

Inc(i);

If CVx<Congviec then

Ok := HqCV[Congviec,Tho]>HqCV[Congviec,Gheptho[CVx]]

End;

i := 1;

While (i<Yeucau) and Ok do

Begin

ThoX := ChonTho[Congviec,i];

Inc(i);

If Thodxet[ThoX] then

OK := NgvTho[ThoX,Congviec]>NgvTho[ThoX,GhepCV[ThoX]];

End;

Benvung := Ok;

End;

Begin

For yeucau := 1 to N do

Begin

Tho := ChonTho[Congviec,yeucau];

If Not Thodxet[Tho] then

If benvung then

Begin

Gheptho[Congviec] := Tho;

GhepCV[Tho] := Congviec;

Thodxet[Tho] := True;

If Congviec<N then Ghep(Congviec+1)

Else Hien;

Thodxet[Tho] := False;

End;

End;

End;

BEGIN

Clrscr;

Assign(F1,Fi);

Reset(F1);

Assign(F2,Fo);

Rewrite(F2);

While Not SeekEof(F1) do

Begin

For Congviec := 1 to n do

Begin

For yeucau := 1 to N do

Begin

Read(F1,ChonTho[Congviec,yeucau]);

HqCV[Congviec,ChonTho[Congviec,yeucau]] := yeucau;

End;

Readln(f1);

End;

For Tho := 1 to N do

Begin

For yeucau:=1 to N do

Begin

Read(F1,ChonCV[Tho,yeucau]);

NgvTho[Tho,ChonCV[Tho,yeucau]] := yeucau;

End;

Readln(f1);

End;

End;

Close(F1);

FillChar(Thodxet,Sizeof(Thodxet),false);

Ghep(1);

Close(F2);

Writeln(#13#10'Da ghi xong vao file ',Fo);

Readln;

END.

C11-B-16

Uses Crt;

Const Max = 100;

Fi = 'Tongk.txt';

Fo = 'Tongk.out';

Type M1 = Array[1..Max*Max+1] of Integer;

M2 = Array[1..Max*Max+1] of Byte;

M3 = Array[1..Max] of Byte;

M4 = Array[1..Max] of Boolean;

Var B,LB : M1;

D,C : M2;

M,N,k : Byte;

DxD,DxC : M4;

Tong,LTong,csMax: LongInt;

KqD,KqC,LkqD,LkqC : M3;

Procedure DocF;

Var i,j : Byte;

F : Text;

Begin

Assign(F,Fi);

{$I-} Reset(F); {$I+}

If IoResult<>0 then

Begin

Writeln('Loi File ');

Readln;

Halt;

End;

Readln(F,M,N,k);

For i:=1 to M do

Begin

For j:=1 to N do

Begin

Read(F,B[(i-1)*N+j]);

D[(i-1)*N+j] := i;

C[(i-1)*N+j] := j;

End;

Readln(F);

Writeln;

End;

Close(F);

LB := B;

CsMax := M*N;

End;

Procedure Sapxep_dl; {Sap giam dan }

Procedure Quick(dau,cuoi : LongInt);

Var i,j,L,phu : LongInt;

Begin

i := dau;

j := cuoi;

L := (i+j) div 2;

Repeat

While B[i]>B[L] do Inc(i);

While B[j]<B[L] do Dec(j);

If i<=j then

Begin

phu := B[i];

B[i] := B[j];

B[j] := phu;

phu := D[i];

D[i] := D[j];

D[j] := phu;

phu := C[i];

C[i] := C[j];

C[j] := phu;

Inc(i);

Dec(j);

End;

Until i>j;

If dau<j then Quick(dau,j);

If i<cuoi then Quick(i,cuoi);

End;

Begin

Quick(1,M*N);

End;

Procedure Khoitri;

Begin

FillChar(B,Sizeof(B),0);

FillChar(C,Sizeof(C),0);

FillChar(DxD,Sizeof(DxD),False);

FillChar(DxC,Sizeof(DxC),False);

FillChar(KqD,Sizeof(KqD),0);

FillChar(KqC,Sizeof(KqC),0);

Tong := 0;

Ltong := 0;

End;

Procedure GhiToiuu;

Begin

LkqD := kqD;

LkqC := kqC;

Ltong:= Tong;

End;

Procedure Chon(i,j : Byte);{xet toi o thu i trong Kq, tu o j trong B }

Var d1,c1 : Byte;

delta,j1,p,cL,Luu : LongInt;

Begin

cL := k-i;

Delta := Tong-LTong;

If cL<0 then

Begin

If Delta>=0 then GhiToiuu;

End

Else

Begin

j1 := j-1;

Repeat

Inc(j1);

d1 := D[j1];

c1 := C[j1];

Until (j1> Csmax) or ((Not DxD[d1])and (Not DxC[c1]));

If j1<= csMax then

If B[j1]+B[j1+1]*cL+Delta>0 then

For p := j1 to csMax-1 do

Begin

d1 := D[p];

c1 := C[p];

If (B[p]+B[p+1]*cL+Delta>0) and

(Not DxD[d1]) and (Not DxC[c1]) then

Begin

DxD[d1] := True;

DxC[c1] := True;

Luu := Tong;

Tong := Tong+B[p];

KqD[i] := d1;

KqC[i] := c1;

Chon(i+1,p+1);

DxD[d1] := False;

DxC[c1] := False;

Tong := Luu;

KqD[i] := 0;

KqC[i] := 0;

End;

End;

End;

End;

Procedure Inkq;

Var i : Byte;

F : Text;

Begin

Assign(F,Fo);

ReWrite(F);

Writeln(F,'k= ',k,' Tong = ',LTong);

For i:=1 to k do

Writeln(F,LkqD[i]:2,' ',LkqC[i]:2,' = ',LB[(LkqD[i]-1)*N+LkqC[i]]);

Close(F);

End;

BEGIN

Clrscr;

Khoitri;

DocF;

Sapxep_dl;

Chon(1,1);

Inkq;

END.

Sau đây là lời giải của Lê Sỹ Quang 12 Chuyên Tin 1995 ( Bài đạt giải nhì toàn quốc 1995 )

(Bài số 3 Đề thi Quốc gia chọn Học sinh giỏi Phổ thông năm học 1994-1995 Bảng A )

Kết quả thi đấu quốc gia của N vận động viên ( đánh số từ 1 đến N ) trên M môn ( đánh số từ 1 đến M ) được đánh giá bằng điểm ( giá trị nguyên không âm ) . Với vận động viên , ta biết điểm đánh giá trên từng môn của vận động viên ấy . Các điểm này được ghi trong File văn bản có cấu trúc :

+ Dòng đầu ghi số vận động viên và số môn .

+ Các dòng tiếp theo . mỗi dòng ghi các điểm đánh giá trên tất cả m môn của một vận động viên theo thứ tự môn thi 1,2,..,m . các dòng này được ghi theo thứ tự vận động viên 1.2,..,N

+ Các số ghi trên một dòng cách nhau một dấu cách .

Cần chọn ra k vận động viên và k môn để lập một đội tuyển thi đấu Olypic quốc tế , trong đó mỗi vận động viên chỉ được thi đấu 1 môn ( 1<=k<=M,N) , sao cho tổng số điểm của các vận động viên trên các môn đã chọn là lớn nhất .

Yêu cầu :

Đọc bảng điểm từ 1 File văn bản ( Tên File vào Từ bàn phím ), sau đó cứ mỗi lần nhận một giá trị k nguyên dương từ bàn phím , chương trình đưa lên màn hình kết quả tuyển chọn dưới dạnh k cặp (i,j) với nghĩa vận động viên i được chọn thi đấu môn j và tổng số điểm tương ứng với cách đã chọn . Chương trình kết thúc khi nhận được giá trị k=0

Các giá trị giới hạn 1<=M,N<= 20

Điểm đánh giá từ 0 đến 100 .

Thí dụ :

File dữ liệu

3 3

1 5 0

5 7 4

3 6 3

Mỗi khi nạp giá trị k ta nhận được :

Nạp k=1 , máy trả lời (2,2) Tổng điểm = 7

Nạp k=2 , máy trả lời (2,1) (3,2) Tổng điểm = 11

Nạp k=3 , máy trả lời (1,2) (2,1) (3,3) Tổng điểm = 13

Nạp k=0 , Kết thúc

{$A+,B-,D+,E+,F-,I+,L+,N-,O-,R-,S+,V-}

{$M 16384,0,655360}

Uses Crt;

Const Max = 20;

Type Ta = Array[1..max,1..max] of Integer;

Tb = Array[1..max] of Byte;

Tl = Array[1..max] of Integer;

Var N,M,k : Byte;

a : Ta;

b,lb : Tb;

G,Lg : Integer;

Ok : Set of Byte;

Procedure Input;

Var Tf : String;

f : Text;

Ok : Boolean;

i,j : Byte;

Begin

Repeat

Write(#10#13,'Cho biet ten file du lieu : ');

Readln(tf);

{$i-} Assign(f,tf); Reset(f); {$i+}

Ok:=Ioresult=0;

If Not Ok then

Begin Writeln('File loi hoac khong co file ten la :',tf); End;

Until Ok or (tf='');

If tf='' then Halt;

Readln(f,n,m);

For i:=1 to n do

Begin

For j:=1 to m do Read(f,a[i,j]);

Readln(f);

End;

Close(f);

End;

Procedure NhapK;

Begin

Repeat

Write(#10#13,'Cho biet so mon can chon K:=');

{$i-} Readln(k); {$i+}

Until (Ioresult=0) and (k>=0) and (k<=m) and (k<=n);

End;

Procedure Hien;

Var i,j : Byte;

Begin

For i:=1 to n do

Begin

For j:=1 to m do Write(a[i,j]:4); Writeln;

End;

End;

Procedure HienNghiem;

Var i : Byte;

Begin

For i:=1 to n do

If (Lb[i]>0) then Write('(',i,',',Lb[i],')');

Writeln(#10#13,'Tong so diem = ',lg);

End;

Procedure VETCAN(i,somon:Byte);

Var j : Byte;

Begin

If (somon>k) then

Begin

If (lg<g) then

Begin

Lb:=b;

Lg:=g;

End;

Exit;

End;

If (i>n) then Exit;

For j:=1 to m do

If Not (j in ok) then

Begin

g:=g+a[i,j];

b[i]:=j;

Ok:=Ok+[j];

Vetcan(i+1,somon+1);

g:=g-a[i,j];

b[i]:=0;

Ok:=Ok-[j];

End;

Vetcan(i+1,somon);

End;

Procedure Vet;

Var i : Byte;

Begin

For i:=1 to m do B[i]:=0;

Lg:=-maxint div 2;

G:=0;

Ok:=[ ];

Vetcan(1,1);

Hiennghiem;

End;

BEGIN

Clrscr;

Repeat

Input;

Hien;

Repeat

NhapK;

If (k>0) Then VET;

Until (k=0);

Write(#10#13,'ESC de thoat hoac phim bat ki de thu ');

Write('lai voi file khac');

Until (readkey=#27);

END.

C11-B-17

( Bài toán xây dựng bộ lọc )

Uses Crt;

Const Max = 10;

Type Mang = Array[1..Max] of Integer;

Var i,n,dem,shv : Integer;

M,M1 : Mang;

Procedure Hien;

Var k : Byte;

Begin

Inc(shv);

For k:=1 to n do Write(M[k]:3);

Writeln;

End;

Procedure Trao(Var a,b : Integer);

Var c : Integer;

Begin

c := a;

a := b;

b := c;

End;

Procedure L2(Var a,b : Integer);

Var c : Integer;

Begin

If a > b then Trao(a,b);

End;

Procedure L3(Var a,b,c : Integer);

Begin

L2(a,b);

L2(b,c);

L2(a,b);

End;

Procedue L4(Var a,b,c,d : Integer);

Var coc : Integer;

Begin

L2(a,b);

L2(c,d);

L2(a,c);

L2(b,d);

L2(b,c);

End;

Procedure L5( var a,b,c,d,e : Integer);

Var coc : Integer;

Begin

L2(d,e);

L2(b,c);

L2(b,d);

L2(c,e);

L2(a,b);

L2(b,e);

L3(b,c,d);

End;

Function OK(X,Y : Mang) : Boolean;

Var i : byte;

Begin

For i:=1 to N do

If X[i]<>Y[i] then Begin OK := False; Exit; End;

Ok := True;

End;

Procedure Taohoanvi(n : Byte );

Procedure Doicho (Var M : Mang; k : Integer);

Var i,j : Byte;

c : Integer;

Begin

If k=1 then

Begin

Writeln;

Hien;

L5(M[1],M[2],M[3],M[4],M[5]);

Hien;

If not Ok(M,M1) then Inc(dem);

End

Else

For i:= k downto 1 do

Begin

c := M[k];

M[k] := M[i];

M[i] := c;

Doicho(M,k-1)

End;

End;

Begin

Doicho(M,n);

End;

BEGIN

Clrscr;

dem := 0;

N:= 5;

For i:=1 to n do M[i] := i;

M1:=M;

Writeln;

Taohoanvi(n);

Writeln('So hoan vi cua ',n,' = ',shv div 2);

Writeln('So mac loi cua bo loc da xay dung la : ',dem );

If dem=0 then Writeln('OK ! ');

Readln;

END.

C11-B-18 ( Xếp hình U,I,T )

Program XapXep;

Uses Crt;

Const Input = 'xep_uit.txt';

Type Mang1 = Array [1..6,1..9] of Char;

Mang2 = Array [1..4,1..4] of Char;

Var A,B : Mang1;

Dem : Integer;

Hinh : Array [1..21] of Mang2;

Cod,Coc : Array [1..21] of Byte;

Procedure Nhap;

Var F : Text;

i,j : Byte;

Begin

Assign(F,Input);

Reset(F);

For i:=1 to 6 do

Begin

For j:=1 to 9 do read(F,B[i,j]);

Readln(F);

End;

Close(F);

FillChar(A,Sizeof(A),' ');

End;

Procedure Quay(k : Byte;Var h2: Mang2);

Var i,j : Byte;

Begin

For i:=1 to Cod[k] do

For j:=1 to Coc[k] do

h2[j,Cod[k]+1-i] := hinh[k,i,j];

Cod[k+1] := Coc[k];

Coc[k+1] := Cod[k];

End;

Procedure Taomau;

Var i : Byte;

Begin

For i:=1 to 21 do

FillChar(hinh[i],Sizeof(hinh[i]),' ');

Hinh[1,1,1]:='U';Hinh[1,1,2]:=' ';Hinh[1,1,3]:='U';

Hinh[1,2,1]:='U';Hinh[1,2,2]:=' ';Hinh[1,2,3]:='U';

Hinh[1,3,1]:='U';Hinh[1,3,2]:='U';Hinh[1,3,3]:='U';

Cod[1] := 3;

Coc[1] := 3;

Quay(1,Hinh[2]);

Quay(2,Hinh[3]);

Quay(3,Hinh[4]);

Hinh[5,1,1]:='T';Hinh[5,1,2]:='T';Hinh[5,1,3]:='T';

Hinh[5,2,1]:=' ';Hinh[5,2,2]:='T';Hinh[5,2,3]:=' ';

Hinh[5,3,1]:=' ';Hinh[5,3,2]:='T';Hinh[5,3,3]:=' ';

Cod[5] := 3;

Coc[5] := 3;

Quay(5,Hinh[6]);

Quay(6,Hinh[7]);

Quay(7,Hinh[8]);

Hinh[8,1,1]:='I';Hinh[8,1,2]:='I';

Hinh[9,1,1]:='I';Hinh[9,2,1]:='I';

Cod[8] :=1; Coc[8]:=2;

Cod[9] :=2; Coc[9]:=1;

Hinh[10,1,1]:='T';Hinh[10,1,2]:='T';Hinh[10,1,3]:='T';

Hinh[10,2,1]:='U';Hinh[10,2,2]:='T';Hinh[10,2,3]:='U';

Hinh[10,3,1]:='U';Hinh[10,3,2]:='T';Hinh[10,3,3]:='U';

Hinh[10,4,1]:='U';Hinh[10,4,2]:='U';Hinh[10,4,3]:='U';

Cod[10] := 4;

Coc[10] := 3;

Quay(10,Hinh[11]);

Quay(11,Hinh[12]);

Quay(12,Hinh[13]);

Hinh[14,1,1]:='T';Hinh[14,1,2]:='T';Hinh[14,1,3]:='T';

Hinh[14,2,1]:='I';Hinh[14,2,2]:='T';Hinh[14,2,3]:='I';

Hinh[14,3,1]:='I';Hinh[14,3,2]:='T';Hinh[14,3,3]:='I';

Cod[14] := 3;

Coc[14] := 3;

Quay(14,Hinh[15]);

Quay(15,Hinh[16]);

Quay(16,Hinh[17]);

Hinh[18,1,1]:='U';Hinh[18,1,2]:='I';Hinh[18,1,3]:='U';

Hinh[18,2,1]:='U';Hinh[18,2,2]:='I';Hinh[18,2,3]:='U';

Hinh[18,3,1]:='U';Hinh[18,3,2]:='U';Hinh[18,3,3]:='U';

Cod[18] := 3;

Coc[18] := 3;

Quay(18,Hinh[19]);

Quay(19,Hinh[20]);

Quay(20,Hinh[21]);

End;

Function Chapnhan(x,y,sh: Byte) : Boolean;

Var d,c : Byte;

Begin

If A[x,y]<>' ' then

Begin

Chapnhan := False;

Exit;

End;

If Not ((x+Cod[sh]<8)

and (y+Coc[sh]<11)) then

Begin

Chapnhan := False;

Exit;

End;

For d:=1 to Cod[sh] do

For c:=1 to Coc[sh] do

If Hinh[sh,d,c]<>' ' then

Begin

If (A[d+x-1,c+y-1]<>' ') or ((B[d+x-1,c+y-1]<>'C') and

(B[d+x-1,c+y-1]<>Hinh[sh,d,c])) then

Begin

Chapnhan := False;

Exit;

End;

End;

Chapnhan := True

End;

Procedure Lap(x,y,sh : Byte);

Var d,c : Byte;

Begin

For d:=1 to Cod[sh] do

For c:=1 to Coc[sh] do

Begin

If (Hinh[sh,d,c]<>' ') then

Begin

A[d+x-1,c+y-1] := Hinh[sh,d,c];

End;

End;

End;

Procedure Thao (x,y,sh : Byte);

Var d,c : Byte;

Begin

For d:=1 to Cod[sh] do

For c:=1 to Coc[sh] do

Begin

If (Hinh[sh,d,c]<>' ') then

Begin

A[d+x-1,c+y-1] := ' ' ;

End;

End;

End;

Procedure HienKq;

Var i,j : Byte;

Begin

Inc(dem);

Writeln(dem);

For i:=1 to 6 do

Begin

For j:=1 to 9 do Write(A[i,j]:2);

Writeln;

End;

Writeln

End;

Function Ketthuc : Boolean;

Var i,j : Byte;

Begin

Ketthuc := False;

For i:=1 to 6 do

For j:=1 to 9 do

If A[i,j]=' ' then Exit;

Ketthuc := True

End;

Procedure Tim(Var x,y : Byte);

Begin

While A[x,y]<>' ' do

Begin

If y<9 then Begin Inc(y);End

Else

If x<6 then

Begin Inc(x);y := 1; End

End

End;

Procedure Vet(x,y : Byte);

Var Lx,Ly ,i,j : Byte;

Begin

Begin

Tim(X,Y);

For i:=1 to 21 do

Begin

If Chapnhan(x,y,i) then

Begin

Lap(x,y,i);

Lx :=1;Ly:=1;

If Ketthuc then HienKq Else Vet(Lx,Ly);

Thao(x,y,i);

End;

End;

End

End;

Begin

ClrScr;

Nhap;

Taomau; dem := 0;

Vet(1,1);

Writeln('Da xong ',dem,' nghiem ');

Readln

End.

TEST

UUUCCCCCC

UUUUCCCCC

UUUUCCCCC

CUUUCCCCC

CCCCCCCCC

CCCCCCCCC

U U U I I I I I I

U U U U I I I I I

U U U U I U U U I

I U U U I U U U U

I I I I I U U U U

I I I I I I U U U

C11-B-19 ( Bài 3 - Đề thi toàn quốc 1994 )

{Bai 3 - De thi toan quoc 1994 }

Uses Crt;

Const Max = 16;

Fi = 'tq94_b3.txt';

Type M1 = Array[1..max,1..max] of Byte;

M2 = Array[1..max] of Boolean;

M3 = Array[1..max*max] of Record

x,y : Byte;

End;

Var A,B : M1;

Dxh,Dxc : M2;

N,d,Tong,LT : Byte;

Tr,KQ,LKQ : M3;

Procedure Input;

Var f : Text;S : String;

i,j : Byte;

Begin

Assign(f,fi); {$i-} Reset(f); {$i+}

If (ioresult<>0) then

Begin

Write('Error file data : ',fi,' . Enter de thoat ');

Readln; Halt;

End;

Readln(f,n);

For i:=1 to n do

Begin

Readln(f,S);

For j:=1 to N do A[i,j] := Ord(S[j])-48;

End;

Close(f);

End;

Procedure Hien( A : M1);

Var i,j : Byte;

Begin

For i:=1 to n do

Begin

For j:=1 to n do

Begin

If A[i,j]=2 then Textcolor(10);

Write(A[i,j]:2); Textcolor(15);

End;

Writeln;

End;

End;

Function Kiemtra:Boolean;

Var i : Byte;

Begin

Kiemtra:=False;

If (Tong<=LT) then Exit;

For i:=1 to d do

If (B[Tr[i].x,Tr[i].y] = 1) and

(Not Dxh[Tr[i].x] and Dxc[Tr[i].y]) then Exit;

Kiemtra:=True;

End;

Procedure Vet(i,j:Byte);

Begin

If (i = N+1) then

Begin

If Kiemtra then

Begin

LT := Tong;

LKQ := KQ;

End;

Exit;

End;

If (A[i,j]=1) then

Begin

If Dxh[i] and Dxc[j] then

Begin

Dxh[i]:=False;

Dxc[j]:=False;

Inc(Tong);

KQ[Tong].x:=i;

KQ[Tong].y:=j;

B[i,j] := 1;

If (j=N) Then Vet(i+1,1)

Else Vet(i,j+1);

Dxh[i]:=True;

Dxc[j]:=True;

B[i,j]:=0;

Dec(Tong);

End;

{If (j=N) Then Vet(i+1,1)

Else Vet(i,j+1);

Exit;}

End;

If (j=N) Then Vet(i+1,1)

Else Vet(i,j+1);

End;

Procedure Khoitao;

Var i,j : Byte;

Begin

For i:=1 to N do

Begin

Dxh[i]:=True;

Dxc[i]:=True;

End;

d:=0;

For i:=1 to N do

For j:=1 to N do

Begin

If A[i,j]=1 then

Begin

Inc(d);

Tr[d].x:=i;

Tr[d].y:=j;

End;

End;

Tong:=0;

LT:=0;

Vet(1,1);

For i:=1 to N do

For j:=1 to N do B[i,j]:=1;

For i:=1 to d do B[Tr[i].x,Tr[i].y] := 1;

For i:=1 to LT do B[LKQ[i].x,LKQ[i].y] := 2;

Writeln('Cach xep duoc nhieu xe nhat : ',LT);

Hien(B);

End;

BEGIN

Clrscr;

Input;

Hien(A);

Khoitao;

Write(#10#13,'Enter to quit ');

Readln;

END.

C11_B20 ( Bài NETWORK OF SCHOOLS ) - Đề thi quốc tế 1996

Uses Crt;

Const Max = 110;

{ Inp = 'c:\qt96\data\net\input9.txt'; }

Inp = 'Inputtdh.txt';

Out = '';

Type Danhsach = Array[1..Max*Max] of Byte;

Tro = Array[1..Max] of LongInt;

Bacdinh = Array[1..Max] of Byte;

Daxet = Array[1..Max] of Boolean;

Var

Vao,Ra : Danhsach;

Tv,Tr : Tro;

D : Daxet;

V,R : Bacdinh;

N : Byte;

Procedure Baoloi(S : String);

Begin Writeln(S); Readln; Halt; End;

Procedure DocF;

Var i,j : Byte;

k,h : LongInt;

F : Text;

Begin

Assign(F,Inp);

{$I-} Reset(F); {$I+}

If Ioresult<>0 then Baoloi('Khong thay File '+inp);

Readln(F,N);

k := 0;

For i:=1 to N do

Begin

Read(F,j);

While j<>0 do

Begin

Inc(k);

Ra[k] := j;

Inc(R[i]);

Inc(V[j]);

Read(F,j);

End;

Tr[i] := k;

Readln(F);

End;

Close(F);

h := 0;

For i:=1 to N do

Begin

For k:=Tr[i-1]+1 to Tr[i] do { Ra[k]=i <-> A[j,i] =1 }

For j:=1 to N do

If Ra[k] = j then

Begin

Inc(h);

Vao[h] := i;

Tv[j] := h;

End

End;

End;

Procedure Lam;

Var F : Text;

s : Byte;

colap : Boolean;

i,scum1, scum2, scl , khac,p,T,LT : Integer;

Procedure Loai(i:Byte;Var s:Byte;gd:Byte);{ Lan tu truong i }

Var k,j:Integer;

Begin

For k:=Tr[i-1]+1 to Tr[i] do

Begin { Xoa cum loai 1 }

j := Ra[k];

If Not D[j] then

Begin

D[j]:= True;

If R[j]=0 then Inc(s);

Loai(j,s,kk);

End;

End;

If gd =1 then

For k:=Tv[i-1]+1 to Tv[i] do { Xoa cum loai 2 }

Begin

j := Vao[k];

If Not D[j] then

Begin

D[j]:= True;

If R[j]=0 then Inc(s);

Loai(j,s,kk);

End;

End;

End;

Begin

Fillchar(D,sizeof(D),False);

Assign(f,Out);

Rewrite(f);

scum1:=0; scum2:=0; T := 0; scl:=0; khac:= 0;

For i:=1 to N do

If Not D[i] and (V[i]=0) and (R[i]<>0) then

Begin

D[i]:= True;

s:=0;

Loai(i,s,0);

If s>0 then T := T+s;

Inc(scum1);

End;

For i:=1 to N do

If Not D[i] and ((R[i]=0) and (V[i]<>0)) then

Begin

D[i]:= True;

s:=0;

Loai(i,s,1);

If s>0 then T:=T+s;

Inc(scum2);

End;

{ Xoa nhung diem con lai : co lap hoac luan quan }

For i:=1 to N do

If Not D[i] then

Begin

colap := False;

If (V[i]=0) and (R[i]=0) then

Begin

Inc(scl); { k:so diem co lap hoac luan quan}

colap := true;

End;

D[i]:= True;

If Not colap then

Begin

Inc(khac);

s:=0;

Loai(i,s,1);

End;

End;

LT := scum1+scum2+scl+khac;

Writeln(f,LT);

LT := T+scum1+scum2+scl+khac;

If scum1+scum2+khac = 1 then LT := T;

Writeln(LT);

Close(F);

End;

BEGIN

Clrscr;

DocF;

Lam;

Readln;

Writeln('Da xong ');

END.

Bài 2 - Đề thi chọn đội tuyển Quốc gia năm 1997 ( dự kỳ thi quốc tế tại Nam Phi )

Cho lưới ô vuông kích thước 8x8 và 21 thanh Triminô , mỗi thanh là một hình chữ nhật gồm 3 ô vuông , trên mỗi ô của thanh Triminô có một chữ số trong phạm vi từ 1 đến 8 .

Yêu cầu tìm cách xếp 21 quân Triminô này lên lưới , sao cho :

- Chỉ còn đúng 1 ô của lưới không bị phủ .

- Số có 8 chữ số tạo thành bằng cách đọc các giá trị số trên các ô của đường chéo bắt đầu từ góc trên trái và kết thúc ở góc phải dưới là lớn nhất ( Quy ước : ô không bị phủ được coi là có chứa số 0 ).

Dữ liệu vào : Cho trên File văn bản ‘TRIMINO.INP’ gồm 21 dòng , mỗi dòng 3 chữ số có trên một quân Triminô , số thứ 2 là số ở giữa của Triminô.

Dữ liệu ra : Kết quả ghi lên File văn bản ‘TRIMINO.OUT’ theo cấu trúc :

- Dòng đầu ghi số tìm được

- 8 dòng tiếp theo , mỗi dòng ứng với 1 hàng của lưới tính từ trên xuống , ghi 8 giá trị số trên các ô của hàng theo thứ tự từ trái qua phải .

‘TRIMINO.INP’

‘TRIMINO.OUT’

8 7 1 1 3 6 1 1

3 8 1 1 8 3 2 1

1 7 8 1 1 0 3 4

3 1 1 8 1 1 8 7

6 7 2 6 7 1 2 2

1 3 7 1 1 7 2 1

1 1 6 5 7 1 7 1

5 1 6 3 6 1 3 6

1 1 7

1 3 6

1 2 3

1 1 4

1 7 1

1 8 3

1 3 6

1 6 3

1 3 4

1 7 3

1 2 7

1 7 8

1 8 7

1 2 2

1 1 5

1 7 6

1 6 5

1 6 5

1 6 8

1 6 3

1 7 4

Uses Crt;

Const Fi = 'Trimino.inp';

Fo = 'Trimino.out';

Type Banco = Array[1..8,1..8] of Byte;

Mathanh = Array[1..8,1..8] of Byte;

Daxet = Array[1..21] of Boolean;

Thanh = Array[1..21,1..4] of Byte;

Var B,LB : Banco;

M,LM : Mathanh;

D : Daxet;

T : Thanh;

F : Text;

Ldcheo : LongInt;

q,x,y,x1,x2,y1,y2,h1 : Byte;

Procedure TaoF;

Var i : Byte;

F : Text;

Begin

Assign(F,Fi);

ReWrite(F);

For i:=1 to 21 do

Writeln(F,Random(8)+1,' ',Random(8)+1,' ',Random(8)+1,' ');

Close(F);

End;

Procedure DocF;

Var F : Text;

i,j : Byte;

Begin

Assign(F,Fi);

{$I-} Reset(f);{$I+}

If IoResult<>0 then

Begin

Writeln('Khong thay ',Fi);

Readln;

Halt;

End;

For i:=1 to 21 do

Begin

For j:=1 to 3 do Read(F,T[i,j]);

Readln(F);

T[i,4] := i;

End;

Close(F);

End;

Procedure Timhuong(q: Byte;Var h1 : Byte);

Var i,j,d1 : Byte;

Begin

x1 := 1;y1 :=1;x2 :=1;y2 :=1;

If q=22 then Exit;

d1 := 0;

For i:=1 to 8 do

For j:=1 to 8 do

Begin

If (M[i,j] = q) then

If (d1=0) then

Begin

x1 := i;y1 := j;

Inc(d1);

End

Else

Begin

x2 := i;y2 :=j;

Inc(d1);

If d1=3 then

Begin

If y2>y1 then h1 := 1 Else h1 := 2;

Exit;

End;

End;

End;

End;

Function Timvitri(i : Byte) : Byte; {Tim vi tri quan A[i,i] la 1,2,3}

Begin

If M[i,i]=22 then Begin Timvitri := 0;Exit; End;

x1 := 1;y1 :=1;x2 :=1;y2 :=1;

Timhuong(M[i,i],h1); {Tim huong cua quan 8 }

If (i=x1) and (i=y1) then Timvitri := 1 Else

If (i=x2) and (i=y2) then Timvitri := 3 Else

Timvitri := 2;

End;

Function QMax(vt : Byte): Byte; {Tim thanh co phan tu max o vitri=vt }

Var t1,i : Byte;

Max : Byte;

Begin

Max := 0;

If vt = 0 then Exit;

For i:=1 to 21 do

If (Not D[i]) then

If vt in [1..3] then

If (T[i,vt]> Max) then

Begin

T1 := T[i,4];

Max := T[i,vt];

End;

QMax := T1;

End;

Procedure Doi(i : Byte);

Var q1,q2,q3,vt1,k: Byte; Nguoc : Boolean;

Begin

q1 := M[i,i];

vt1 := Timvitri(i); { Duoc gia tri x1,x2,y1,y2,h1 }

If vt1=2 then q2 := QMax(2)

Else

Begin

q2 := QMax(1);

q3 := Qmax(3);

If q2<q3 then

Begin

q2 := q3;

nguoc := True;

End

Else nguoc := False;

End;

If Not (q2 in [1..21] ) then Exit;

D[q2] := True;

If Not nguoc then

Begin

Case h1 of

1: For k:=1 to 3 do B[x1,y1+k-1]:=T[q2,k];

2: For k:=1 to 3 do B[x1+k-1,y1]:=T[q2,k];

End;

End

Else

{If nguoc then}

Begin

Case h1 of

1: For k:=1 to 3 do B[x1,y1+k-1]:=T[q2,4-k];

2: For k:=1 to 3 do B[x1+k-1,y1]:=T[q2,4-k];

End;

End;

End;

Procedure Tim(Var x,y : Byte);

Begin

While (M[x,y]>0) and (x in [1..8]) and (y in [1..8]) do

If y<8 then Inc(y)

Else If x<8 then

Begin Inc(x);y:=1;End;

End;

Function Chapnhan(x,y,hg : Byte): Boolean;

Var i : Byte;

Begin

Chapnhan := False;

If ((hg=1) and (y>6)) or ((hg=2) and (x>6)) then Exit;

Case hg of

1 : For i:=1 to 3 do If M[x,y+i-1]>0 then Exit;

2 : For i:=1 to 3 do If M[x+i-1,y]>0 then Exit;

End;

Chapnhan := True;

End;

Procedure Dat(x,y,hg : Byte);

Var i : Byte;

Begin

Case hg of

1 : For i:=1 to 3 do M[x,y+i-1] := T[q,4];

2 : For i:=1 to 3 do M[x+i-1,y] := T[q,4];

End;

End;

Function Duongcheo(B : Banco): LongInt;

Var dc: LongInt; i : Byte;

Begin

dc := 0;

For i:=1 to 8 do

If (B[i,i]= 0) then dc := dc*10

Else dc := dc*10+B[i,i];

Duongcheo := dc;

End;

Procedure Xoa(x,y,hg : Byte);

Var i : Byte;

Begin

Case hg of

1 : For i:=1 to 3 do M[x,y+i-1] := 0;

2 : For i:=1 to 3 do M[x+i-1,y] := 0;

End;

End;

Procedure GhiLB;

Var i,j : Byte;

Begin

For i:=1 to 8 do

Begin

For j:=1 to 8 do Write(F,LB[i,j]:3);

Writeln(F);

End;

End;

Procedure GhiLM;

Var i,j : Byte;

Begin

For i:=1 to 8 do

Begin

For j:=1 to 8 do Write(F,LM[i,j]:3);

Writeln(F);

End;

Writeln(F);

End;

Procedure Ghitoiuu;

Var i : Byte; p : LongInt;

Begin

FillChar(D,Sizeof(D),False);

FillChar(B,Sizeof(B),0);

For i:=1 to 8 do Doi(i);

p := duongcheo(B);

If p>Ldcheo then

Begin

Ldcheo := p;

LB := B;

LM := M;

End;

End;

Procedure Vet(x,y : Byte);

Var hg,i,j : Byte;

Begin

Tim(x,y);

For hg := 1 to 2 do

If chapnhan(x,y,hg) then

Begin

Inc(q);

Dat(x,y,hg);

If q=21 then

Ghitoiuu Else Vet(x,y);

Dec(q);

Xoa(x,y,hg);

End;

End;

Procedure Datnot;

Var i,j,k,dem : Byte;

Begin

FillChar(D,Sizeof(D),False);

For i:=1 to 8 do D[LM[i,i]]:= True;

For k:=1 to 21 do

If Not D[k] then

Begin

dem := 0;

For i:=1 to 8 do

For j:=1 to 8 do

If LM[i,j]=k then

Begin

Inc(dem);

LB[i,j]:= T[k,dem];

End;

End;

End;

BEGIN

Clrscr;{ TaoF;}

DocF; Assign(F,Fo); ReWrite(F);

Ldcheo := 0;

Writeln('Please wait ... ');

For x:=1 to 8 do

For y:=1 to 8 do

Begin

FillChar(M,Sizeof(M),0);

FillChar(B,Sizeof(B),0);

q := 0;

M[x,y] := 22;

Vet(1,1);

End;

Datnot;

GhiLM;

GhiLB;

Close(F);

Writeln('Da xong ');

Readln;

END.

Bài trên làm theo sơ đồ sau :

1 - Cho ô trống tuỳ ý trên bàn cờ , coi các Triminô như nhau ( nghĩa là không để ý tới các số trên chúng ) , đặt 21 quân Triminô lên bàn cờ , sẽ đựơc kết quả đầu tiên là : chỉ khi ô trống ở vào các vị trí (3,3) ; (3,6) ; (6,3) ; (6,6) thì mới đặt được . Tất cả có 1424 cách đặt theo kiểu này (tạm gọi mỗi cách là 1 cấu hình của bàn cờ ).

2 - Với mỗi cách đặt trên , bây giờ xếp các Triminô lần lượt vào các vị trí trên đường chéo từ góc trên_trái cho đến góc dưới_phải , sao cho tại mỗi vị trí là tốt nhất :

+ Xem ô (i,i) đang xét là ô ở vị trí thứ mấy trong thanh Triminô Ti chứa ô (i,i) của cấu hình đang xét .(gọi vị trí này là vt )

+ Duyệt các Triminô chưa dùng trong 21 Triminô , tìm thanh nào có số lớn nhất ở vị trị vt . Nếu vt=1 hoặc 3 thì phải tìm số lớn nhất ở cả 2 vị trí 1 và 3 .Gọi thanh tìm được là thanh Tx

+ Trên bàn cờ thay tương ứng thanh Ti bằng thanh Tx , xoá thanh Tx vì đã sử dụng

3 - Tính đường chéo , nếu thấy tốt hơn thì lưu lại bàn cờ và cấu hình tương ứng

4 - Đặt nốt các thanh Triminô chưa dùng vào bàn cờ theo lưu cấu hình ( chỉ cần 1 cách đặt nốt )

PHẦN 3

CÂY - CÂY KHUNG NGẮN NHẤT

I / Định nghĩa :

Cây là đồ thị hữu hạn , vô hướng , liên thông , không có chu trình , có ít nhất 2 đỉnh .

II / Tính chất :

1 - Định lý 1 :

Nếu H là cây có N đỉnh thì H có các tính chất sau đây :

a) Thêm vào H một cạnh nối 2 đỉnh bất kỳ không kề nhau , H sẽ xuất hiện chu trình .

b) Bớt đi 1 cạnh trong H thì H không liên thông

c) Giữa 2 đỉnh bất kỳ của H luôn tồn tại 1 đường đi duy nhất ( vậy H là đồ thị đơn)

d) H có N-1 cạnh

2 - Định lý 2 :

Nêú đồ thị G liên thông có N đỉnh và N-1 cạnh thì G là cây .

Vậy cây là đồ thị liên thông có chu số bằng 0 ( suy từ công thức Ơle )

3 - Ghi chú :

Từ 1 đồ thị có thể hình thành nhiều cây khác nhau ( gọi là các cây khung của đồ thị ) . Trong số các cây khung của đồ thị , có 1 cây được tạo ra một cách đơn giản như sau : nối 1 đỉnh với n-1 đỉnh còn lại !

Số cây khung của 1 đồ thị đầy đủ là N ^n-2 ( N số đỉnh )

Số cây khung của một đồ thị có hữu hạn đỉnh là một số hữu hạn ,nên luôn tìm được ít nhất 1 cây khung có tổng độ dài nhỏ nhất ( nguyên lý biên ). Ta gọi cây khung này là cây khung ngắn nhất .

Bài toán tìm cây khung ngắn nhất là một bài toán gặp trong thực tế :

Thí dụ : Xây dựng mạng dây điện thoại nối N thành phố sao cho 2 thành phố bất kỳ liên lạc được với nhau và tổng đường dây điện ngắn nhất .Đó là bài toán tìm cây khung ngắn nhất . Ngược lại : Xây dựng mạng dây điện thoại nối N thành phố sao cho 2 thành phố bất kỳ liên lạc được với nhau và tổng độ tin cậy trên các đường dây điện là lớn nhất .Đó là bài toán tìm cây khung dài nhất .

III / Thuật toán Prim tìm cây khung nhỏ nhất :

Bước 1 : Khởi trị - Lấy 1 đỉnh i tuỳ ý đưa vào tập đỉnh của cây . Khi đó tập đỉnh của cây là Đ = {i }. Tập cạnh của cây là C = ∅ ( Tập rỗng )

Bước 2 : Gán nhãn - Với mỗi đỉnh k không thuộc Đ , ta gán cho nó nhãn k(i ,d ) trong đó i là tên đỉnh thuộc Đ ,kề với k , gần k nhất , còn d là khoảng cách giữa i và k . Nếu trong Đ không tìm được đỉnh i kề với k thì gán cho k nhãn k( 0 ,∞ ) .

Bước 3 : Kết nap - Chọn đỉnh k không thuộc tập Đ , có nhãn d nhỏ nhất , kết nạp k vào Đ .Vậy Đ = Đ + { k } . Nhãn của k là k( i ,d ) thì kết nạp cạnh ( i , k ) vào tập cạnh C . Vậy C = C + { cạnh ( i , k ) } . Gọi đỉnh k vừa kết nạp là i_{0 .}

Nếu số đỉnh của Đ bằng N thì kết thúc , còn không chuyển sang bước 4

Bước 4 : Sửa nhãn - Với mọi đỉnh k chưa thuộc Đ có nhãn là k( i, d ) mà k kề với i ₀ - là đỉnh vừa được kết nạp vào tập đỉnh ở bước 3 - ta sửa lại nhãn của k theo nguyên tắc sau : Gọi độ dài cung (i₀ ,k ) là e

Nếu d > e thì đỉnh k có nhãn mới là k( i ₀ , e )

k

(i,23)

i ₀

(i₀,10)

i

e=15

i₀

Nhãn mới

k (i₀,15)

+) i₀ : vừa kết nạp vào Đ , k : không thuộc Đ

Thí dụ :

12

6

5

2

3

4

1

16 3 13 5

12 10

16

7 16

File dữ liệu vào : PRIM.INT

6

0 16 3 12 0 0

16 0 12 0 7 0

3 12 0 13 16 10

12 0 13 0 0 5

0 7 16 0 0 16

0 0 10 5 16 0

File dữ liệu ra : PRIM.OUT

( 1, 3)= 3 ( 3, 6)= 10 ( 6, 4)= 5 ( 3, 2)= 12 ( 2, 5)= 7

Tong gia tri cay khung ngan nhat la 37

Uses Crt;

Const Fi = 'prim.txt';

Fo = 'prim.out';

Max = 200;

Var A : Array[1..Max,1..Max] of Byte;

D : Array[1..Max] of Boolean;

C : Array[0..Max] of record x1,x2 : Byte; end;

Nh : Array[1..Max] of record truoc,giatri : Byte; end;

N,dd,socanh : Byte;

{canh : Integer;}

{--------------------------------}

Procedure DocF;

Var f : Text;

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;

Close(f);

End;

{--------------------------------}

Procedure Napdinh1;

Begin

Fillchar(d,sizeof(d),False);

d[1] := True;

dd := 1;

End;

{--------------------------------}

Function Min(xj : Byte): Byte;

Var xi,p,i : Byte;

Begin

xi := 0; p := 255;

For i:=1 to N do

If d[i] then

If (p>a[i,xj]) and (a[i,xj]>0) then

Begin

xi := i; p := a[i,xj];

End;

Min := xi;

End;

{--------------------------------}

Procedure Gannhan;

Var xi,xj : Byte;

Begin

For xj:=1 to N do

If not d[xj] then

Begin

xi := Min(xj);

If (xi>0) and (A[xi,xj]>0) then

Begin

nh[xj].truoc := xi;

nh[xj].giatri:= A[xi,xj];

End

Else

If xi=0 then

Begin

nh[xj].truoc := 0;

nh[xj].giatri:= 255;

End;

End;

End;

{--------------------------------}

Procedure Ketnapthem;

Var p,j,xj : Byte;

Begin

p := 255;

For j:=1 to n do

If not d[j] then

Begin

If (nh[j].giatri<p) then

Begin

xj := j;

p := nh[j].giatri;

End;

End;

d[xj] := True;

Inc(socanh);

c[socanh].x1 := nh[xj].truoc;

c[socanh].x2 := xj;

dd := xj;

End;

{--------------------------------}

Procedure Suanhan;

Var xj : Byte;

Begin

For xj:=1 to N do

If (not D[xj]) and (A[xj,dd]>0) then

Begin

If Nh[xj].giatri>A[xj,dd] then

Begin

Nh[xj].truoc := dd;

Nh[xj].giatri:= A[xj,dd];

End;

End;

End;

{--------------------------------}

Procedure Hiencanh;

Var i,p : Byte;f : Text;

Begin

Assign(f,fo);

Rewrite(f);p:=0;

For i:=1 to n-1 do

Begin

p := A[c[i].x1,c[i].x2]+p;

Write(f,'(',c[i].x1:2,',',c[i].x2:2,')=',A[c[i].x1,c[i].x2]:3,' ':3);

End;

Writeln(f);

Writeln(f,'Tong gia tri cay khung ngan nhat la ',p);

Close(f);

End;

{--------------------------------}

Procedure TT_Prim;

Var Ok : Boolean;

Begin

SoCanh := 0;

Fillchar(nh,sizeof(nh),0);

Napdinh1;

Gannhan;

Ok := False;

Repeat

Ketnapthem;

If Socanh=N-1 then Ok:= True

Else Suanhan;

Until Ok;

Hiencanh;

End;

{--------------------------------}

BEGIN

Clrscr;

DocF;

TT_Prim

END.

PHẦN 4

TÌM ĐƯỜNG ĐI NGẮN NHẤT

THUẬT TOÁN DI JSKTRA VÀ FORD-BELLMAN

Một bài toán thường gặp trên đồ thị là tìm đường đi ngắn nhất từ đỉnh thứ nhất (ký hiệu là xp ) tới đỉnh thứ hai ( ký hiệu là đ ). Khi vét cạn duyệt mọi đường đi từ xp tới đ , nếu không chú ý các cận ( trên hoặc dưới ) thích hợp để tránh các đường đi không tới đích , có thể duyệt không hết được khi đồ thị nhiều cung . Sau đây là 2 thuật toán giúp tránh tình trạng đó trong nhiều đồ thị.

I / Thuật toán Di jsktra ( gán nhãn ) :

Tư tưởng của thuật toán là trong quá trình xây dựng đường đi từ xp tới đ ,luôn kết hợp với việc chọn lựa đường đi để nó tốt dần lên bằng cách thay đổi liên tục nhãn tại các đỉnh .Mỗi đỉnh i sẽ có nhãn gồm 2 đặc trưng : Đặc trưng 1 ghi nhận đỉnh kề đi tới i , đặc trưng 2 ghi nhận độ dài đường đi ngắn nhất từ đỉnh xp tới đỉnh i này . Do đó khi tới đỉnh cuối cùng ta có ngay đường đi ngắn nhất . Các bước của thuật toán như sau :

Bước 1 - Khởi trị :

+ Nhãn đỉnh xuất phát là xp(0,0) : đỉnh đi tới đỉnh xp là đỉnh 0 ,đường đi đã qua là 0 .Các đỉnh i còn lại có nhãn là i (0, ∞ ) : có nghĩa đỉnh tới i là đỉnh 0 , đường đã qua tới i là vô cùng lớn .

+ Khởi trị mảng đánh dấu : Các đỉnh đều chưa tới .

Bước 2 - Sửa nhãn :

Vòng lặp :

Begin

+ Chọn một đỉnh i trong các đỉnh chưa tới và có nhãn độ dài nhỏ nhất . Đánh dấu đã tới đỉnh i.

+ Sửa lại nhãn các đỉnh k chưa tới theo công thức quy hoạch động

Nhãn[ k] = Min { Nhãn[k] , Nhãn[i] + A[i,k] }

End;

Cho đến khi tới đỉnh đích .

Bước 3 - Lần ngược ,hiện đường đi ngắn nhất :

+ Bắt đầu : đỉnh := đ ; cs := 1 ; KQ[cs] := đỉnh ;

+ Vòng lặp

Begin

đỉnh := Nhãn thứ nhất của đỉnh ;

Inc(cs);

KQ[cs] := đỉnh;

End;

Cho đến khi đỉnh = xp;

+ Duyệt ngược mảng KQ để hiện hành trình

+ Hiện độ dài đường đi .

II / Thuật toán Ford - BellMan :

Bằng 3 vòng For đơn giản , thuật toán đã thể hiện tinh thần quy hoạch động một cách

“ đẹp đẽ bất ngờ “ :

Với 2 đỉnh i và j ( 1 ≤ i, j ≤ N ) , đường đi ngắn nhất từ i tới j là D[i,j] rõ ràng là đại lượng nhỏ nhất trong các tổng : D[i,k] + D[k,j] trong đó k là mọi đỉnh trung gian ( con đường đi từ i tới j sẽ đi qua k ).

j

k

i

D[i,j] = Min { D[i,k] + D[k,j] } ∀ k

Procedure DgdiFB;

Var i,j,k : Integer;

Begin

For k:=1 to N do

For i:=1 to N do

For j := 1 to N do

if A[i,k]^.dd +A[i,k]^.dd <A[i,j]^.dd then

Begin

A[i,j]^.dd := A[i,k]^.dd +A[i,k]^.dd ;

A[i,j]^.đỉnh := k;

End;

End;

III / Bài tập mẫu :

Bài 1 : Cho đồ thị vô hướng liên thông từ File “DGDI.INP” tổ chức như sau :

+ Dòng thứ nhất ghi 3 số : N,xp,đ ( số đỉnh , tên đỉnh xuất phát , đỉnh đích )

+ Các dòng tiếp theo : mỗi dòng 3 số : i,j , A[i,j] ( A[i,j] là khoảng cách i tới j )

Nếu i=0 thì kết thúc dữ liệu về đồ thị này

Bằng thuật toán Di jsktra tìm đường đi ngắn nhất từ xp tới đ

Bài 2 : Nội dung như trên nhưng tìm đường đi ngắn nhất bằng thuật toán For-Bellman

Lời giải :

Bài 1 : Bằng thuật toán Di jsktra tìm đường đi ngắn nhất

Uses Crt;

Const Max = 100;

Fi = 'duongdi.inp';

Type Ta = Array[1..Max,1..Max] of Integer;

Re = Record

t : Byte;

h : Word;

End;

Nhan = Array[0..Max] of Re;

Dau = Array[1..Max] of Boolean;

Var N,xp,d : Byte;

A : ^Ta;

F : Text;

Procedure DocF;

Var i,j : Byte;

Begin

Assign(F,Fi);

Reset(F);

Readln(F,N,xp,d);

New(A);

For i:=1 to N do

For j:=1 to n do A^[i,j] := MaxInt;

While not Seekeof(F) do

Begin

Read(F,i,j);

If i=0 then

Begin Close(F);Exit;End;

Readln(F,A^[i,j]);

End;

For i:=1 to N do A^[i,i] := 0;

Close(F);

End;

Procedure Lam;

Var NH : Nhan;

dd : Dau;

i,j : Byte;

Procedure Khoitao;

Var i : Byte;

Begin

For i:=1 to N do

Begin

NH[i].h := MaxInt;

DD[i] := False;

End;

NH[xp].h := 0;

NH[xp].t := 0;

End;

Function Min : Byte;

Var i,k : Byte;

Begin

i := 0;

For k:=1 to N do

If (Not DD[k]) and (NH[k].h<NH[i].h) then i := k;

Min := i;

End;

Procedure Sua(i : Byte); {i : dinh cuoi cua hanh trinh hien tai }

Var j : Byte;

Begin

DD[i] := True;

For j:=1 to N do

If (Not DD[j]) and (NH[j].h>NH[i].h+A^[i,j]) then

Begin

NH[j].h := NH[i].h+A^[i,j];

NH[j].t := i;

End;

End;

Procedure Lannguoc;

Var S : String;

i,j : Byte;

Begin

i := d;

S := '';

While i>0 do

Begin

S := chr(i)+S;

i := NH[i].t;

End;

For i:=1 to Length(S) do Write(Ord(S[i]),' ');

End;

Begin

Clrscr;

Khoitao;

While Not DD[d] do

Begin

i := Min;

If i=0 then

Begin

Writeln('vo nghiem ');

Exit;

End;

Sua(i);

End;

Lannguoc;

End;

BEGIN

Clrscr;

DocF;

Lam;

Dispose(A);

Writeln('Da xong ');

Readln;

END.

Input

8 1 8

1 2 3

2 1 3

1 3 5

3 1 5

1 4 2

4 1 2

2 3 1

3 2 1

2 5 7

5 2 7

3 4 4

4 3 4

3 5 5

5 3 5

4 6 3

6 4 3

5 8 3

8 5 3

6 7 4

7 6 4

6 8 6

8 6 6

7 8 5

8 7 5

6 3 1

6 5 2

7 4 6

0

OUT

Nếu xp=1,d=8 thì có đường đi 1 4 6 5 8

Nếu xp=8,d=1 thì có đường đi 8 6 3 2 1

Bài 2 : Bằng thuật toán For-Bellman tìm đường đi ngắn nhất từ xp tới đ

Uses Crt;

Const Max = 100;

Fi = 'Duongdi.inp';

Type Ta = Array[1..Max,1..Max] of Record h : Word;tg : Byte; End;

Dau = Array[1..Max] of Boolean;

Var N,xp,t : Integer;

A : ^Ta;

F : Text;

Procedure DocF;

Var i,j : Byte;

Begin

Assign(F,Fi);

Reset(F);

New(A);

Readln(F,N,xp,t);

For i:=1 to N do

For j:=1 to N do

Begin

A^[i,j].h := MaxInt;

A^[i,j].tg := 0;

End;

For i:=1 to N do A^[i,i].h := 0;

While Not SeekEof(F) do

Begin

Read(F,i,j);

If i=0 then

Begin

Close(F);

Exit;

End;

Readln(F,A^[i,j].h);

End;

Close(F);

End;

Procedure FB;

Var i,j,k : Integer;

Begin

For k:=1 to N do

For i:=1 to N do

For j:=1 to N do

If (A^[i,k].h+A^[k,j].h<A^[i,j].h) then

Begin

A^[i,j].h := A^[i,k].h+A^[k,j].h;

A^[i,j].tg := k;

End;

End;

Procedure Lannguoc;

Var S : String;

i,x1,y1 : Byte;

Begin

If A^[xp,t].h = MaxInt then

Begin

Writeln('Vo nghiem ');

Exit;

End;

S := Char(xp)+char(t);

i := 1;

While i<Length(S) do

Begin

x1 := Ord(S[i]);

y1 := Ord(S[i+1]);

If A^[x1,y1].tg=0 then Inc(i)

Else Insert(Char(A^[x1,y1].tg),S,i+1);

End;

For i:=1 to Length(S) do Write(Ord(S[i]):4);

Writeln;

Writeln('Do dai : ',A^[xp,t].h);

End;

BEGIN

Clrscr;

DocF;

FB;

Lannguoc;

Dispose(A);

END.

PHẦN 3

CÂY - CÂY KHUNG NGẮN NHẤT

I / Định nghĩa :

Cây là đồ thị hữu hạn , vô hướng , liên thông , không có chu trình , có ít nhất 2 đỉnh .

II / Tính chất :

1 - Định lý 1 :

Nếu H là cây có N đỉnh thì H có các tính chất sau đây :

a) Thêm vào H một cạnh nối 2 đỉnh bất kỳ không kề nhau , H sẽ xuất hiện chu trình .

b) Bớt đi 1 cạnh trong H thì H không liên thông

c) Giữa 2 đỉnh bất kỳ của H luôn tồn tại 1 đường đi duy nhất ( vậy H là đồ thị đơn)

d) H có N-1 cạnh

2 - Định lý 2 :

Nêú đồ thị G liên thông có N đỉnh và N-1 cạnh thì G là cây .

Vậy cây là đồ thị liên thông có chu số bằng 0 ( suy từ công thức Ơle )

3 - Ghi chú :

Từ 1 đồ thị có thể hình thành nhiều cây khác nhau ( gọi là các cây khung của đồ thị ) . Trong số các cây khung của đồ thị , có 1 cây được tạo ra một cách đơn giản như sau : nối 1 đỉnh với n-1 đỉnh còn lại !

Số cây khung của 1 đồ thị đầy đủ là N ^n-2 ( N số đỉnh )

Số cây khung của một đồ thị có hữu hạn đỉnh là một số hữu hạn ,nên luôn tìm được ít nhất 1 cây khung có tổng độ dài nhỏ nhất ( nguyên lý biên ). Ta gọi cây khung này là cây khung ngắn nhất .

Bài toán tìm cây khung ngắn nhất là một bài toán gặp trong thực tế :

Thí dụ : Xây dựng mạng dây điện thoại nối N thành phố sao cho 2 thành phố bất kỳ liên lạc được với nhau và tổng đường dây điện ngắn nhất .Đó là bài toán tìm cây khung ngắn nhất . Ngược lại : Xây dựng mạng dây điện thoại nối N thành phố sao cho 2 thành phố bất kỳ liên lạc được với nhau và tổng độ tin cậy trên các đường dây điện là lớn nhất .Đó là bài toán tìm cây khung dài nhất .

III / Thuật toán Prim tìm cây khung nhỏ nhất :

Bước 1 : Khởi trị - Lấy 1 đỉnh i tuỳ ý đưa vào tập đỉnh của cây . Khi đó tập đỉnh của cây là Đ = {i }. Tập cạnh của cây là C = ∅ ( Tập rỗng )

Bước 2 : Gán nhãn - Với mỗi đỉnh k không thuộc Đ , ta gán cho nó nhãn k(i ,d ) trong đó i là tên đỉnh thuộc Đ ,kề với k , gần k nhất , còn d là khoảng cách giữa i và k . Nếu trong Đ không tìm được đỉnh i kề với k thì gán cho k nhãn k( 0 ,∞ ) .

Bước 3 : Kết nap - Chọn đỉnh k không thuộc tập Đ , có nhãn d nhỏ nhất , kết nạp k vào Đ .Vậy Đ = Đ + { k } . Nhãn của k là k( i ,d ) thì kết nạp cạnh ( i , k ) vào tập cạnh C . Vậy C = C + { cạnh ( i , k ) } . Gọi đỉnh k vừa kết nạp là i_{0 .}

Nếu số đỉnh của Đ bằng N thì kết thúc , còn không chuyển sang bước 4

Bước 4 : Sửa nhãn - Với mọi đỉnh k chưa thuộc Đ có nhãn là k( i, d ) mà k kề với i ₀ - là đỉnh vừa được kết nạp vào tập đỉnh ở bước 3 - ta sửa lại nhãn của k theo nguyên tắc sau : Gọi độ dài cung (i₀ ,k ) là e

Nếu d > e thì đỉnh k có nhãn mới là k( i ₀ , e )

k

(i,23)

i ₀

(i₀,10)

i

e=15

i₀

Nhãn mới

k (i₀,15)

+) i₀ : vừa kết nạp vào Đ , k : không thuộc Đ

Thí dụ :

12

6

5

2

3

4

1

16 3 13 5

12 10

16

7 16

File dữ liệu vào : PRIM.INT

6

0 16 3 12 0 0

16 0 12 0 7 0

3 12 0 13 16 10

12 0 13 0 0 5

0 7 16 0 0 16

0 0 10 5 16 0

File dữ liệu ra : PRIM.OUT

( 1, 3)= 3 ( 3, 6)= 10 ( 6, 4)= 5 ( 3, 2)= 12 ( 2, 5)= 7

Tong gia tri cay khung ngan nhat la 37

Uses Crt;

Const Fi = 'prim.txt';

Fo = 'prim.out';

Max = 200;

Var A : Array[1..Max,1..Max] of Byte;

D : Array[1..Max] of Boolean;

C : Array[0..Max] of record x1,x2 : Byte; end;

Nh : Array[1..Max] of record truoc,giatri : Byte; end;

N,dd,socanh : Byte;

{canh : Integer;}

{--------------------------------}

Procedure DocF;

Var f : Text;

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;

Close(f);

End;

{--------------------------------}

Procedure Napdinh1;

Begin

Fillchar(d,sizeof(d),False);

d[1] := True;

dd := 1;

End;

{--------------------------------}

Function Min(xj : Byte): Byte;

Var xi,p,i : Byte;

Begin

xi := 0; p := 255;

For i:=1 to N do

If d[i] then

If (p>a[i,xj]) and (a[i,xj]>0) then

Begin

xi := i; p := a[i,xj];

End;

Min := xi;

End;

{--------------------------------}

Procedure Gannhan;

Var xi,xj : Byte;

Begin

For xj:=1 to N do

If not d[xj] then

Begin

xi := Min(xj);

If (xi>0) and (A[xi,xj]>0) then

Begin

nh[xj].truoc := xi;

nh[xj].giatri:= A[xi,xj];

End

Else

If xi=0 then

Begin

nh[xj].truoc := 0;

nh[xj].giatri:= 255;

End;

End;

End;

{--------------------------------}

Procedure Ketnapthem;

Var p,j,xj : Byte;

Begin

p := 255;

For j:=1 to n do

If not d[j] then

Begin

If (nh[j].giatri<p) then

Begin

xj := j;

p := nh[j].giatri;

End;

End;

d[xj] := True;

Inc(socanh);

c[socanh].x1 := nh[xj].truoc;

c[socanh].x2 := xj;

dd := xj;

End;

{--------------------------------}

Procedure Suanhan;

Var xj : Byte;

Begin

For xj:=1 to N do

If (not D[xj]) and (A[xj,dd]>0) then

Begin

If Nh[xj].giatri>A[xj,dd] then

Begin

Nh[xj].truoc := dd;

Nh[xj].giatri:= A[xj,dd];

End;

End;

End;

{--------------------------------}

Procedure Hiencanh;

Var i,p : Byte;f : Text;

Begin

Assign(f,fo);

Rewrite(f);p:=0;

For i:=1 to n-1 do

Begin

p := A[c[i].x1,c[i].x2]+p;

Write(f,'(',c[i].x1:2,',',c[i].x2:2,')=',A[c[i].x1,c[i].x2]:3,' ':3);

End;

Writeln(f);

Writeln(f,'Tong gia tri cay khung ngan nhat la ',p);

Close(f);

End;

{--------------------------------}

Procedure TT_Prim;

Var Ok : Boolean;

Begin

SoCanh := 0;

Fillchar(nh,sizeof(nh),0);

Napdinh1;

Gannhan;

Ok := False;

Repeat

Ketnapthem;

If Socanh=N-1 then Ok:= True

Else Suanhan;

Until Ok;

Hiencanh;

End;

{--------------------------------}

BEGIN

Clrscr;

DocF;

TT_Prim

END.

PHẦN 4

TÌM ĐƯỜNG ĐI NGẮN NHẤT

THUẬT TOÁN DI JSKTRA VÀ FORD-BELLMAN

Một bài toán thường gặp trên đồ thị là tìm đường đi ngắn nhất từ đỉnh thứ nhất (ký hiệu là xp ) tới đỉnh thứ hai ( ký hiệu là đ ). Khi vét cạn duyệt mọi đường đi từ xp tới đ , nếu không chú ý các cận ( trên hoặc dưới ) thích hợp để tránh các đường đi không tới đích , có thể duyệt không hết được khi đồ thị nhiều cung . Sau đây là 2 thuật toán giúp tránh tình trạng đó trong nhiều đồ thị.

I / Thuật toán Di jsktra ( gán nhãn ) :

Tư tưởng của thuật toán là trong quá trình xây dựng đường đi từ xp tới đ ,luôn kết hợp với việc chọn lựa đường đi để nó tốt dần lên bằng cách thay đổi liên tục nhãn tại các đỉnh .Mỗi đỉnh i sẽ có nhãn gồm 2 đặc trưng : Đặc trưng 1 ghi nhận đỉnh kề đi tới i , đặc trưng 2 ghi nhận độ dài đường đi ngắn nhất từ đỉnh xp tới đỉnh i này . Do đó khi tới đỉnh cuối cùng ta có ngay đường đi ngắn nhất . Các bước của thuật toán như sau :

Bước 1 - Khởi trị :

+ Nhãn đỉnh xuất phát là xp(0,0) : đỉnh đi tới đỉnh xp là đỉnh 0 ,đường đi đã qua là 0 .Các đỉnh i còn lại có nhãn là i (0, ∞ ) : có nghĩa đỉnh tới i là đỉnh 0 , đường đã qua tới i là vô cùng lớn .

+ Khởi trị mảng đánh dấu : Các đỉnh đều chưa tới .

Bước 2 - Sửa nhãn :

Vòng lặp :

Begin

+ Chọn một đỉnh i trong các đỉnh chưa tới và có nhãn độ dài nhỏ nhất . Đánh dấu đã tới đỉnh i.

+ Sửa lại nhãn các đỉnh k chưa tới theo công thức quy hoạch động

Nhãn[ k] = Min { Nhãn[k] , Nhãn[i] + A[i,k] }

End;

Cho đến khi tới đỉnh đích .

Bước 3 - Lần ngược ,hiện đường đi ngắn nhất :

+ Bắt đầu : đỉnh := đ ; cs := 1 ; KQ[cs] := đỉnh ;

+ Vòng lặp

Begin

đỉnh := Nhãn thứ nhất của đỉnh ;

Inc(cs);

KQ[cs] := đỉnh;

End;

Cho đến khi đỉnh = xp;

+ Duyệt ngược mảng KQ để hiện hành trình

+ Hiện độ dài đường đi .

II / Thuật toán Ford - BellMan :

Bằng 3 vòng For đơn giản , thuật toán đã thể hiện tinh thần quy hoạch động một cách

“ đẹp đẽ bất ngờ “ :

Với 2 đỉnh i và j ( 1 ≤ i, j ≤ N ) , đường đi ngắn nhất từ i tới j là D[i,j] rõ ràng là đại lượng nhỏ nhất trong các tổng : D[i,k] + D[k,j] trong đó k là mọi đỉnh trung gian ( con đường đi từ i tới j sẽ đi qua k ).

j

k

i

D[i,j] = Min { D[i,k] + D[k,j] } ∀ k

Procedure DgdiFB;

Var i,j,k : Integer;

Begin

For k:=1 to N do

For i:=1 to N do

For j := 1 to N do

if A[i,k]^.dd +A[i,k]^.dd <A[i,j]^.dd then

Begin

A[i,j]^.dd := A[i,k]^.dd +A[i,k]^.dd ;

A[i,j]^.đỉnh := k;

End;

End;

III / Bài tập mẫu :

Bài 1 : Cho đồ thị vô hướng liên thông từ File “DGDI.INP” tổ chức như sau :

+ Dòng thứ nhất ghi 3 số : N,xp,đ ( số đỉnh , tên đỉnh xuất phát , đỉnh đích )

+ Các dòng tiếp theo : mỗi dòng 3 số : i,j , A[i,j] ( A[i,j] là khoảng cách i tới j )

Nếu i=0 thì kết thúc dữ liệu về đồ thị này

Bằng thuật toán Di jsktra tìm đường đi ngắn nhất từ xp tới đ

Bài 2 : Nội dung như trên nhưng tìm đường đi ngắn nhất bằng thuật toán For-Bellman

Lời giải :

Bài 1 : Bằng thuật toán Di jsktra tìm đường đi ngắn nhất

Uses Crt;

Const Max = 100;

Fi = 'duongdi.inp';

Type Ta = Array[1..Max,1..Max] of Integer;

Re = Record

t : Byte;

h : Word;

End;

Nhan = Array[0..Max] of Re;

Dau = Array[1..Max] of Boolean;

Var N,xp,d : Byte;

A : ^Ta;

F : Text;

Procedure DocF;

Var i,j : Byte;

Begin

Assign(F,Fi);

Reset(F);

Readln(F,N,xp,d);

New(A);

For i:=1 to N do

For j:=1 to n do A^[i,j] := MaxInt;

While not Seekeof(F) do

Begin

Read(F,i,j);

If i=0 then

Begin Close(F);Exit;End;

Readln(F,A^[i,j]);

End;

For i:=1 to N do A^[i,i] := 0;

Close(F);

End;

Procedure Lam;

Var NH : Nhan;

dd : Dau;

i,j : Byte;

Procedure Khoitao;

Var i : Byte;

Begin

For i:=1 to N do

Begin

NH[i].h := MaxInt;

DD[i] := False;

End;

NH[xp].h := 0;

NH[xp].t := 0;

End;

Function Min : Byte;

Var i,k : Byte;

Begin

i := 0;

For k:=1 to N do

If (Not DD[k]) and (NH[k].h<NH[i].h) then i := k;

Min := i;

End;

Procedure Sua(i : Byte); {i : dinh cuoi cua hanh trinh hien tai }

Var j : Byte;

Begin

DD[i] := True;

For j:=1 to N do

If (Not DD[j]) and (NH[j].h>NH[i].h+A^[i,j]) then

Begin

NH[j].h := NH[i].h+A^[i,j];

NH[j].t := i;

End;

End;

Procedure Lannguoc;

Var S : String;

i,j : Byte;

Begin

i := d;

S := '';

While i>0 do

Begin

S := chr(i)+S;

i := NH[i].t;

End;

For i:=1 to Length(S) do Write(Ord(S[i]),' ');

End;

Begin

Clrscr;

Khoitao;

While Not DD[d] do

Begin

i := Min;

If i=0 then

Begin

Writeln('vo nghiem ');

Exit;

End;

Sua(i);

End;

Lannguoc;

End;

BEGIN

Clrscr;

DocF;

Lam;

Dispose(A);

Writeln('Da xong ');

Readln;

END.

Input

8 1 8

1 2 3

2 1 3

1 3 5

3 1 5

1 4 2

4 1 2

2 3 1

3 2 1

2 5 7

5 2 7

3 4 4

4 3 4

3 5 5

5 3 5

4 6 3

6 4 3

5 8 3

8 5 3

6 7 4

7 6 4

6 8 6

8 6 6

7 8 5

8 7 5

6 3 1

6 5 2

7 4 6

0

OUT

Nếu xp=1,d=8 thì có đường đi 1 4 6 5 8

Nếu xp=8,d=1 thì có đường đi 8 6 3 2 1

Bài 2 : Bằng thuật toán For-Bellman tìm đường đi ngắn nhất từ xp tới đ

Uses Crt;

Const Max = 100;

Fi = 'Duongdi.inp';

Type Ta = Array[1..Max,1..Max] of Record h : Word;tg : Byte; End;

Dau = Array[1..Max] of Boolean;

Var N,xp,t : Integer;

A : ^Ta;

F : Text;

Procedure DocF;

Var i,j : Byte;

Begin

Assign(F,Fi);

Reset(F);

New(A);

Readln(F,N,xp,t);

For i:=1 to N do

For j:=1 to N do

Begin

A^[i,j].h := MaxInt;

A^[i,j].tg := 0;

End;

For i:=1 to N do A^[i,i].h := 0;

While Not SeekEof(F) do

Begin

Read(F,i,j);

If i=0 then

Begin

Close(F);

Exit;

End;

Readln(F,A^[i,j].h);

End;

Close(F);

End;

Procedure FB;

Var i,j,k : Integer;

Begin

For k:=1 to N do

For i:=1 to N do

For j:=1 to N do

If (A^[i,k].h+A^[k,j].h<A^[i,j].h) then

Begin

A^[i,j].h := A^[i,k].h+A^[k,j].h;

A^[i,j].tg := k;

End;

End;

Procedure Lannguoc;

Var S : String;

i,x1,y1 : Byte;

Begin

If A^[xp,t].h = MaxInt then

Begin

Writeln('Vo nghiem ');

Exit;

End;

S := Char(xp)+char(t);

i := 1;

While i<Length(S) do

Begin

x1 := Ord(S[i]);

y1 := Ord(S[i+1]);

If A^[x1,y1].tg=0 then Inc(i)

Else Insert(Char(A^[x1,y1].tg),S,i+1);

End;

For i:=1 to Length(S) do Write(Ord(S[i]):4);

Writeln;

Writeln('Do dai : ',A^[xp,t].h);

End;

BEGIN

Clrscr;

DocF;

FB;

Lannguoc;

Dispose(A);

END.

PHẦN 1 : KHÁI NIỆM CHUNG

I / Định nghĩa đồ thị :

Đồ thị gồm tập hợp X và một ánh xạ F từ X vào X ( ánh xạ này có thể đa trị ). Kí hiệu đồ thị là G(X,F) .

Thí dụ : Trong mặt phẳng , hình ảnh hình học của đồ thị có thể như :

+ Tập X : tập điểm ( gọi là tập đỉnh của đồ thị )

+ Ánh xạ F biểu hiện như tập cung U ( có hướng hoặc vô hướng )

Cung nối đỉnh x_i với đỉnh x_k kí hiệu là u _{i k} .

Đỉnh x_i gọi là đỉnh gốc , đỉnh x_k gọi là đỉnh ngọn của cung u_ik . Cung nối 1 đỉnh với chính đỉnh ấy gọi là cung khuyên .

Đỉnh treo là đỉnh chỉ có 1 cung nối với nó , cung này cũng gọi là cung treo

Đỉnh cô lập là đỉnh không có cung nào nối với nó .

Tập hợp các cung của một đồ thị kí hiệu là U , thì đồ thị ký hiệu là G(X,U)

Ma trận kề của đồ thị ( có N đỉnh ) là ma trận A(N,N) được tạo như sau :

Nếu có s cung nối đỉnh i với đỉnh k thì A[i,k] = s ( thông thường s=1 ) . Nếu không có cung nào nối thì A[i,k]=0

5

6

7

2

4

3

1

Trong ma trận A(7,7) qui định A[i,i]=0 (i=1..7)

II / Phân loại đồ thị :

Cách phân loại theo số cung S nối 2 đỉnh : nếu S = 0..1 thì có đơn đồ thị , nếu S>1 có đa đồ thị

Cách phân loại theo cung có hướng và vô hướng :

+ Trong đồ thị có hướng qui định chiều đi trên cung từ đỉnh gốc đến đỉnh ngọn.

+ Trong đồ thị vô hướng không phân biệt chiều đi trên cung ( nghĩa là không định hướng trên cung ). Khi đó trong ma trận kề ta có A[i,k] = A[k,i] ( số cung từ i tới k cũng là số cung từ k tới i ). Đồ thị vô hướng còn gọi là đồ thị đối xứng . Cung trong đồ thị đối xứng được gọi là cạnh của đồ thị

III / Một số định nghĩa khác :

a ) Trong đồ thị có hướng :

+ Tổng số cung đi vào một đỉnh gọi là bán bậc vào của đỉnh .Tổng số cung đi ra từ một đỉnh gọi là bán bậc ra của đỉnh .

+ Một dãy cung liên tiếp ( có thể không cùng chiều ) gọi là một dây chuyền.

+ Một dây chuyền mà ngọn của cung này là gốc của cung tiếp theo (trừ cung cuối cùng ) được gọi là một mạch ( còn gọi là đường đi có hướng )

+ Một mạch khép kín (ngọn cung cuối cùng trùng với gốc cung đầu tiên ) gọi là mạch đóng ( còn gọi là chu trình có hướng )

+ Chu trình sơ cấp là chu trình đi qua các đỉnh của nó không quá 1 lần (trừ đỉnh đầu và đỉnh cuối)

+ Độ dài của mạch là tổng khoảng cách các cung của nó (trong một số trường hợp người ta coi mỗi cung dài bằng 1 thì độ dài của mạch là số lượng cung trên mạch

+ Hai đỉnh được gọi là liên thông nếu tồn tại ít nhất 1 dây chuyền nối chúng . Hai đỉnh được gọi là liên thông mạnh nếu tồn tại ít nhất 1 mạch nối chúng .Một vùng liên thông của đồ thị là tập hợp một số đỉnh của đồ thị mà 2 đỉnh bất kỳ trong chúng liên thông nhau . Một vùng liên thông mạnh của đồ thị là tập hợp một số đỉnh của đồ thị mà 2 đỉnh bất kỳ trong chúng liên thông mạnh với nhau .

Một đồ thị được gọi là đồ thị liên thông nếu nó chỉ gồm 1 vùng liên thông duy nhất ,một đồ thị được gọi là đồ thị liên thông mạnh nếu nó chỉ gồm 1 vùng liên thông mạnh duy nhất .

Ta cũng có các định nghĩa tương tự cho đồ thị vô hướng :

b ) Trong đồ thị vô hướng :

+ Tổng số cạnh nối tới một đỉnh gọi là bậc của đỉnh .

+ Một dãy cạnh và đỉnh liên tiếp gọi là một đường đi

+ Một đường đi khép kín gọi là một chu trình

+ Chu trình sơ cấp là chu trình đi qua các đỉnh của nó không quá 1 lần (trừ đỉnh đầu và đỉnh cuối)

+ Độ dài của đường đi là tổng khoảng cách các cạnh của nó (trong một số trường hợp người ta coi mỗi cạnh dài bằng 1 thì độ dài của đường đi là số lượng cạnh trên đường đi

+ Hai đỉnh được gọi là liên thông nếu tồn tại ít nhất 1 đường đi nối chúng ..Một vùng liên thông của đồ thị là tập hợp một số đỉnh của đồ thị mà 2 đỉnh bất kỳ trong chúng liên thông nhau .

Một đồ thị được gọi là đồ thị liên thông nếu nó chỉ gồm 1 vùng liên thông duy nhất .

+ Cầu của đồ thị là cạnh có tính chất : nếu xoá nó khỏi đồ thị thì số vùng liên thông của đồ thị tăng thêm 1 vùng

c ) Đường đi và chu trình đặc biệt :

+ Đường đi qua tất cả các đỉnh, mỗi đỉnh qua đúng 1 lần , gọi là đường đi Hamintơn. Chu trình đi qua tất cả các đỉnh, mỗi đỉnh qua đúng 1 lần , gọi là chu trình Hamintơn.

+ Đường đi qua tất cả các cạnh, mỗi cạnh qua đúng 1 lần , gọi là đường đi Ơ le. Chu trình đi qua tất cả các cạnh, mỗi cạnh qua đúng 1 lần , gọi là chu trình Ơ le.

IV / Một vài tính chất khác trong đồ thị vô hướng:

1) Nếu đồ thị vô hướng , liên thông và không có chu trình thì khi xoá 1 cạnh sẽ mất tính liên thông .

2) Ngược lại : một đồ thị vô hướng , liên thông khi xoá 1 cạnh mà mất tính chất liên thông thì đồ thị đó không có chu trình

3) Điều kiện cần và đủ để đồ thị có chu trình Ơ le là bậc của mọi đỉnh đều chẵn

4) Điều kiện cần và đủ để đồ thị có đường đi Ơ le: số đỉnh bậc lẻ không lớn hơn 2

5) Hệ thức Ơle :

ct = sc - sd + svlt

C T : số chu trình Sc : số cạnh

Sđ : số đỉnh Svlt : số vùng liên thông .

Thí dụ :

5

4

3

2

1

Đồ thị bên có :

4 cạnh , 5 đỉnh , 1 vùng liên thông

Do đó số chu trình là :

CT = 4 - 5 +1 = 0 ( Không có chu trình )

V / Số ổn định trong và số ổn định ngoài :

1 ) Số ổn định trong :

+ Tập con A các đỉnh thuộc đồ thị G(X,E) là tập ổn định trong nếu mỗi cặp đỉnh thuộc A đều không kề nhau

+ Tập ổn định trong lớn nhất : Là tập ổn định trong và nếu thêm một đỉnh tuỳ ý thì không còn là tập ổn định trong .

+ Số phần tử của tập ổn định trong lớn nhất gọi là số ổn định trong . Ký hiệu là α(G)

2) Số ổn định ngoài :

+ Tập đỉnh B thuộc đồ thị G(X,E) gọi là tập ổn định ngoài nếu với mọi đỉnh y của đồ thị không thuộc B thì đều tìm thấy một đỉnh x thuộc B mà x và y có cạnh nối .

+ Tập ổn định ngoài nhỏ nhất là tập ổn định ngoài có số phần tử ít nhất .

+ Số phần tử của tập ổn định ngoài nhỏ nhất được gọi là số ổn định ngoài . Ký hiệu là β(G)

3 ) Một số tính chất :

+ Mọi tập con của tập ổn định trong cũng là tập ổn định trong .

+ Mọi tập đỉnh của đồ thị chứa tập ổn định ngoài cũng là tập ổn định ngoài .

4 ) Nhân đồ thị :

+ Nhân đồ thị là tập đỉnh của đồ thị có tính chất : vừa là tập ổn định trong vừa là tập ổn định ngoài

VI / Sắc số của đồ thị :

+ Sắc số của đồ thị là số màu ít nhất có thể tô các đỉnh đồ thị sao cho 2 đỉnh kề nhau tuỳ ý khác màu .

+ Một số định lý về sắc số :

ĐL1 : Đồ thị đầy đủ n đỉnh có sắc số bằng n

ĐL2 : Một chu trình có độ dài chẵn luôn có sắc số = 2

ĐL3 : Một chu trình có độ dài lẻ luôn có sắc số = 3

ĐL4 : Đồ thị hình hoa thị gồm 1 chu trình và 1 đỉnh A nối với các đỉnh của chu trình ( hình vẽ ) có sắc số = 3 nếu chu trình chẵn , có sắc số = 4 nếu chu trình lẻ

+ Thuật toán tìm sắc số :

Thuật toán 1 : Bằng cách áp dụng các định lý trên , ta tìm được khẳng định về số màu tô ít nhất là p . Vậy sắc số ≥ p . Sau đó chỉ ra được 1 cách tô chỉ bằng p màu . Từ đó kết luận được sắc số = p .

Thuật toán 2 : ( Tìm được gần đúng )

+ Các đỉnh chưa đánh dấu

+ Tính bậc các đỉnh

+ Sắp các đỉnh theo thứ tự bậc giảm dần

+ Tô đỉnh có bậc cao nhất và những đỉnh không kề với đỉnh này và chưa bị đánh dấu bằng cùng màu 1

+ Đánh dấu các đỉnh đã được tô màu.

+ Lại chọn đỉnh có bậc cao nhất , tô đỉnh có bậc cao nhất và những đỉnh không kề với đỉnh này và chưa bị đánh dấu bằng cùng màu mới ( giả sử đã dùng các màu từ 1 đến i thì bây giờ tô màu i+1 )

+ Quá trình như thế cho đến khi các đỉnh đều đã được đánh dấu

BÀI TẬP

1 ) Cho ma trận kề A(N,N) của đồ thị N đỉnh . Tìm số vùng liên thông của đồ thị .

Yêu cầu : File input : ‘SVLT.txt’

+ Dòng đầu : N

+ N dòng tiếp theo : Ma trận A(N,N)

Dữ liệu ra trên File ‘SVLT.out’

+ Dòng đầu : số S là số vùng liên thông

+ S dòng tiếp theo : Mỗi dòng ghi các đỉnh thuộc cùng 1 vùng liên thông

2 ) Cho hình chữ nhật H(M,N) m dòng , n cột gồm MxN ô vuông , mỗi ô vuông chứa số 0 hoặc 1. Tìm và tính diện tích các vùng liên thông chứa toàn số 0 trong 2 trường hợp :

+ Các ô số 0 nếu chung cạnh thì có đường đi tới nhau

+ Các ô số 0 nếu có điểm chung thì có đường đi tới nhau

Yêu cầu :

File input ‘HCN.txt’

Dòng đầu : 2 số M,N

M dòng tiếp theo : ma trận thể hiện hình chữ nhật H(M,N)

File output ‘HCN.out’

Mỗi trường hợp thể hiện một ma trận hình chữ nhật D(M,N) sao cho các ô của D cùng thuộc 1 vùng liên thông thì có cùng 1 mã số vùng . Những ô số 1 trong H thay bằng ô tương ứng trong D là kí tự ‘*’

Dòng cuối cùng là diện tích của các vùng .

3 ) Đề thi Quốc tế 1994 (tại Thuỵ Điển ) : Bài 2 ( 5-7-1994 )

Hình 2 biểu diễn bản đồ lâu đài . Hãy viết chương trình tính :

1 - Lâu đài có bao nhiêu phòng ?

2 - Phòng lớn nhất là bao nhiêu ?

3 - Bức tường nào cần loại bỏ để phòng càng rộng càng tốt ?

Lâu đài chia thành MxN (M ≤ 50, N ≤ 50 ) modul vuông . Mỗi môdul vuông có thể có từ 0 đến 4 bức tường

INPUT DATA

Bản đồ được lưu trữ tong file Input.txt ở dạng các số cho các môdul .

File bắt đầu từ số lượng các môdul theo hướng Bắc-Nam và số lượng các modul theo hướng Đông Tây.

Trong các dòng tiếp theo ,mỗi modul được mô tả bởi 1 số (0 ≤p≤15).Số đó là tổng của : 1 (= tường phía Tây ), 2 (=tường phía Bắc ) ,4 (=tường phía Đông ) , 8 ( = tường phía Nam) .

1 2 3 4 5 6 7 N (Bắc)

1

(Tây) W E (Đông)

2

3

S (Nam)

4

Mũi tên chỉ bức tường cần loại bỏ theo kết quả ở ví dụ

Các bức tường ở bên trong được xác định hai lần ; bức tường phía Nam trong modul (1,1) đồng thời là bức tơừng phía Bắc trong modul (2,1)

* Lâu đài luôn có ít nhất 2 phòng

INPUT.TXT của ví dụ :

4

7

11 6 11 6 3 10 6

7 9 6 13 5 15 5

1 10 12 7 13 7 5

13 11 10 8 10 12 13

Output data

Trong file ra OUTPUT.TXT viết trên 3 dòng : dòng thứ nhất viết số lượng phòng ,dòng tiếp đến là diện tích của phòng lớn nhất (tính theo số modul ) và bức tường cần loại bỏ (trước tiên là hàng sau đó là cột của modul có tường đó ) và dòng cuối cùng là hướng của bức tường .Trong ví dụ “4 1 E “ là một trong số các khả năng có thể ,bạn chỉ cần chỉ ra một )

5

9

4 1 E

4 ) Một vùng lãnh thổ có dạng một lưới ô vuông A gồm NxN ô (4 ≤ N ≤ 12) với mục đích phủ sóng truyền hình toàn vùng lãnh thổ ,người ta lập một dự án xây dựng một hệ thống gồm k trạm tiếp sóng ở k ô của lưới .Một trạm tiếp sóng đặt ở một ô nào đó của lưới không những bảo đảm phủ sóng ô này mà còn cho tất cả các ô có chung đỉnh với nó .Dữ liệu về dự án được cho trong 1 File dạng Text là PHUSONG.TXT trong đó dòng đầu tiên ghi số N ,trong k dòng tiếp theo , mỗi dòng ghi 2 số nguyên dương (x_i , y_i ) là toạ độ trên lưới của một trạm tiếp sóng của dự án ( hai số cách nhau bởi dấu cách ).Dữ liệu ra ghi trong File PHUSONG.OUT :

a) N dòng đầu là ma trận A(N,N) (các trạm tiếp sóng ghi số 1,ô khác ghi số 0 )

b) Dòng tiếp theo là số 0 hoặc số 1 : Số 1 là dự án phủ sóng toàn lãnh thổ,số 0 là dự án không phủ được toàn lãnh thổ

Trong trường hợp dự án không phủ toàn lãnh thổ , dòng tiếp theo là số S : số các ô chưa được phủ sóng , sau đó S dòng tiếp theo lần lượt mỗi dòng ghi toạ độ của một ô chưa được phủ sóng .

c) Trong trường hợp phủ sóng toàn lãnh thổ,hãy tìm cách loại bớt 1 số trạm tiếp sóng mà vẫn phủ sóng toàn lãnh thổ ,nếu không loại bỏ được thì ghi số 0 ,nếu loại bỏ được thì ghi số trạm loại bỏ nhiều nhất ,sau đó nêu rõ toạ độ các trạm bị loại bỏ (mỗi trạm 1 dòng )

Trong File PHUSONG.OUT , để ngăn cách kết quả từng câu , trước kết quả câu a) là dòng chữ “ CAU A” ; trước kết quả câu b) là dòng chữ “ CAU B” ; trước kết quả câu c) là dòng chữ “ CAU C”

5 ) Bài kiểm tra :

Cho đồ thị G vô hướng gồm N đỉnh , biểu diễn bởi ma trận A : A[i,j]=A[j,i]=0 hoặc 1( 0 là không có đường nối i với j , 1 là ngược lại ).Đồ thị gọi là liên thông đơn nếu với mọi i,j bất kỳ có đúng 1 đường đi nối i với j .

a) Kiểm tra A có liên thông đơn không .Nếu không thì loại bớt một số cạnh để liên thông đơn.

b) Giả sử G liên thông đơn, hãy tìm các cạnh độc đạo (là cạnh mà mọi đường đi dài nhất đều qua nó )

6 ) Cho đồ thị G(X,E) . Lập chương trình tìm số ổn định trong , số ổn định ngoài , tìm tập nhân ít phần tử nhất .

7 ) Cho N điểm , hãy dùng số màu ít nhất tô màu các điểm sao cho 2 điểm kề nhau thì khác màu nhau .

8 ) Đề thi Tin học Toàn quốc 3-1998 : Dàn đèn màu

Cho một lưới toạ độ nguyên , hoành độ từ 0 đến M , tung độ từ 0 đến N (M,N ≤200) . Trên k nút cho trước , mỗi nút cần đặt một đèn màu sao cho 2 đèn ở 2 nút có cùng hoành độ hoặc có cùng tung độ phải có màu khác nhau . Hãy tìm cách bố trí dàn đèn sao cho số màu phải dùng là ít nhất . Các màu đã sử dụng phải được đánh số bởi các số nguyên dương liên tục bắt đầu từ số 1

Dữ liệu vào : File BL1.INP

* Dòng đầu ghi 3 số M,N,K

* Dòng thứ i trong số k dòng tiếp theo ghi hoành độ và tung độ của nút thứ i trong dãy k nút cần đặt đèn ( i= 1,2,...,k )

Kết quả : Ghi vào File BL1.OUT

* Dòng đầu ghi số lượng màu cần sử dụng p

* Dòng thứ i trong số k dòng tiếp theo ghi màu của đèn ở nút thứ i ( i= 1,2,...,k )

Ví dụ

PHẦN BÀI CHỮA

Bài 1 ( Tìm số vùng liên thông )

Uses Crt;

Const Max = 100;

Fi = 'Lthong.txt';

Fo = 'Lthong.out';

Type MA = Array[1..Max,1..Max] of 0..1;

MD = Array[1..Max] of Byte;

MQ = Array[1..Max*Max] of Byte;

Var A : MA;

D : MD;

Q : MQ;

N,dau,cuoi,sv : Byte;

Procedure DocF;

Var F : Text;

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;

Close(F);

End;

Function Tim : Byte;

Var i : Byte;

Begin

Tim := 0;

For i:=1 to N do

If D[i]=0 then

Begin

Tim := i;

Exit;

End;

End;

Procedure TaoQ_rong;

Begin

FillChar(Q,sizeof(Q),0);

Dau := 0;

Cuoi := 0;

End;

Procedure Loang(i : Byte);

Var j,k : Byte;

Begin

Inc(cuoi);

Q[cuoi] := i;

D[i] := sv;

While (dau+1<=cuoi) do

Begin

Inc(dau);

j := Q[dau];

For k:=1 to N do

If (D[k]=0) and (A[j,k]=1) then

Begin

Inc(cuoi);

Q[cuoi] := k;

D[k] := sv;

End;

End;

End;

Procedure Timstplt;

Var i : Byte;

Ok : Boolean;

Begin

sv := 0;

FillChar(D,sizeof(D),0);

Repeat

TaoQ_rong;

Ok := True;

i := Tim;

If i>0 then

Begin

Inc(sv);

Loang(i);

Ok := False;

End;

Until Ok;

Writeln('So thanh phan lien thong : ',sv);

End;

Procedure GhiF;

Var F : Text;

i,j : Byte;

Begin

Assign(F,Fo);

Rewrite(F);

Writeln(F,'So thanh phan lien thong la : ',sv);

For i:=1 to sv do

Begin

Write(F,'Vung ',i,' : ');

For j:=1 to N do

If D[j]=i then Write(F,j:4);

Writeln(F);

End;

Close(F);

End;

BEGIN

Clrscr;

DocF;

Timstplt;

GhiF;

END.

SVLT.TXT

11

0 1 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0

0 0 1 1 0 1 0 0 0 0 0

0 0 0 0 1 0 1 1 0 0 0

0 0 0 0 0 1 0 0 0 0 0

0 0 0 0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 1 0

SVLT.OUT

So thanh phan lien thong la : 4

Vung 1 : 1 2

Vung 2 : 3 4 5 6 7 8

Vung 3 : 9

Vung 4 : 10 11

Bài 2 ( Tìm số vùng liên thông của các ô số 0 trong hình chữ nhật theo 2 cách : chung cạnh, chung đỉnh )

Uses Crt;

Const Max = 100;

Fi = 'SVLT2.txt';

Fo = 'SVLT2.out';

aDc : Array[1..4] of -1..1 = ( 0 ,1 ,0 ,-1); {so gia cot}

aDd : Array[1..4] of -1..1 = (-1, 0 ,1 , 0); {so gia dong }

bDc : Array[1..8] of -1..1 = ( 0, 1, 1, 1, 0,-1,-1,-1); {so gia cot}

bDd : Array[1..8] of -1..1 = (-1,-1, 0, 1, 1, 1, 0,-1); {so gia dong }

Type KA = Array[1..Max,1..Max] of 0..1;

KD = Array[1..Max,1..Max] of Byte;

KQ = Array[1..Max*Max] of Record d,c : Byte; End;

KDT = Array[1..Max*Max] of Integer;

Var A : KA;

D : KD;

Q : KQ;

DT : KDT;

N,M,i,j,dau,cuoi,sv,cau : Byte;

Procedure DocF;

Var i,j : Byte; F : Text;

Begin

Assign(F,Fi);

Reset(F);

Readln(F,M,N);

For i:=1 to M do

Begin

For j:=1 to N do Read(F,A[i,j]);

Readln(F);

End;

Close(F);

End;

Function Tim(Var i,j : Byte): Boolean;

Var x,y : Byte;

Begin

Tim := False;

For x:=1 to M do

For y:=1 to N do

If (D[x,y]=0) and (A[x,y]=0) then

Begin

i := x;

j := y;

Tim := True;

Exit;

End;

End;

Procedure Q_rong;

Begin

Fillchar(Q,Sizeof(D),0);

Dau := 0;

Cuoi := 0;

End;

Procedure Loang1(i,j : Byte);

Var k,dong,cot,u,v : byte;

Begin

Inc(cuoi);

Q[cuoi].d := i;

Q[cuoi].c := j;

D[i,j] := sv;

While dau+1<=cuoi do

Begin

Inc(dau);

dong := Q[dau].d;

cot := Q[dau].c;

For k:=1 to 4 do

Begin

u := dong + aDd[k];

v := cot + aDc[k];

If (u>0) and (u<=M) and (v>0) and (v<=N) then

If (A[u,v]=0) and (D[u,v]=0) then

Begin

Inc(cuoi);

Q[cuoi].d := u;

Q[cuoi].c := v;

D[u,v] := sv;

Inc(DT[sv]);

End;

End;

End;

End;

Procedure Loang2(i,j : Byte);

Var k,dong,cot,u,v : byte;

Begin

Inc(cuoi);

Q[cuoi].d := i;

Q[cuoi].c := j;

D[i,j] := sv;

While dau+1<=cuoi do

Begin

Inc(dau);

dong := Q[dau].d;

cot := Q[dau].c;

For k:=1 to 8 do

Begin

u := dong + bDd[k];

v := cot + bDc[k];

If (u>0) and (u<=M) and (v>0) and (v<=N) then

If (A[u,v]=0) and (D[u,v]=0) then

Begin

Inc(cuoi);

Q[cuoi].d := u;

Q[cuoi].c := v;

D[u,v] := sv;

Inc(DT[sv]);

End;

End;

End;

End;

Procedure Timsvlt(cau : Byte);

Var Ok : Boolean;

Begin

Sv := 0;

For i:=1 to M*N do DT[i] := 1;

Fillchar(D,sizeof(D),0);

Repeat

Ok := True;

Q_rong;

If Tim(i,j) then

Begin

Inc(sv);

If cau=1 then

Loang1(i,j) Else Loang2(i,j);

Ok := False;

End;

Until Ok;

End;

Procedure HienBandoV;

Var i,j : Byte; F : Text;

Begin

Assign(F,Fo);

Rewrite(F);

For i:=1 to M do

Begin

For j:=1 to N do

If D[i,j]=0 then Write(F,'*':4)

Else Write(F,D[i,j]:4);

Writeln(F);

End;

Writeln(F,'Dien tich tung vung : ');

For i:=1 to sv do Write(F,DT[i]:4);

Close(F);

End;

Procedure Menu;

Var ch : Char;

Begin

Writeln('Go ESC thoat ! ');

Writeln('Chon cau A hay B (A/B) ');

Repeat

Ch := Upcase(Readkey);

If ch=#27 then Exit;

If ch='A' then cau:=1 Else cau:=2;

Timsvlt(cau);

HienBandoV;

Until ch in ['A'..'B',#27]

End;

BEGIN

Clrscr;

DocF;

Menu;

Writeln('Da xong . Moi go Enter va Xem du lieu ra trong File ',Fo);

Readln;

END.

Dũ liệu vào trong File SVLT2.TXT

8 10

0 1 0 0 0 0 0 0 1 0

1 1 0 0 0 0 0 0 1 0

0 0 0 1 1 0 0 0 1 0

1 1 1 0 1 1 0 0 1 0

0 0 1 1 0 0 0 0 1 0

0 0 0 1 1 1 1 1 1 0

1 1 0 1 0 0 0 1 0 1

0 0 0 1 0 0 1 0 1 0

Kết quả câu a) trong SVLT2.OUT

1 * 2 2 2 2 2 2 * 3

* * 2 2 2 2 2 2 * 3

2 2 2 * * 2 2 2 * 3

* * * 4 * * 2 2 * 3

5 5 * * 2 2 2 2 * 3

5 5 5 * * * * * * 3

* * 5 * 6 6 6 * 7 *

5 5 5 * 6 6 * 8 * 9

Dien tich tung vung :

1 24 6 1 9 5 1 1 1

Kết quả câu b) trong SVLT2.OUT

1 * 2 2 2 2 2 2 * 3

* * 2 2 2 2 2 2 * 3

2 2 2 * * 2 2 2 * 3

* * * 2 * * 2 2 * 3

4 4 * * 2 2 2 2 * 3

4 4 4 * * * * * * 3

* * 4 * 3 3 3 * 3 *

4 4 4 * 3 3 * 3 * 3

Dien tich tung vung :

1 25 14 9

Bài 3 :

Uses Crt;

Const MM = 50;

MN = 50;

Fi = 'Input.txt';

Fo = 'Output.txt';

Type KA = Array[1..MM,1..MN] of Byte;

KDT = Array[1..MM*MN] of Integer;

KDD = Array[0..MM+1,0..MN+1] of Integer;

Kpt = Record x,y : Byte; End;

KQ = Array[1..MM*MN] of KPT;

Var A : KA;

DT : KDT;

Q : KQ;

D : KDD;

ch : Char;

M,N,x,y : Byte;

dau,cuoi,sp,dtm : Integer;

Procedure DocF;

Var F : Text;

i,j : Byte;

Begin

Assign(F,Fi);

Reset(f);

Readln(F,M);

Readln(F,N);

For i:=1 to M do

Begin

For j:=1 to N do Read(F,A[i,j]);

Readln(F);

End;

Close(F);

End;

Procedure Q_rong;

Begin

Fillchar(Q,sizeof(Q),0);

dau := 0;

cuoi := 0;

End;

Procedure Lay(var x,y : Byte);

Begin

Inc(dau);

x := Q[dau].x;

y := Q[dau].y;

End;

Procedure Nap(x,y : Byte);

Begin

Inc(cuoi);

Q[cuoi].x := x;

Q[cuoi].y := y;

D[x,y] := sp;

Inc(DT[sp]);

End;

Procedure Loang(x,y : Byte);{ o(x,y) dau tien cua 1 phong moi }

Var i,j : Byte;

Begin

Nap(x,y);

While (dau+1<=cuoi) do

Begin

Lay(x,y);

If (A[x,y] and 1 = 0) and (D[x,y-1]=0) then Nap(x,y-1);

If (A[x,y] and 2 = 0) and (D[x-1,y]=0) then Nap(x-1,y);

If (A[x,y] and 4 = 0) and (D[x,y+1]=0) then Nap(x,y+1);

If (A[x,y] and 8 = 0) and (D[x+1,y]=0) then Nap(x+1,y);

End;

End;

Function Tim(Var x,y : Byte) : Boolean;

Var i,j : Byte;

Begin

Tim := False;

For i:=1 to M do

For j:=1 to N do

If D[i,j]=0 then

Begin

x:=i;

y:=j;

Tim:=true;

Exit;

End;

End;

Procedure Timsophong;

Var i,j : Byte;

Ok : Boolean;

Begin

For i:=0 to M+1 do

For j:=0 to N+1 do D[i,j] := -1;

For i:=1 to M do

For j:=1 to N do D[i,j] := 0;

sp := 0;

Repeat

Ok := True;

If Tim(x,y) then

Begin

Q_rong;

Inc(sp);

Loang(x,y);

Ok := False;

End;

Until Ok;

End;

Procedure Dientich_Max;

Var i : Integer;

Begin

DtM := DT[1];

For i:=2 to sp do

If DT[i]>dtm then dtm := DT[i];

End;

Procedure PhaPhong(Var x,y : Byte; Var ch : Char);

Var i,j : Byte;

phu : Integer;

Begin

phu := 0;

For i:=1 to M-1 do

For j:=1 to N-1 do

Begin

If (D[i,j]<>D[i+1,j]) and (DT[D[i,j]]+DT[D[i+1,j]]>phu) then

Begin

x := i;

y := j;

ch := 'S';

phu := DT[D[i,j]]+DT[D[i+1,j]];

End;

If (D[i,j]<>D[i,j+1]) and (DT[D[i,j]]+DT[D[i,j+1]]>phu) then

Begin

x := i;

y := j;

ch := 'E';

phu := DT[D[i,j]]+DT[D[i,j+1]];

End;

End;

End;

Procedure Lam_GhiF;

Var F : Text;

Begin

Assign(F,Fo);

Rewrite(F);

Timsophong;

Writeln(F,sp);

Dientich_Max;

Writeln(F,dtm);

Phaphong(x,y,ch);

Writeln(F,x,y:3,ch:3);

Close(F);

End;

BEGIN

Clrscr;

DocF;

Lam_GhiF;

END.

INPUT.TXT

5

10

3 10 10 2 10 10 2 10 10 6

1 6 3 4 3 6 1 6 3 4

1 4 1 4 1 4 1 4 1 4

1 12 9 4 9 12 1 12 9 4

9 10 10 8 10 10 8 10 10 12

OUTPUT.TXT

2

44

1 5 S

1 6 S

2 4 E

2 5 N

2 5 W

2 6 E

2 6 N

2 7 W

3 4 E

3 5 W

3 6 E

3 7 W

4 4 E

4 5 S

4 5 W

4 6 E

4 6 S

4 7 W

5 5 N

5 6 N

Bài 4 : (Phủ sóng)

Uses Crt;

Const MN = 12;

Fi = 'Phusong.txt';

Fo = 'Phusong.out';

Di : Array[1..8] of -1..1 = (-1,-1, 0, 1, 1, 1, 0,-1);

Dj : Array[1..8] of -1..1 = ( 0, 1, 1, 1, 0,-1,-1,-1);

Type Ka = Array[1..Mn,1..Mn] of 0..1;

Kpt = Record x,y : Byte; End;

KTram = Array[1..Mn*Mn] of Kpt;

Kddau = Array[1..Mn,1..Mn] of Byte;

Kketqua = Array[0..Mn*Mn] of Byte;

Var A,B : Ka;

T,CP : Ktram;

D : Kddau;

KQ,LKq : Kketqua;

N,st,Luu_bo : Byte;

F2 : Text;

Phutatca : Boolean;

Dabo : Array[1..Mn*Mn] of Boolean;

Procedure DocF;

Var F : Text;

Begin

Assign(F,Fi);

Reset(F);

Readln(F,N);

st := 0;

While not eof(F) do

Begin

Inc(st);

Readln(F,T[st].x,T[st].y);

End;

Close(F);

End;

Procedure Hien(X : KA);

Var i,j : Byte;

Begin

For i:=1 to N do

Begin

For j:=1 to N do Write(F2,A[i,j]:2);

Writeln(F2);

End;

End;

Procedure MoF_out;

Begin

Assign(F2,Fo);

ReWrite(F2);

End;

Procedure CauA;

Var i : Byte;

Begin

Writeln(F2,'CAU A');

Fillchar(A,sizeof(A),0);

For i:=1 to st do A[T[i].x,T[i].y] := 1;

Hien(A);

End;

Procedure CauB;

Var i,j,k : Byte;

Begin

PHUTATCA := False;

Writeln(F2,'CAU B');

B := A;

For i:=1 to N do

For j:=1 to N do

If B[i,j]=1 then

For k:=1 to 8 do

If (i+Di[k]>0) and (j+Dj[k]>0)

and (i+Di[k]<=N) and (j+Dj[k]<=N) then

Inc(A[i+Di[k],j+Dj[k]]);

k := 0;

For i:=1 to N do

For j:=1 to N do

If A[i,j]=0 then

Begin

Inc(k);

CP[k].x := i;

CP[k].y := j;

End;

If k=0 then

Begin

Writeln(F2,1);

PHUTATCA := True;

End

Else

Begin

Writeln(F2,0); {Nhung o chua duoc phu song }

For i:=1 to k do Writeln(F2,CP[i].x:3,CP[i].y:3);

End;

End;

Procedure Giam(i : Byte);

Var k : Byte;

Begin

Dec(A[T[i].x,T[i].y]);

For k:=1 to 8 do Dec(A[T[i].x+Di[k],T[i].y+Dj[k]]);

End;

Procedure Tang(i : Byte);

Var k : Byte;

Begin

Inc(A[T[i].x,T[i].y]);

For k:=1 to 8 do Inc(A[T[i].x+Di[k],T[i].y+Dj[k]]);

End;

Function Boduoc(i : Byte) : Boolean;

Var k,u,v : Byte;

Begin

Boduoc := True;

If A[T[i].x,T[i].y]<=1 then

Begin

Boduoc := False;

Exit;

End;

For k:=1 to 8 do

Begin

u := T[i].x+Di[k];

v := T[i].y+Dj[k];

If (A[u,v]<=1) and (u>0) and (u<=N) and (v>0) and (v<=N)

then

Begin

Boduoc := False;

Exit;

End;

End;

End;

Procedure Try(k : Byte);{ So tram loai bo la k }

Var i : Byte;

Ok : Boolean;

Begin

Ok := False;

For i := 1 to ST do

If Boduoc(i) and (Not Dabo[i]) then

Begin

Giam(i);

KQ[k]:= i;

Dabo[i] := True;

Ok := True;

Try(k+1);

Tang(i);

Dabo[i] := False;

End;

If Not Ok then

If k-1>luu_bo then

Begin

LKQ := KQ;

Luu_bo := k-1;

End;

End;

Procedure CauC;

Var i : Byte;

Begin

Fillchar(Dabo,Sizeof(Dabo),False);

Writeln(F2,'CAU C');

If Not phutatca then

Begin

Writeln(F2,0,' khong phu duoc tat ca ');

End

Else

Begin

Luu_bo := 0;

KQ[0] := 0;

Try(1);

If Luu_bo=0 then Writeln(F2,0)

Else

Begin

Writeln(F2,Luu_bo);

For i:=1 to Luu_bo do

Writeln(F2,T[LKQ[i]].x:3,T[LKQ[i]].y:3);

End;

End;

End;

BEGIN

DocF;

MoF_out;

CauA;

CauB;

CauC;

Close(F2);

END.

PHUSONG.TXT

5

1 1

5 5

2 2

2 4

3 1

3 4

5 2

5 4

PHUSONG.OUT

CAU A

1 0 0 0 0

0 1 0 1 0

1 0 0 1 0

0 0 0 0 0

0 1 0 1 1

CAU B

1

CAU C

4

1 1

5 5

3 1

3 4

Bài 6 : ( Số ổn định trong, ổn định ngoài , tập nhân )

Uses Crt;

Const Max = 100;

Fi = 'OnDinh2.inp';

Fo = 'OnDinh2.out';

Type Mang1 = Array[0..Max] of Integer;

Var A : Mang1;

N,k : Byte;

F,F2 : Text;

G : Array[1..Max,1..Max] of Integer;

Dem,Tong : LongInt;

Procedure DocF;

Var i,j : Byte;

Begin

Assign(F,Fi);

Reset(F);

Readln(F,N);

While Not Eof(F) do

Begin

Read(F,i);

While Not Eoln(F) do

Begin

Read(F,j);

G[i,j] := 1;

G[j,i] := 1;

End;

Readln(F);

End;

Close(F);

End;

Procedure Hien;

Var i : Byte;

Begin

Inc(dem);

For i:=1 to k do

Write(F2,A[i]:4);

Writeln(F2);

End;

Procedure Tao_Trong(i : Byte);

Var j : Byte;

Function KT_Trong (A : Mang1;h : Byte): Boolean;

Var x,y : Byte;

Begin

For x:=1 to h-1 do

For y:= x+1 to h do

If G[A[x],A[y]]=1 then

Begin

Kt_Trong := False;

Exit;

End;

KT_Trong := True;

End;

Begin

If i>k then

Begin

If KT_Trong(A,k) then Inc(Dem){Hien};

End

Else

For j:=A[i-1]+1 to N-k+i do

Begin

A[i] := j;

Tao_Trong(i+1);

End;

End;

Procedure Tao_Ondinhtrong;

Begin

Tong := 0;

For k:=N downto 1 do

Begin

Dem := 0;

FillChar(A,Sizeof(A),0);

A[0] := 0;

Tao_Trong(1);

If Dem>0 then

Begin

Writeln(F2,k);

{ Tong := Tong +Dem;}

Break;

End;

End;

{ Writeln(F2,'Tong cong co ',Tong,' Tap on dinh trong . ');}

End;

Procedure Tao_Ngoai(i : Byte);

Var j : Byte;

Function KT_Ngoai (A : Mang1;h : Byte): Boolean;

Var x,y : Byte;

Function Khongthuoc : Boolean;

Var j : Byte;

Begin

For j:= 1 to h do

If x=A[j] then

Begin

Khongthuoc := False;

Exit;

End;

Khongthuoc := True;

End;

Function CoNoi : Boolean;

Var j : Byte;

Begin

For j:=1 to h do

If G[x,A[j]]=1 then

Begin

CoNoi := True;

Exit;

End;

CoNoi := False;

End;

Begin

For x:=1 to N do

If Khongthuoc then

If Not Conoi then

Begin

Kt_Ngoai := False;

Exit;

End;

KT_Ngoai := True;

End;

Begin

If i>k then

Begin

If KT_Ngoai(A,k) then Inc(Dem); {Hien};

End

Else

For j:=A[i-1]+1 to N-k+i do

Begin

A[i] := j;

Tao_Ngoai(i+1);

End;

End;

Procedure Tao_OndinhNgoai;

Begin

Tong := 0;

For k:=1 to N do

Begin

Dem := 0;

FillChar(A,Sizeof(A),0);

A[0] := 0;

Tao_Ngoai(1);

If Dem>0 then

Begin

Writeln(F2,k);

{Tong := Tong +Dem;}

Break;

End;

End;

{ Writeln(F2,'Tong cong co ',Tong,' Tap on dinh ngoai . ');}

End;

Procedure Vet_Nhan(i : Byte);

Var j : Byte;

Function KT_Trong (A : Mang1;h : Byte): Boolean;

Var x,y : Byte;

Begin

For x:=1 to h-1 do

For y:= x+1 to h do

If G[A[x],A[y]]=1 then

Begin

Kt_Trong := False;

Exit;

End;

KT_Trong := True;

End;

Function KT_Ngoai (A : Mang1;h : Byte): Boolean;

Var x,y : Byte;

Function Khongthuoc : Boolean;

Var j : Byte;

Begin

For j:= 1 to h do

If x=A[j] then

Begin

Khongthuoc := False;

Exit;

End;

Khongthuoc := True;

End;

Function CoNoi : Boolean;

Var j : Byte;

Begin

For j:=1 to h do

If G[x,A[j]]=1 then

Begin

CoNoi := True;

Exit;

End;

CoNoi := False;

End;

Begin

For x:=1 to N do

If Khongthuoc then

If Not Conoi then

Begin

Kt_Ngoai := False;

Exit;

End;

KT_Ngoai := True;

End;

Begin

If i>k then

Begin

If KT_Ngoai(A,k) and KT_Trong(A,k) then Hien;

End

Else

For j:=A[i-1]+1 to N-k+i do

Begin

A[i] := j;

Vet_Nhan(i+1);

End;

End;

Procedure Tao_Nhan;

Begin

Tong := 0;

For k:=1 to N do

Begin

Dem := 0;

FillChar(A,Sizeof(A),0);

A[0] := 0;

Vet_Nhan(1);

If Dem>0 then

Begin

Writeln(F2,Dem,' Tap nhan ',k, ' phan tu .');

{Tong := Tong +Dem;}

Break;{ CHI TIM TAP NHAN IT PHAN TU NHAT }

End;

End;

{ Writeln(F2,'Tong cong co ',Tong,' Tap Nhan . ');}

End;

BEGIN

Clrscr;

DocF;

Assign(F2,Fo);

Rewrite(F2);

Writeln(F2,'************* SO ON DINH TRONG ***********');

Writeln(F2);

Tao_Ondinhtrong;

Writeln(F2);

Writeln(F2,'************* SO ON DINH NGOAI ***********');

Writeln(F2);

Tao_Ondinhngoai;

Writeln(F2);

Writeln(F2,'************* CAC TAP NHAN IT PHAN TU NHAT ***********');

Writeln(F2);

Tao_Nhan;

Close(F2);

END.

Bài 7 : Tô màu

Uses Crt;

Const Max = 20;

Fi = 'Tomau3.inp';

Var A : Array[1..Max,1..Max] of 0..1;

Mau,LMau : Array[1..Max] of Byte;

N,i : Integer;