Báo cáo Biện pháp Áp dụng thuật toán tìm kiếm nhị phân trong quá trình bồi dưỡng học sinh giỏi môn Tin học

Nội dung tài liệu: Báo cáo Biện pháp Áp dụng thuật toán tìm kiếm nhị phân trong quá trình bồi dưỡng học sinh giỏi môn Tin học

1. d := 1; {d là điểm đầu của đoạn tìm kiếm} c := n; {c là điểm cuối của đoạn tìm kiếm} tim_thay:=false; while (d <=c) and not tim_thay do begin g:= (d+c) div 2 if x = a[g] then tim_thay :=true else if x<a[g] then c := g-1 else d:=g+1 end If tim_thay then kq:=g else kq := 0 {kq là vị trí của số hạng bằng x hoặc 0 nếu không tìm thấy x} End; 2. Độ phức tạp: Để tìm kiếm một phần tử trong mảng. Với cách thông thường, ta phải duyệt tất cả các số từ a[1] đến a[n], tức là mất độ phức tạp O(n). Tuy nhiên với mảng đơn điệu, ta dùng chặt nhị phân để tìm kiếm thì : Ttốt= O(1) ( x nằm ở vị trí giữa mảng) Txấu= O(logn) Logarit là một hàm tăng chậm. Trong trường hợp ta còn băn khoăn về tính hiệu quả khi tìm kiếm nhị phân, hãy xét việc tìm kiếm một tên trong một cuốn danh bạ điện thoại có chứa một triệu tên. Tìm kiếm nhị phân cho phép ta tìm thấy bất kỳ tên nào chỉ sau nhiều nhất 21 lượt so sánh. Nếu ta có thể quản lý một danh sách có chứa tất cả mọi người trên thế giới được sắp xếp theo tên, ta có thể tìm thấy bất kỳ người nào trong vòng chưa đầy 35 bước. 3. Bài tập vận dụng Bài 1. ĐOÁN SỐ Hai người chơi như sau: Người thứ nhất sẽ nghĩ ra một số nguyên dương trong khoảng từ 1 đến N (N được cho biết trước). Người thứ hai sẽ lần lượt đưa ra các số dự đoán. Với mỗi số dự đoán này, người thứ hai sẽ nhận được câu trả lời cho biết số mình vừa 3
2. nêu ra lớn hơn, nhỏ hơn, hay bằng với số mà người thứ nhất đã nghĩ. Em hãy giúp người thứ hai chọn đúng số cần tìm với số lần đoán càng ít càng tốt. Thuật toán: Người thứ hai muốn chọn đúng số mà người thứ nhất nghĩ với số lần đoán ít nhất thì người thứ hai chắc chắn phải sử dụng đến thuật toán tìm kiếm nhị phân. Các bước sẽ lần lượt như sau: Bước 1.X:=1; y:=n; a:=0; Bước 2.A:=(x+y) div 2 Bước 3.Lần đoán thứ i: a Bước 4.Nếu a lớn hơn số cần tìm thì gán y:=a Nếu a nhỏ hơn số cần tìm thì gán x:=a Bước 5.Nếu số lần đoán vượt quá log2N thì chấm dứt Ngược lại thì trở lại bước 2 Bài 2. DÃY CON Cho một ddãy số nguyên dương a1, a2, ..., aN (1 ≤ N ≤ 5*105), ai ≤109 với mọi i=1..N và một số nguyên dương S (S < 109). Yêu cầu : Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy mà có tổng các phần tử lớn hơn hoặc bằng S. Dữ liệu vào: Đọc từ file SUB.INP gồm 2 dòng, dòng 1 chứa N và S ở dòng đầu. Dòng 2 chứa các phần tử của dãy. Dữ liệu ra: Kết quả ghi vào file SUB.OUT, chứa độ dài của dãy con tìm được. Ví dụ : SUB.INP SUB.INP 10 17 2 5 1 3 5 10 7 4 9 2 8 Program SUB; const fi='SUB.INP'; fo='SUB.OUT'; nmax = 100000; oo = 10000001; 4
3. Var A,T:array[0..nmax] of int64; N,S,kq:longint; F:text; procedure doc; var i:longint; Begin assign(F,fi); reset(F); T[0] := 0; Readln(F,N,S); for i:=1 to N do Begin read(F,A[i]); T[i] := T[i-1] + A[i]; end; close(F); end; function min(a,b:longint):longint; Begin if a > b then min := b else min := a; end; procedure xuly; var i,d,c,g:longint; Begin kq := oo; for i:=1 to N do Begin d := 1; c := i-1; While d <= c do 5
4. Begin g := (d + c) div 2; if T[i] - T[g] >= S then Begin kq := min(kq,i-g); d := g + 1; end else c := g - 1; end; end; end; procedure ghi; Begin assign(F,fo); rewrite(F); if kq = oo then write(F,0) else Write(F,kq); close(F); end; BEGIN doc; xuly; ghi; END. Bài 3. SỐ 0 CUỐI CÙNG Cho một dãy số khoảng 1000000 kí tự số toàn 0 và 1. Biết rằng các số 0 đứng trước các chữ số 1: 000....0011...11. Hãy cho biết vị trí của số 0 cuối cùng trong dãy. Thuật toán: Ta tiến hành tìm kiếm nhị phân trên xâu kí tự để tìm ra vị trí số 0 cuối cùng như sau: - Tìm phần tử giữa xâu đang xét - So sánh kí tự ở vị trí giữa xâu với kí tự 0. 6
5. - Nếu kí tự giữa xâu là kí tự 0 thì ta tìm ở nửa sau của xâu, nếu không phải kí tự 0 (mà là 1) thì ta tìm ở nửa trước của xâu. 1.d:=1; c:=length(s); 2. trong khi d<c thì 2.1 g:=(d+c+1) div 2; 2.2 Nếu s[g]='0' thì d:=g 2.3 Nếu s[g]='1' thì c:=g-1; 3.Quay lại bước 3 4.Kết thúc Vậy vị trí của số 0 cuối cùng trong dãy là d Bài 4. HÀNG CÂY Trong khu vườn, người ta trồng một hàng cây chạy dài gồm có N cây, mỗi cây có độ cao là a1, a2, , aN. Người ta cần lấy M mét gỗ bằng cách đặt cưa máy sao cho lưỡi cưa ở độ cao H (mét) để cưa tất cả các cây có độ cao lớn hơn H (dĩ nhiên những cây có độ cao không lớn hơn H thì không bị cưa). Ví dụ: Nếu hàng cây có các cây với độ cao tương ứng là 20; 15; 10 và 18 mét, cần lấy 7 mét gỗ. Lưỡi cưa đặt tại độ cao hợp lí là 15 mét thì độ cao của các cây còn lại sau khi bị cưa tương ứng là 15; 15; 10 và 15 mét. Tổng số mét gỗ lấy được là 8 mét (dư 1 mét). Yêu cầu: Hãy tìm vị trí đặt lưỡi cưa hợp lí (số nguyên H lớn nhất) sao cho lấy được M mét gỗ và số mét gỗ dư ra là ít nhất. Dữ liệu: • Dòng thứ nhất chứa 2 số nguyên dương N và M (1≤N≤10 6; 1≤M≤2x109) cách nhau một dấu cách. • Dòng thứ hai chứa N số nguyên dương ai là độ cao của mỗi cây trong hàng 9 (1≤ai≤10 ; i=1 N), mỗi số cách nhau ít nhất một dấu cách. Kết quả: Đưa ra màn hình một số nguyên cho biết giá trị cần tìm. Ví dụ: WOOD.INP WOOD.OUT 7
6. 4 7 15 20 15 10 18 Thuật toán : + Đầu=0, cuối= chiều cao cây cao nhất. + Kiểm tra số mét gỗ S lấy được khi chặt ở độ cao h=(đầu+cuối) div 2: - Nếu S=M: Thì in ra h và dừng chương trình. - Nếu S<M thì đầu =h - Nếu S>M thì cuối =h - Tiếp tục kiểm tra h cho đến khi chênh lệch của M, S lặp lại. writeln('Chieu cao cua cac cay la:'); for i:=1 to n do begin write('cay ',i,'=');readln(a[i]); if a[i]>c then c:=a[i]; end; d:=0;kt:=true; while kt and (d<=c) do begin s:=0; g:=(d+c) div 2; for i:=1 to n do begin t:=a[i]-g; if t>=0 then s:=s+t; end; t:=s-m; if (t=0 )or (cl=t)then kt:=false else begin cl:=t; if t<0 then c:=g else d:=g; end; 8
7. end; if t>=0 then write('h=',g) else write('ko tim dc'); Bài 5. DÃY CON TĂNG DÀI NHẤT Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint. Input: File Lis.Inp • Dòng đầu tiên gồm số nguyên N. • Dòng thứ hai gồm N số mô tả dãy. Output: file Lis.Out Gồm một số nguyên duy nhất là đáp số của bài toán Ví dụ: Lis.Inp Lis.Out 5 3 2 1 4 3 5 Thuật toán: Gọi k là độ dài cực đại của dãy con tăng và ký hiệu H[1..k] là dãy có ý nghĩa sau: H[i] là số hạng nhỏ nhất trong các số hạng cuối cùng của các dãy con tăng có độ dài i. Đuơng nhiên h[1] < h[2] <.. < h[k]. Mỗi khi xét thêm một giá trị mới trong dãy A thì các giá trị trong dãy H và giá trị k cũng tương ứng thay đổi. Res:=1; H[1]:=1; For i:=2 to n do Begin If A[i] < a[h[1]] then h[1]:=i else if a[i] > a[h[res]] then Begin Inc(Res); H[res]:=i; End 9
8. else Begin d:=1; c:=Res; While d<>c do begin mid:=(d+c+1) div 2; If A[i] > a[h[mid]] then d:=mid else c:=mid-1; End; Mid:=(d+c) div 2; If (A[h[mid]] < a[i]) and (a[i]<a[h[mid+1]]) then h[mid+1]:=i; End; End; Writeln(Res); Bài 6 : Đ￿m tam giác Cho 3 dãy số dương A, B, C cùng có N phần tử. Hãy đếm xem có bao nhiêu bộ 3 số A[i], B[j] và C[k] mà 3 số này là 3 cạnh của 1 tam giác. Dữ liệu vào: từ file TRIANGLE.INP với cấu trúc: - Dòng đầu chứa số nguyên n (n <= 1000) - Dòng thứ hai chứa các số A1, A2, ..., An. - Dòng thứ ba chứa các số B1, B2, ..., Bn. - Dòng thứ tư chứa các số C1, C2, ..., Cn. Các số ai, bi, ci đều không vượt quá 104 và được ghi cách nhau bởi dấu cách. Dữ liệu ra: file văn bản TRIANGLE.OUT gồm một số S duy nhất là số lượng bộ ba số tìm được. TRIANGLE.INP TRIANGLE.OUT TRIANGLE.INP TRIANGLE.OUT 2 2 3 8 2 3 2 3 1 3 1 4 4 9 10
9. 4 7 8 5 2 program triangle; const fi='triangle.inp'; fo='triangle.out'; max=1000; var f: text; a,b,c: array[1..max] of longint; n,dem: longint; procedure Nhapdl; var i,j,tg: longint; begin assign(f,fi); reset(f); readln(f,n); for i:= 1 to n do read(f, a[i]); readln(f); for i:= 1 to n do read(f, b[i]); readln(f); for i:= 1 to n do read(f, c[i]); readln(f); close(f); for i:= 1 to n-1 do for j:= i to n do begin if a[i]>a[j] then begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; 11
10. end; if b[i]>b[j] then begin tg:=b[i]; b[i]:=b[j]; b[j]:=tg; end; if c[i]>c[j] then begin tg:=c[i]; c[i]:=c[j]; c[j]:=tg; end; end; dem:=0; end; procedure tim; var i,j,x,y,dau,cuoi,giua: longint; begin for i:= 1 to n do for j:= 1 to n do begin x:=abs(a[i]-b[j]); y:=a[i]+b[j]; dau:=1; cuoi:=n; while dau<=cuoi do begin if (c[dau]>x) and (c[cuoi]<y) then begin 12
11. dem:=dem+cuoi-dau+1; break; end; if (c[dau]<=x) then inc(dau); if (c[cuoi]>=y) then dec(cuoi); end; end; end; procedure Inkq; begin assign(f,fo); rewrite(f); writeln(f,dem); close(f); end; BEGIN Nhapdl; Tim; Inkq; END. III. HIỆU QUẢ Kết quả sau khi áp dụng nội dung này vào việc dạy bồi dưỡng học sinh giỏi thì có hiệu quả tốt trong quá trình phát triển tư duy của học sinh. Trong các năm dạy đội tuyển, kết quả học sinh đậu có tỉ lệ tương đối tốt, cụ thể trong các năm học gần đây 2020 – 2021, 2022- 2023 đội tuyển Tin đều có HS đạt HSG tỉnh. IV. KẾT LUẬN: 13