Tài liệu chuyên Tin 11

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 (A1 ,A 2 , ... A i-1 ,Ai ,..... An-1 ,An ), 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ừ (Ai-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 :
	S1 ³ S2 ³ ..... ³ SN-1 ³ SN ³0 ( Si 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
 A1
 B1
 C1
 D1
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 (sodia0);
 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
 In ...  ) và M nhóm thợ ( mã số từ 1 đến M ) (0<N,M<100).Thuê thợ theo nguyên tắc phải thuê toàn nhóm và sao cho n công việc đều được thực hiện với 2 trường hợp sau :
 	Câu a : Số nhóm thợ phải thuê là ít nhất
 	Câu b : Số thợ thuê là ít nhất
Dữ liệu vào từ File ‘nhomtho.inp’
 	Dòng đầu là 2 số n, m
 	Trong m dòng tiếp theo : số đầu tiên của dòng i trong m dòng nàylà số thợ của nhóm i , các số tiếp theo của dòng là các mã số của các công việc mà nhóm này có thể làm . 
Dữ liệu ra trên màn hình :
Câu a : các mã số là tên các nhóm thợ được thuê trong trường hợp A
Câu b : các mã số là tên các nhóm thợ được thuê trong trường hợp B
Thí dụ :
File ‘nhomtho.inp’
5 5
6 1 3 
5 5 1 2 
9 4 1 5 
9 4 5 2 3 
6 2 5 1 4 
Kết quả trên màn hình là :
Câu A : 1 4 ( hoặc 1 5 )
Câu B : 1 5
Chú ý : Nếu mỗi nhóm thợ không đặc trưng bởi số người , thay bằng giá trị công việc nhóm đó đạt được . Đồng thời mỗi nhóm có thể gọi là 1 " người " thì 
	Bài toán trên có thể thay hình thức phát biểu : Cho M thợ , N công việc , giá công thuê thợ i là B[i] .Nếu A[i,j]=1 thể hiện thợ i làm được công việc j . Hãy thuê thợ để hoàn thành tất cả N công việc trong 2 trường hợp
Câu a : Thuê sao tốn ít tiền nhất , 
Câu b : Thuê sao ít thợ nhất . 
File dữ liệu vào cho như cũ
Bài toán 8 : ( M nhóm thợ , hoàn thành N công việc )
Uses Crt;
Const 	Max 	= 50;
 	Fi 	= 'nhomtho1.INP';
Type 	Ta 	= Array[1..max,1..max] of Byte;
 	Tb 	= Array[1..max] of Byte;
Var 	N,M,LN,LT,Sn,St 	: Byte;
 	A 	: Ta;
 	B,KqA,KqB,Kq,phu : Tb;
 	Thcv 	: Set of Byte;
Procedure TaoF;
 Var 	f 	: Text;
 	k,p,i,j 	: Byte;
 	TH 	: Set of Byte;
 Begin
 Assign(f,fi);
 Rewrite(f);
 Write('So cong viec n = ');Readln(n);
 Write('So nhom tho m = ');Readln(m);
 Writeln(f,n,' ',m);
 Randomize;
 For i:=1 to m do
 Begin
 Write(f,Random(10)+1,' ');
 TH := [];
 For j:=1 to n do
 Begin
 k := Random(n)+1;
 If Not (k in TH) then
 Begin
 TH := TH+[k];
 Write(f,k,' ');
 End;
 End;
 Writeln(f);
 End;
 Close(f);
 End;
Procedure Nhap;
 Var 	f 	: Text;
 	i,j 	: Byte;
 Begin
 Assign(f,Fi); {$i-} Reset(f); {$i+}
 If (ioresult0) then
 Begin
 Write('Error file data ',fi,' .Enter to quit');
 Readln; halt;
 End;
 Readln(f,n,m);
 For i:=1 to m do
 Begin
 Read(f,B[i]);
 While not Seekeoln(f) do
 Begin
 Read(f,j);
 A[i,j] := 1;
 End;
 Readln(f);
 End;
 Close(f);
 End;
Function Dk_Can:Boolean;{= False : Có công việc không thể thuê nhóm nào làm được}
 Var 	i,j : Byte;
 Function Cot_0(j:Byte):Boolean;{True: c/v j không nhóm nào làm được (cột j là cột 0)}
 	Var i : Byte;
 	Begin
 	Cot_0 := False;
 	For i:=1 to m do
 	If a[i,j]0 then Exit;
 	Cot_0 := True;
 	End;
 Begin
 Dk_Can := False;
 For j:=1 to n do
 If Cot_0(j) then Exit;
 Dk_Can := True;
 End;
Procedure Toiuu;
 Begin
 If (sn<Ln) then
 Begin
 Ln:=sn;
 KqA:=Kq;
 End;
 If (st<Lt) then
 Begin
 Lt:=st;
 KqB:=Kq;
 End;
 End;
Procedure Them_nhom(i:Byte);
 Var j : Byte;
 Begin
 For j:=1 to n do
 If a[i,j]=1 then
 Begin
 Inc(Phu[j]); {So tho lam cong viec j }
 Thcv:=thcv+[j];
 End;
 Inc(sn);
 Inc(st,b[i]);
 End;
Procedure Loai_nhom(i:Byte);
 Var j : Byte;
 Begin
 For j:=1 to n do
 If (A[i,j]=1) then
 Begin
 Dec(Phu[j]);{Phu[j] : so tho biet cv j cua cac nhom da thue }
 {Thcv : tap hop cac cong viec thue}
 If (Phu[j]=0) then Thcv:=Thcv-[j];
 End;
 Dec(sn);
 Dec(st,b[i]);
 End;
Function Chapnhan(i:Byte):Boolean;{True : Nhom i co kha nang lam cv chua co ai lam}
 Var 	j : Byte;
 Begin
 Chapnhan := True;
 For j:=1 to n do
 If (A[i,j]=1) and Not (j in Thcv) then Exit;
 Chapnhan := False;
 End;
Procedure Vet(i:Byte);
 Begin
 If (Thcv=[1..n]) then
 Begin
 Toiuu;
 Exit;
 End;
 If ((Sn>=Ln) and (St>=Lt)) or (i=m+1) then Exit;
 If Chapnhan(i) then
 { Nhom i lam duoc cong viec ma nhom tho da tuyen khong the lam duoc}
 Begin
 Them_nhom(i);
 Kq[i]:=1;
 Vet(i+1);
 Loai_nhom(i);
 Kq[i]:=0;
 End;
 Vet(i+1);
 End;
Procedure Khoitri;
 Var 	i : Byte;
 Begin
 Ln:=Max+1;
 Lt:=Max+1;
 St:=0;
 sn:=0;
 Thcv:=[];
 For i:=1 to n do Phu[i]:=0;
 End;
Procedure Hienkq;
 Var i : Byte;
 Begin
 Writeln('Dang chay chuong trinh ... ');
 Write('Phuong an thue it nhom nhat la : ');
 For i:=1 to n do
 If KqA[i]=1 then Write(i:4);
 Write(#10#13,'Phuong an thue it tho nhat la : ');
 For i:=1 to n do
 If KqB[i]=1 then Write(i:4);
 Writeln(#10#13,'Chuong trinh da chay xong ! ');
 End;
Procedure Xuly;
 Begin
 If Not Dk_Can then
 Begin
 Writeln('Khong ton tai phuong an thue .Enter de thoat');
 Readln;
 Halt;
 End;
 Khoitri;
 Vet(1);
 End;
BEGIN
 Clrscr;
 {TaoF;}
 Nhap;
 Xuly;
 Hienkq;
 Readln;
END.
Bài 9 : ( Bài thi Tin học quốc gia 1995 ) 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ị nguiyên không âm ) . Với mỗ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 gfhi trên một 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 ít nhất 1 dấu cách
Cần chọn ra k vận động viên và k môn để thành lập đội tuyển thi đấu Olympic quốc tế , trong đó mỗi vận động viên chỉ được thi đấu đúng 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 cho 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ạng 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 một giá trị k ta nhận được :
k=1 , máy trả lời 
	(2,2)
	Tổng số điểm = 7 
k=2 , máy trả lời 
	(2,1) (3,2)
	Tổng số điểm = 11 
k=3 , máy trả lời 
	(1,2) (2,1) (3,3) 
	Tổng số điểm = 13 
	K=0 Kết thúc
{$A+,B-,D+,E+,F-,I+,L+,N-,O-,R-,S+,V-}
{$M 16384,0,655360}
Program BL3;
 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 and (tf'');
 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.
Bài 9 : Cho M vận động viên , N môn thể thao . Vận động viên i đấu môn j được số điểm là Di j . Cần chọn K vận động viên thi đấu k môn ( mỗi vận động viên chỉ thi đúng 1 môn ) Nêu rõ cần chọn K vận động viên nào và những vận động viên ấy mỗi người thi đấu môn nào ? 
Uses Crt;
Const 	Max 	= 100;
 	Fi 	= 'Tongk.txt';
 	Fo 	= '';
Type Pt = Record d,c,gt : Byte; End;
 M1 	= Array[1..Max*Max+1] of Pt;
 	M2 	= Array[1..Max] of Record d,c :Byte;End;
Var B,LB 	: M1;
	M,N,k 	: Byte;
 Dx,Kq,Lkq : M2;
 	Tong,LTong,csMax : LongInt;
Procedure DocF;
 Var 	i,j 	: Byte;
 F 	: Text;
 Begin
 Assign(F,Fi);
 {$I-} Reset(F); {$I+}
 If IoResult0 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].gt);
 B[(i-1)*N+j].d := i;
 B[(i-1)*N+j].c := j;
 End;
 Readln(F);
 End;
 Close(F);
	 LB := B;
 CsMax := M*N;
 End;
