Tin học - Phương pháp vét cạn toàn bộ

Phương pháp vét cạn toàn bộ.
Muốn tìm được cây kim trong đống rơm, hãy lần lượt rút từng cọng rơm cho đến khi rút được cây kim
Mô tả tuật toán:
Gọi D là không gian của bài toán (tập tất cả các khả năng có thể xảy ra của bài toán)
D = tập tất cả các bộ (x1, x2, , xn)
Trong đó:
X1 Î D1
X2 Î D2
Xn Î Dn
Và Di là các tập hữu hạn có số phần tử mi
Gọi quy tắc xác định lời giải là một ánh xạ f
f : D à {True, False}
Để tìm kiếm lời giải bài toán ta lần lượt xét tất cả các phần tử của tập D, nếu phần tử x=(x1,x2,, xn) thỏa f(X)= True thì X là một lời giải của bài toán
Coloigiai:=false;
For " x1 Î D1 do
For " x2 Î D2 do
.
For " xn Î Dn do
If f(x1,x2,..,xn)=True then 
	begin
	 là 1 lời giải
	coloigiai:=true
	end;
If coloigiai= False then 
VD1. Vừa gà vừa chó 36 con, bó lại cho tròn 100 chân chẵn. Tìm số gà, số chó mỗi loại?
HD. Ta có D = D1 x D2
D1: tập các giá trị mà số gà có thể nhận 	D1=[1..36] à ga
D2: tập các giá trị mà số chó có thể nhận 	D2=[1..25] à cho
Điều kiện nhận kết quả
	Đk1: ga+cho =36 
	Đk2: ga x 2 + cho x 4 =100
Code tham khảo
var ga, cho:byte;
begin
for ga:=1 to 36 do
for cho:=1 to 25 do
if (ga+cho=36) and (ga*2+cho*4=100) 	then write(ga:4,cho:4);
readln
end.
VD2. LỚP HỌC MÚA 
Lớp học múa khiêu vũ dạ hội của giáo sư Padegras có n học sinh nam và nữ ghi tên. Giáo sư cho tất cả học sinh xếp thành một hàng dọc và chọn một nhóm các học sinh liên tiếp nhau cho buổi học đầu tiên với yêu cầu là số học sinh nam và nữ phải bằng nhau.
Hãy xác định, giáo sư Padegras có bao nhiêu cách lựa chọn khác nhau cho buổi học đầu tiên.
Dữ liệu: Vào từ file văn bản DANCE.INP:
Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 106),
Dòng thứ 2 chứa xâu độ dài n bao gồm các ký tự từ tập {a, b} xác định dòng xếp hàng, a là nam, b – nữ.
Kết quả: Đưa ra file văn bản DANCE.OUT một số nguyên – số cách lựa chọn.
Ví dụ:
DANCE.INP	DANCE.OUT
8
abbababa	13
Kiểm tra các xâu con k ký tự liên tiếp nhau, với k = 2 ÷ n.
Phát biểu lại bài toán: Đếm xem có bao nhiêu xâu con có số kí tự a bằng số kí tự b
function compare(st:string):boolean;
var x,y,j:integer;ss:boolean;
begin
x:=0;y:=0;
for j:=1 to length(st) do
begin
	if st[j]='a' then inc(x);
	if st[j]='b' then inc(y);
