Tài liệu Tin học_chuyên đề duyệt bằng vòng lặp

CHUYÊN ĐỀ: DUYỆT BẰNG VÒNG LẶP: CỔ ĐIỂN NHƯNG HIỆU QUẢ 1. Bài toán duyệt bằng vòng lặp: Có thể nói duyệt bằng vòng lặp là chiến thuật hay gặp nhất trong lập trình, từ những người mới học lập trình đến nhưng chuyên gia đều thường xuyên phải sử dụng đến nó. Trong các kỳ thi học sinh giỏi quốc gia và học sinh giỏi quốc tế luôn có nhứng bài yêu cầu thí sinh làm bằng duyệt vòng lặp. Hiện nay một số học sinh, sinh viên vẫn hay gọi nó là duyệt bằng “trâu – bò”. Từ cái tên của chiến thuật đã thể hiện rõ: Duyệt tất cả các nghiệm của bài toán bằng các vòng lặp. Mặc dù chiến thuật duyệt bằng vòng lặp là phổ biến, tuy nhiên dùng nó như thế nào để có hiệu quả cao nhất hay muốn cải tiến thuật toán bằng vòng lặp ta phải làm thế nào thì vẫn còn là mới mẻ. Ta có thể xét bài toán bằng chiến thuật duyệt bằng vòng lặp như sau: Bài toán trăm trâu trăm cỏ: Trăm trâu, trăm cỏ trâu đứng ăn năm trâu nằm ăn ba lọm khọm trâu già ba con một bó. Hỏi có bao nhiêu trâu mỗi loại? Ý tưởng 1: - Gọi trâu đứng là x, trâu nằm là y, trâu già là z. (1<=x,y,z<=100). - Ta thử tất cả các trường hợp x, y, z từ 1 đến 100. Nếu thỏa mãn (x+y+z=100) và (5x+3y+z/3=100) thì bộ x, y, z đó là một nghiệm của bài toán. Code: Var x,y,z:longint; Begin For x:=1 to 100 do For y:=1 to 100 do For z:=1 to 100 do if (x+y+z=100) and (5*x+3*y+z/3=100) then writeln('trau dung=',x,' ','trau nam=',y,' trau gia=',z); readln; end. Ý tưởng 2: - Gọi trâu đứng là x, trâu nằm là y thì trâu già là 100-(x+y). - Ta có 5*x ≤100 => x ≤ 20, tương tự ta có y<=33. Code: Var x,y:longint; Begin For x:=1 to 20 do For y:=1 to 33 do if (5*x+3*y+(100-x-y)/3=100) then writeln('trau dung=',x,' ','trau nam=',y,' trau gia=',100-x-y); readln; end. Nhận xét: - Với hai ý tưởng trên đều cho cùng kết quả, có 3 bộ nghiệm như sau: (4, 18, 78); (8, 11, 81); (12, 4, 81). Tuy nhiên rõ ràng cài đặt thuật toán bằng ý tưởng 2 nhanh hơn ý tưởng 1. - Trong cả 2 thuật toán trên thì phần chứa các vòng lặp for gọi là phần duyệt còn phần chứa câu lệnh if gọi là phần kiểm tra. - Chi phí của thuật toán duyệt = chi phí duyệt * chi phí kiểm tra. ở ý tưởng 1 chi phí là: 100*100*100*1; còn ở ý tưởng 2 là: 20*33*1. Do vậy chương trình 2 chạy nhanh hơn chương trình 1 gấp 1000000/660=1515 lần. 2. Các bước giải bài toán bằng vòng lặp: - Xác định véc tơ nghiệm, tức là xác định các tham số để duyệt (Như bài toán trên với ý tưởng 1 là x, y, z còn ý tưởng 2 là x, y) cùng với miền giá trị mà các tham số này có thể nhận (Xác định phần duyệt) - Xác định phần kiểm tra. - Tối ưu thuật toán: Có thể tối ưu ở phần duyệt hoặc tối ưu ở phần kiểm tra tùy thuộc vào từng bài toán cụ thể. 3. Một số bài tập áp dụng: Bài 1: 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: - Véc tơ nghiệm (i,j) với i là chỉ số đầu và j là chỉ số của phần tử cuối của một dãy con cần tìm. Vậy i sẽ tăng từ 1 đến n-3 còn j sẽ tăng từ i+1 đến n => Phần duyệt sẽ có hai vòng lặp với chỉ số i và j nên độ phức tạp là O(n2). - Kiểm tra: Ta phải tính tổng các phần tử từ i đến j (mất một vòng lặp for) nên chi phi kiểm tra có độ phức tạp là O(n). - Tổng chi phí thuật toán là: O(n3) nên có thể chạy được với n<=300. Code: Function kiemtra(i,j:longint):Boolean; Var 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; *. Thuật toán 2: Cài tiến việc kiểm tra từ O(n) về O(1). - Ở thuật toán 1 nếu với mỗi cặp (i,j) ta đã biết tổng các phần tử từ ai đến aj thì chi phí kiểm tra chỉ còn là O(1). Ta có thể thực hiện việc đó bằng phương pháp dùng mảng cộng dồn như sau: 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. Ta tính mảng L với độ phức tạp O(n) như sau: 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 kiemtra(i,j:longint):Boolean; Begin 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. *. 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[i1] + 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). Bài 2: 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 1: - 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. (Độ phức tạp của phần duyệt là O(n2)) - Với mỗi i,j ta tìm tổng của đoạn 1 và 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; Ý tưởng 2: Cải tiến phần kiểm tra - 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 (Như bài toán 1) - 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; Ý tưởng 3: 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 imax then max:= a[i,k]+a[j,k]+a[i,l]+a[j,l]; Ý tưởng 2 Với hai hàng i và j ta tìm 2 giá trị lớn nhất của tổng a[i,k] và a[j,k]. Tổng hai gia trị đó chính là hình chữ nhật lớn nhất nếu chọn hành i và hàng j. Kq:=-oo; for i:=1 to m-1 do for j:=i+1 to m do Begin max1:=-oo; max2:=-oo; for h:=1 to n do if a[i,h]+a[j,h]>max1 then begin max2:=max1; max1:=a[i,h]+a[j,h]; end else if a[i,h]+a[j,h]>max2 then max2:=a[i,h]+a[j,h]; if max1+max2>kq then kq:=max1+max2; Độ phức tạp là O(n3) đáp ứng được yêu cầu của đề bài với n<=500. Kết luận: - Duyệt bằng vòng lặp tuy không phải là mới nhưng chúng ta phải tiến hành đúng tuần tự các bước thì giải bài tập mới hiệu quả được từ việc xác định véctơ nghiệm, xác định miền giá trị của các thành phần trong véc tơ nghiệm cho đến việc tối ưu phần kiểm tra hoặc tối ưu phần duyệt. - Hy vọng chuyên đề có thể giúp các bạn làm tốt được các bài tập bằng duyệt vòng lặp – hay còn gọi là thuật toán “trâu – bò”. - Chúc các bạn thành công!