Procedure Sapxep_dl; {Sap giam dan }
 Procedure Quick(dau,cuoi : LongInt);
 Var 	i,j,L : LongInt;
 phu : Pt;
 Begin
 i := dau;
 j := cuoi;
 L := (i+j) div 2;
 Repeat
 	 While B[i].gt>B[L].gt do Inc(i);
 	 While B[j].gt<B[L].gt do Dec(j);
 	 If i<=j then
 	 Begin
 	 phu := B[i];
 	 B[i] := B[j];
 	 B[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(Dx,Sizeof(Dx),False);
 FillChar(Kq,Sizeof(Kq),0);
	 Tong := 0;
 Ltong := 0;
 End;
Procedure GhiToiuu;
 Begin
 Lkq := kq;
 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,L,p,cL,Luu : LongInt;
 Begin
 cL := k-i; { cl : con lai }
 Delta := Tong-LTong;
 If cL<0 then
 Begin
 	If Delta>=0 then GhiToiuu;
 End
 Else
 Begin
 	L := j-1;
 	Repeat
 	 Inc(L);
 d1 := B[L].d;
 c1 := B[L].c;
 	Until (L> Csmax) or ((Dx[d1].d=0) and (Dx[c1].c=0));
 	If L<= csMax then
 If B[L].gt+B[L+1].gt*cL+Delta>0 then
 For p := L to csMax-1 do
 Begin
 d1 := B[p].d;
 c1 := B[p].c;
 If (B[p].gt+B[p+1].gt*cL+Delta>0) and
 	(Dx[d1].d=0) and (Dx[c1].c=0) then
 Begin
 Dx[d1].d := 1;
 Dx[c1].c := 1;
 Luu := Tong;
 Tong := Tong+B[p].gt;
 Kq[i].d := d1;
 Kq[i].c := c1;
 Chon(i+1,p+1);
 Dx[d1].d := 0;
 Dx[c1].c := 0;
 Tong := Luu;
 Kq[i].d := 0;
 Kq[i].c := 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,Lkq[i].d:2,' ',Lkq[i].c:2,' = ',
 LB[(Lkq[i].d-1)*N+Lkq[i].c].gt);
 Close(F);
 End;
BEGIN
 Clrscr;
 Khoitri;
 DocF;
 Sapxep_dl;
 Chon(1,1);
 Inkq;
END.