Phương pháp vét cạn

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]