Tài liệu Chuyên đề vét cạn thử sai

CHUYÊN ĐỀ: PHƯƠNG PHÁP THỬ SAI (Duyệt - Vét cạn). 1. Bài toán về phương pháp thử - sai: Trong một số bài toán việc tìm nghiệm có thể qui về việc tìm vector hữu hạn (x1,x2,…,xn). Trong đó n có thể xác định trước hoặc không xác định trước. Vector cần tìm phải thỏa mãn điều kiện nào đó tùy thuộc vào từng bài toán cụ thể. Trong đó các thành phần xi được chọn ra từ tập Ai. Phương pháp: - Lần lượt liệt kê tất cả các khả năng của nghiệm (Gọi là phần thử - duyệt). - Với mỗi vector nghiệm ta kiểm tra xem nghiệm đó của thỏa mãn điều kiện của đầu bài hay không,…. (Phần sai) Ví dụ 1: Cho dãy số nguyên a1,a2,…,an ( ai <=109) và một số nguyên dương S (S<=109), thực hiện các yêu cầu sau: a) Đếm số lượng dãy con liên tiếp của dãy A có số phần tử lớn hơn 3 và có tổng bằng S b) Chọn 3 phần tử trong dãy mà tích của ba phần tử là lớn nhất. c) Liệt kê tất cả các cách chọn một tập gồm các số trong dãy để tổng các số trong tập được chọn bằng S Phân tích ví dụ: a) Vector nghiệm là (i,j) (Trong đó 1<=i Chi phí duyệt O(n3); Chi phí kiểm tra là O(1) => Độ phức tạp của thuật toán là O(n3) c) Vector nghiệm là (x1,x2,…,xn). Trong đó xi=1 nếu ai được chọn và ngược lại. Ta phải dùng đệ qui để duyệt các dãy nhị phân độ dài n, với mỗi dãy nhị phân ta tính tổng và kiểm tra S. *. Nhận xét: Ta thấy rằng độ phức tạp của 3 thuật toán trên là quá lớn: - Thuật toán của ý a và b là O(n3) chỉ giải quyết được với n<=400 - Thuật toán của ý c là thuật toán đệ qui giải quyết được với n<=20 Vậy có cách tiếp cận nào để giải quyết bài toán: 2. Giải bài toán bằng chiến lược thử sai: - Đoán nhận vector nghiệm: Phải xác định nghiệm gồm bao nhiêu thành phần, miền giá trị của từng thành phần và các rằng buộc giữa các thành phần. Đây là công việc quan trọng mang ý nghĩa quyết định đến việc giải quyết bài toán. - Viết thuật toán, mịn dần thuật toán. - Tối ưu thuật toán: Ta có thể tối ưu thuật toán bằng cách giảm thiểu số trường hợp phải thử (Giảm thiểu thủ tục Thử) hoặc ta có thể giảm chi phí phần kiểm tra (Giảm phần Sai) hoặc ta có thể giảm cả 2 phần. 3. Bài tập áp dụng: Bài 1a) Cho dãy số nguyên a1,a2,…,an ( ai <=109; n<=105) và một số nguyên dương S (S<=109). Đếm số lượng dãy con liên tiếp của dãy a1,a2,…,an có số phần tử lớn hơn 3 và có tổng bằng S. *) Thuật toán 1: Function Var kiemtra(i,j:longint):Boolean; sum:int64; k:longint; Begin Sum:=0; For k:= i to j do sum:=sum+a[k]; Exit(sum=S); End; **************** Procedure try; Var i,j:longint; Begin Count:=0; For i:= 1 to n -3 do For j:= i+3 to n do do If kiemtra(i,j) then inc(count); End; Nhận xét: Với thuật toán trên thì độ phức tạp là O(n3) nên chỉ chạy được với n<=400. *). Thuật toán 2: Cài tiến việc kiểm tra từ O(n) về O(1). - Ta tính toán tổng tất cả các phần tử a[i] đến a[j]. Như vậy khi kiểm tra chỉ việc lấy ra chứ không phải tính toán nữa. Gọi mảng L là mảng một chiều mà L[i] là tổng các phần tử từ phần tử 1 đến phần tử thứ i. Procedure chuanbi; Var i:longint; Begin Fillchar(L,sizeof(L),0); For i:= 1 to n do L[i]:=L[i-1]+a[i]; End: **************** Function Begin kiemtra(i,j:longint):Boolean; Exit(L[j]-L[i-1]=S); End; **************** Procedure try; Var i,j:longint; Begin Count:=0; For i:= 1 to n -3 do For j:= i+3 to n do do If kiemtra(i,j) then inc(count); End; Nhận xét: - Với thuật toán trên do ta tính trước được tổng cấc phần từ tử a[i] đến a[j] nên với mỗi lần duyệt ở thủ tục Try thì ta chỉ cần lấy kết quả ra để kiểm tra => Độ phức tạp của thuật toán là O(n2). Với độ phức tạp này ta có thể chạy được với n<=5000. (Ta cũng có thể làm bằng cách tính tổng cộng dồn sau mỗi khi tăng j) *. Thuật toán 3: Ta tối ưu thuật toán ở phần thử (Phần duyệt). - Với mỗi phần tử thứ i: Ta tìm kiếm xem có bao nhiêu chỉ số j mà (j>i+3, L[i-1] + S =L[j]) - Việc tìm j thỏa mãn điều kiện trên ta có thể tìm bằng thuật toán tìm kiếm nhị phân với độ phức tạp là O(log n). - Để tìm kiếm được ta phải sắp xếp tăng dần mảng Q (Chính là mảng L nhưng có thêm phần chỉ số). Cụ thể ta làm như sau: - Tính mảng L - Độ phức tạp O(n). - Tính mảng Q. For i:= 1 to n do Begin Q[i].GT:=L[i]; Q[i].CS:=i; End; - Sắp xếp (Quicksort) mảng Q theo trường GT - Độ Phức tạp O(nlogn) - Duyệt: Với mỗi i ta tìm Q[j] mà Q[j].GT = S + L[i-1] và Q[i].CS>i+3. Như vậy: Với thuật toán này thì phần duyệt có độ phức tạp là O(n) còn phẩn kiemtra có chi phí là O(logn) => Toàn thuật toán có chi phí là O(nlogn) => Có thể chạy được với n<=105). Muốn viết được thuật toán trên ta phải viết được thuật toán tìm kiếm nhị phân và thuật sắp xếp quicksort: *. Thuật toán tìm kiếm nhị phân: Function Nhiphan(L,H:Longint):Longint; Var Dau,Cuoi,Giua;Longint; Begin Dau:=L; Cuoi:=H; Giua:=(Dau+Cuoi) Div 2; While (a[Giua]<>K ) and (Dau<=Cuoi) do Begin If A[giua]>K then Cuoi:=giua-1 Else Dau:=Giua+1; Giua:=(Dau+Cuoi) Div 2; End; If a[giua]=K then Exit(Giua) else Exit (0); End; *. Thuật toán sắp xếp nhanh (Quicksort). Procedure Quicksort(L,H:Longint); Var i,j:Longint; x,tg:Longint; Begin i:=L; j:=H; x:=a[(L+H) Div 2]; Repeat While a[i].keyx.key do dec(j); If i<=j then Begin Đỗi chỗ a[i] và a[j] Inc(i); Dec(j); End; Until i>j; If Ly.gt then Exit (1) Else Exit(-1); End; Procedure Quicksort(L,H:Longint); Var i,j:Longint; x,tg:Longint; Begin i:=L; j:=H; x:=a[(L+H) Div 2]; Repeat While a[i].keyx.key do dec(j); If i<=j then Begin Đỗi chỗ a[i] và a[j] Inc(i); Dec(j); End; Until i>j; If Li+3. Như vậy: Với thuật toán này thì phần duyệt có độ phức tạp là O(n) còn phẩn kiemtra có chi phí là O(logn) => Toàn thuật toán có chi phí là O(nlogn) => Cos thể chạy được với n<=105). Kết luận: Phương pháp Thử - Sai thực chất là duyệt tất cả các khả năng có thể là nghiệm của bài toán: - Phần duyệt: Có thể duyệt bằng các trường hợp sau: +. Dùng vòng lặp. + Sinh tuần tự các véc tơ. +. Dùng đệ qui,… - Phần kiểm tra. HỆ THỐNG CÁC BÀI TẬP VỀ DUYỆT Bài 1: ESEQ Cho dãy số nguyên A gồm N phần tử A1, A2, .., AN, tìm số cặp chỉ số i, j thỏa mãn: i  p 1 Ap  N  q j Aq với 1 ≤ i < j ≤ N Dữ liệu vào trong file “ESEQ.INP” có dạng: - Dòng đầu là số nguyên dương N (2 ≤ N ≤ 105) - Dòng tiếp theo chứa N số nguyên A1, A2, .., AN (|Ai|<109), các số cách nhau một dấu cách. Kết quả ra file “ESEQ.OUT” có dạng: gồm một số là số cặp tìm được. ESEQ.INP 3 101 ESEQ.OUT 3 Ý tưởng: - Duyệt i,j: Với i là phần tử cuối cùng của đoạn 1 và j là phần tử đầu tiên của đoạn 2. - Với mỗi i,j ta tìm tổng của đoạn 1 va tổng của đoạn 2. mất O(n). => Độ phức tạp của cả thuật toán là O(n3). Mã code như sau: For i:=1 to n-1 do For j:=i+1 to n do Begin S1:=0; For k:=1 to i do S1:=S1+a[k]; S2:=0; For k:=j to n do S2:=S2+a[k]; If S1=S2 then inc(kq); End; Cải tiến 1: ta cải tiến phần kiểm tra từ O(n) về O(1) Bằng cách tính trước mảng cộng dồn. - Gọi mảng L. Trong đó L[i] là tổng các phần tử từ phần tử 1 đến phần từ i. - Gọi mảng R. Trong đó L[j] là tổng các phần tử từ phần tử j đến phần từ n. Thuật toán trên trở thành. For i:=1 to n-1 do For j:=i+1 to n do Begin If L[i]=R[j] then inc(kq); End; Cải tiến 2: Cải tiến phần duyệt. Với mỗi i Ta tìm kiếm nhị phân trên mảng R=L[i]. Để đếm được có bao nhiêu R[j]=L[i] ta phải sắp xếp mảng R theo giá trị đồng thời cũng phải lưu chỉ số ban đầu để kiểm tra thỏa mãn điều kiện (ix do Dec(j); if i<=j then Begin tg:=sp[i]; sp[i]:=sp[j]; sp[j]:=tg; inc(i); dec(j); end; until i>j; if il then quicksort(l,j); end; Function Lan(k,l:longint):longint; Var tg,l1:longint; Begin tg:=0; l1:=l; While (l1>0) and (sp[l1].gt=st[k]) do Begin if sp[l1].cs>k then tg:=tg+1; Dec(l1); end; l1:=l+1; While (l1<=n) and (sp[l1].gt=st[k]) do Begin if sp[l1].cs>k then tg:=tg+1; inc(l1); end; Exit(tg); end; Function tknp(k:longint):longint; Var dau,cuoi,giua:longint; Begin dau:=1; cuoi:=n; while (dau<=cuoi) do Begin giua:=(dau+cuoi) Div 2; if sp[giua].gt=st[k] then exit(giua); if sp[giua].gt0 then Kq:=kq+Lan(i,tg); end; end; Procedure ghikq; Var f:text; Begin Assign(f,fo); rewrite(f); Write(f,kq); Close(f); end; BEGIN Docdl; quicksort(1,n); Xuli; Ghikq; END. Lưu ý: - Phải có hàm Lan sang hai bên vì điều kiện đầu bài ix do dec(j); if i<=j then Begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; inc(i); Dec(j); end; until i>j; if il then quicksort(l,j); end; Function lan(l,k:longint):longint; Var kq1:longint; l1:longint; Begin if k=0 then exit(0); kq1:=0; l1:=k; While (l1>l) and (a[l1]=a[k]) do Begin inc(kq1); dec(l1); end; l1:=K+1; While (l1<=n) and (a[l1]=a[k]) do Begin inc(kq1); inc(l1); end; Exit(kq1); end; Function tknp(l,h,x:longint):longint; Var dau,cuoi,giua:longint; Begin Dau:=l; cuoi:=h; While dau<=cuoi do Begin giua:=(dau+cuoi) div 2; if a[giua]=x then exit(giua); if a[giua]0 then kq:=kq+lan(i,kq1); end; end; procedure ghikq; Var f:text; Begin Assign(f,fo); rewrite(f); Write(f,kq); Close(f); end; BEGIN Docdl; Quicksort(1,n); Xuli; Ghikq; END. LẬT XU Có 16 đồồng xu xếếp thành bảng 4x4, mồỗi đồồng xu có th ể úp hoặc ngửa như hình vẽỗ sau: Mầồu đẽn thể hiện đồồng xu úp, màu trắếng thể hiện đồồng xu ngửa. Tại mồỗi bước ta có phép biếến đổi sau: Chọn một đồồng xu và thay đổi trạng thái của ồ đó và tầết c ả các ồ chung cạnh (úp thành ngửa, ngửa thành úp). Cho trước một trạng thái các đồồng xu, hãy l ập trình tm sồế phép biếến đổi ít nhầết để đưa vếồ trạng thái tầết cả các đồồng xu hoặc đếồu úp hoặc đếồu ngửa. Input  Gồồm 4 dòng, mồỗi dòng 4 ký tự ‘w’ - mồ tả trạng thái ngửa hoặc ‘b’- mồ tả trạng thái úp. Output  Nếếu có thể biếến đổi được ghi sồế phép biếến đổi ít nhầết nếếu khồng ghi -1 latxu.inp bwbw wwww bbwb bwwb latxu.out -1 latxu.inp bwwb bbwb bwwb bwww const fi='Latxu.inp'; fo='Latxu.out'; Type mang=array[0..5,0..5] of longint; Var A,x:mang; kq:longint; Procedure docdl; Var i,j:longint; ch:char; f:text; Begin assign(f,fi); Reset(f); Fillchar(a,sizeof(a),0); For i:=1 to 4 do Begin For j:=1 to 4 do Begin Read(f,ch); if ch='b' then a[i,j]:=0 else a[i,j]:=1; end; readln(f); end; Close(f); end; Function kiemtra(B:mang):boolean; Var i,j,dem:longint; Begin For i:=1 to 4 do latxu.out 4 For j:=1 to 4 do if x[i,j]=1 then Begin B[i,j]:=(B[i,j]+1) mod 2; B[i-1,j]:=(B[i-1,j]+1) mod 2; B[i+1,j]:=(B[i+1,j] +1) mod 2; B[i,j-1]:=(B[i,j-1]+1) mod 2; B[i,j+1]:=(B[i,j+1]+1) mod 2; end; dem:=0; For i:=1 to 4 do For j:=1 to 4 do if B[i,j]=0 then inc(dem); Exit((dem=0) or (dem=16)); End; Function dem:longint; Var i,j,s:longint; Begin s:=0; For i:=1 to 4 do For j:=1 to 4 do if x[i,j]=1 then inc(s); exit(s); end; Procedure xulikq; var i,j:longint; Begin if kiemtra(A) then if dem Ta dùng hai biên chỉ số i, j chạy từ hai đầu về. Chương trình mẫu: {$M 64000000,0} {$MODE OBJFBC} {$INLINE ON} {$H-,I+,Q+,R+,S+} Const InputFile = 'PSEQ.INP'; OutputFile = 'PSEQ.OUT'; max = 15000; Type Arr1Int = array[1..max] of Integer; Var a : Arr1Int; n, m, First, kk : Integer; { ======================================================== } Procedure Enter; Var fi : text; i : Integer; Begin Assign(fi, InputFile); Reset(fi); Read(fi, n, m); For i := 1 to n do Read(fi, a[i]); Close(fi); End; { ================================================== } Procedure Swap(Var x, y : Integer); Var Temp : Integer; Begin Temp := x; x := y; y := Temp; End; { =============================================== } Procedure Sort(L, H : Integer); Var i, j, key : Integer; Begin If L >= H then Exit; i := L; j := H; key := a[L + Random(H - L + 1)]; Repeat While a[i] < key do Inc(i); While a[j] > key do Dec(j); If i <= j then Begin If i < j then Swap(a[i], a[j]); Inc(i); Dec(j); End; Until i > j; Sort(L, j); Sort(i, H); End; { ========================================= } Procedure Test; Var i : Integer; Begin First := 1; For i := n downto 1 do If i <= First then Break Else If a[i] + a[First] <= m then Begin Inc(kk); Inc(First); End Else If a[i] <= m then Inc(kk) Else Begin kk := 0; Break; End; End; { =================================================== } Procedure Process; Begin kk := 0; If n = 1 then Begin If a[n] <= m then kk := 1; End Else Test; End; { ========================================================= } Procedure PrintResult; Var fo : text; Begin Assign(fo, OutputFile); Rewrite(fo); Writeln(fo, kk); Close(fo); End; { =========================================================== } Begin Enter; Sort(1, n); Process; PrintResult; End. COUNTING Cho đoạn số nguyên [a, b] 0 - Xem thêm -