end;
if x=y then ss:=true else ss:=false;
compare:=ss;
end;
Code tham khảo
procedure xuly;
begin
k:=0;
repeat
k:=k+1;
for i:=1 to n-k+1 do
for j:=i+k-1 to n do
if compare(copy(s,i,j-i+1)) then inc(dem);
until k<=n;
end;
BÀI TẬP:
Bài 1: Nhập vào dãy n số nguyên dương
Yêu cầu:
Sắp dãy số không tăng
In ra các cặp số nguyên tố song sinh (số nguyên tố song sinh là các cặp số nguyên tố có hiệu bằng 2
Vd. 12 3 4 5 7 120 12 14 15
120 15 14 12 7 5 4 3 
Co cac cap so nguyen to song sinh la: 
7 va 5
5 va 3
Code tham khảo
procedure sapxep;
var tam:integer;
begin
 for i:=1 to n-1 do
 for j:=i+1 to n do
 if a[i]<a[j] then
 begin
 tam:=a[i];
 a[i]:=a[j];
 a[j]:=tam;
 end;
end;
Function ktnt(n:integer):boolean;
Var kt:boolean;
	j:integer;
Begin
	kt:=true;
	for j:=2 to n div 2 do
	if n mod j=0 then kt:=false;
	ktnt:=kt;
End;
Code tham khảo
procedure xuly;
begin
 for i:=1 to n-1 do
	for j:=i+1 to n do
 if ktnt(a[i]) and ktnt(a[j]) and (a[i]-a[j]=2) then
 writeln(a[i],' va ',a[j]);
end;
BÀI 2: Mật khẩu
Một xâu kí tự được gọi là mật khẩu “an toàn” nếu xâu có độ dài ít nhất 6 kí tự và xâu chứa ít nhất một chữ cái in hoa (‘A’ .. ‘Z’), một chữ cái in thường (‘a’..’z’), một chữ số (‘0’..’9’).
Ví dụ, ‘a1B2c3’, ‘tinHoc6’ là các mật khẩu an toàn, ‘tinhoc’, ‘a1B2c’ là các mật khẩu không an toàn.
Yêu cầu: Cho xâu S, tính số lượng xâu con là mật khẩu an toàn
Dữ liệu vào: File xau.inp gồm một dòng chứa xâu S
Kết quả: Xuất ra file matkhau.out mọt số nguyên là số lượng xâu con là mật khẩu an toàn.
Code tham khảo
procedure try;
var x1,x2,n:longint;
begin
 n:=length(s);
 count:=0;
 for x1:=1 to n do
 for x2:=1 to n do
 if isOK(x1,x2) then count:=count+1;
end;
----------
function isOK(x1,x2:longint):boolean;
begin
 isOK:=(x2-x1>=5)
 and (checkHAZ(x1,x2))
 and (checkLaz(x1,x2))
 and (check09(x1,x2));
end;
----------------
function check09(x1,x2:longint):boolean;
var i:integer;
 kt:boolean;
begin
 kt:=false;
 for i:=x1 to x2 do
 if (s[i]>='0') and (s[i]<='9') then kt:=true;
 check09:=kt
end;
--------
function checkHAZ(x1,x2:longint):boolean;
var i:integer; kt:boolean;
begin
 kt:=false;
 for i:=x1 to x2 do
 if (s[i]>='A') and (s[i]<='Z') then kt:=true;
 checkHAZ:=kt;
end;
function checklaz(x1,x2:longint):boolean;
var i:integer; kt:boolean;
begin
 kt:=false;
 for i:=x1 to x2 do
 if (s[i]>='a') and (s[i]<='z') then kt:=true;
 checkLaz:=kt;
end;
Bài 3: Đếm tàu 
	Một tệp văn bản có tên fn có ghi sơ đồ một vùng biển hình chữ nhật chiều ngang 250 kí tự, chiều dọc (số dòng) không hạn chế. Trên biển có các con tàu hình chữ nhật chứa các kí tự 1, vùng nước được biểu thị qua các kí tự 0. Biết rằng các con tàu không dính nhau. Hãy đếm số lượng tàu. 
Ví dụ, hình bên có 4  tàu.
5 6
0 0 0 0 0 0
0 1 1 0 0 1
0 0 0 0 0 1
0 1 1 0 0 0
0 0 0 0 1 1
Hướng dẫn giải:
Nhận xét:
Để đếm số tàu ta chỉ cần đếm các mũi tàu (nghĩa là ô trên cùng bên trái của tàu là đủ vì tàu là các khối hình chữ nhật số 1).
Bài toán có thể phát biểu lại: đếm các ô (i,j) mà giá trị a[i,j]=1 và a[i-1,j]=0 và a[I,j-1]=0
Code tham khảo
procedure xuly;
begin
 dem:=0;
 for i:=1 to n do
 for j:=1 to m do
 if (a[i,j]=1) and (a[i-1,j]=0) and (a[i,j-1]=0) then inc(dem);
end;