Sáng kiến kinh nghiệm Kỹ thuật chặt nhị phân trong bài toán tìm kiếm

an)= Arccos((a*a+b*b-c*c)/(2*a*b))
Giả sử R là tâm bán kính đường tròn, ta có góc O1OO2=((R1+R)2+(R2+R)2-(R1+R2)2)/ (R1+R2). (Quan sát hình bên)
Từ đây ta tính được tổng góc radian được tạo thành từ tâm đường tròn và các đồng xu 
Để tìm R thỏa mãn, ta sẽ tìm kiếm nhị phân giá trị của R với Rmin=0 và Rmax = tổng các Ri
O1
O2
R1
R2
R
O
O3
O4

Chương trình:
program Vongtron;
uses math;
const fi='Vongtron.inp';
 fo='Vongtron.out';
 nmax=10000;
var f:text;
 r:array[1..nmax] of real;
 n:longint;
 s,kq:real;
procedure doc;
var i:longint;
begin
 assign(f,fi);
 reset(f);
 readln(f,n);
 s:=0;
 for i:=1 to n do
 begin
 read(f,r[i]);
 s:=s+r[i];
 end;
end;
function goc(a,b,c:real):real;
begin
 goc:=arccos((a*a+b*b-c*c)/(2*a*b));
end;
function tinh(x:real):real;
 var s1:real;
 i:longint;
 begin
 s1:=0;
 for i:=2 to n do
 s1:=s1+goc(x+r[i],x+r[i-1],r[i]+r[i-1]);
 s1:=s1+goc(x+r[1],x+r[n],r[1]+r[n]);
 tinh:=s1;
 end;
 procedure tknp;
 var dau,cuoi,giua,kq1:real;
 begin
 dau:=0;
 cuoi:=s;
 giua:=(dau+cuoi)/2;
 while (daugiua) and (cuoigiua) do
 begin
 kq1:=tinh(giua);
 if kq1=2*pi then break;
 if kq1>2*pi then dau:=giua
 else cuoi:=giua;
 giua:=(dau+cuoi)/2;
 end;
 kq:=giua;
end;
begin
doc;
tknp;
assign(f,fo);
rewrite(f);
writeln(f,kq:8:3);
close(f);
end.
Bài 15. Bảo tồn động vật hoang dã (Nguồn bài: thầy Lê Minh Hoàng)
Một khu bảo tồn động vật có N địa điểm và các đường đi hai chiều nối các địa điểm đó, địa điểm thứ i có nhiệt độ là ti, giữa hai địa điểm bất kỳ có nhiều nhất là một đường đi nối chúng. Người ta muốn di chuyển một loài động vật quý hiếm từ địa điểm A tới địa điểm B, tuy nhiên nếu chênh lệch về nhiệt độ giữa hai địa điểm liên tiếp trên đường đi là quá cao thì loài động vật này rất có thể bị chết.
Yêu cầu: Hãy chỉ ra một hành trình mà độ lệch nhiệt độ lớn nhất giữa hai địa điểm liên tiếp bất kỳ trên đường đi là cực tiểu. 
Dữ liệu vào: Đọc từ file MOVE.INP
- Dòng 1: Chứa ba số N, A, B (2 ≤ N ≤ 200; A#B)
- Dòng 2: Chứa N số tự nhiên t1, t2, ..., tN ("i: 0 ≤ ti ≤ 20000)
- Các dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v cho biết giữa hai địa điểm u và v có đường đi nối chúng.
Kết quả: Ghi ra file MOVE.OUT ghi một số nguyên là độ lệch nhiệt độ lớn nhất giữa hai  địa  điểm liên tiếp bất kỳ trên đường đi tìm được, nếu không tồn tại đường đi thì dòng này ghi số -1.
MOVE.INP
MOVE.OUT
7 1 4
20 22 29 30 24 27 26
1 2
1 3
1 4
2 4
2 5
3 4
3 6
4 5
4 6
5 7
6 7
2
Hướng dẫn:
Bài toán yêu cầu tìm một hành trình đi từ A tới B sao cho độ lệch nhiệt độ lớn nhất  Res giữa hai địa điểm liên tiếp bất kỳ trên đường đi là nhỏ nhất. Gọi MaxT là giá trị nhiệt độ ti lớn nhất, vậy Res nằm trong [0..MaxT].  Ứng với mỗi giá trị chặt nhị phân ta dùng thuật toán tìm kiếm theo chiều rộng kiểm tra xem có đường đi từ A tới B không.
program baoton;
const fi='move.inp';
 fo='move.out';
var f:text;
 n,a,b,maxt,res:longint;
 t,trace:array[1..200] of longint;
 a1:array[1..200,1..200] of byte;
 q:array[1..40000] of longint;
procedure doc;
var i,u,v:longint;
begin
 assign(f,fi);
 reset(f);
 readln(f,n,a,b);
 maxt:=0;
 for i:=1 to n do
 begin
 read(f,t[i]);
 if t[i]>maxt then maxt:=t[i];
 end;
 readln(f);
 fillchar(a1,sizeof(a1),0);
 while not eof(f) do
 begin
 readln(f,u,v);
 a1[u,v]:=1;
 a1[v,u]:=1;
 end;
end;
function bfs(val:integer):boolean;
 Var d,c,p,v:integer;
 Begin
 fillchar(trace,sizeof(trace),0);
 d:=1;
 c:=1;
 q[d]:=a;
 repeat
 p:=q[d];
 inc(d);
 for v:=1 to n do
 if (a1[p,v]=1) and (trace[v]=0) and (abs(t[p]-t[v])<=val) then
 begin
 trace[v]:=p;
 if v=b then exit(true);
 inc(c);
 q[c]:=v;
 end;
 until d>c;
 bfs:=false;
end;
Procedure xuly;
var d,c,g:integer;
 ok:boolean;
Begin
 res:=-1;
 d:=0;
 c:=maxt;
 While d<c do
 begin
 g:=(d+c) div 2;
 ok:=bfs(g);
 if ok then
 begin
 res:=g;
 c:=g-1;
 end
 else d:=g+1;
 end;
end;
begin
 doc;
 xuly;
 assign(f,fo);
 rewrite(f);
 writeln(f,res);
 close(f);
end.
4. Một số bài tập tự luyện
Bài 1. DGOLD - Chia vàng – Nguồn Spoj.com
Chuyện kể lại rằng, trong một lần thám hiểm hang động, Aladdin và thần đèn phát hiện một kho báu cổ xưa gồm N thỏi vàng ròng. Vẫn còn tiếc rẻ vì ngày trước ở trong hang thần không thó được món gì ngoài cây đèn cũ nát, Aladdin quyết tâm lần này sẽ mang hết vàng về. Ngặt nỗi kho báu này bị nguyền: Nếu muốn đem K thỏi vàng ra khỏi hang thì K thỏi vàng này phải được chia thành 2 phần có khối lượng bằng nhau mà không được cắt, đập thỏi vàng nào ra cả. Nếu không làm đúng thì hang sẽ sập xuống chôn vùi tất cả, đến thần đèn cũng không cứu được.
 Thần đèn dù tài phép vô biên nhưng tính toán lại rất kém, chỉ có thể hô biến ra một cái cân ký chứ không chọn được vàng. Aladdin cũng không hơn gì (lớn lên trên đường phố mà). Tuy nhiên Aladdin lại không chịu ra khỏi hang một khi chưa đem được lượng vàng nhiều nhất về. Thần đèn đang ngán ngẩm không biết khi nào Aladdin mới chọn vàng xong thì khỉ Abu xuất hiện. Nhanh như thoắt Abu đã chọn xong vàng và chia thành 2 túi có khối lượng đúng bằng nhau.Abu lại còn chọn được lượng vàng nhiều nhất nữa. Trong lúc Aladdin mừng hớn hở (vì bắt được vàng) thì thần đèn do chậm hiểu vẫn còn thắc mắc không biết một túi có bao nhiêu vàng. Hãy giúp thần đèn tìm con số này.
Input: Dòng đầu ghi số N– số thỏi vàng trong kho báu.
N dòng tiếp theo, dòng thứ i ghi số nguyên dương Mi là khối lượng của thỏi vàng i (tính theo gam).
         Giới hạn :    2 <= N <= 24
                              1 <= Mi<= 40.106
Output: Ghi ra một số nguyên duy nhất là số gam vàng trong một túi của Abu.
Input:
Output:
5
6000
30000
3000
11000
3000
6000
Bài 2. C11POST - Đưa quà 
 Santa Khánh được giao nhiệm vụ đi phát quà trong một ngôi làng được biểu diễn bởi ma trận có độ lớn MxN từ nhà Santa Khánh đến những trẻ em trong làng. Trong ma trận có duy nhất 1 điểm là nhà của Santa Khánh ký hiệu là ‘P’, những ngôi nhà của các đứa trẻ ký hiệu là ‘K’, những điểm trống được ký hiệu là ‘.’ .Mỗi điểm được đặc trưng bởi độ cao là H[i][j]. Mỗi bước, Santa Khánh có thể đi đến những ô có điểm chung với ô đang đứng. Độ mệt mỏi bằng hiệu chênh lệch độ cao giữa điểm cao nhất và điểm thấp nhất trên đường đi. Khánh đi từ nhà của Santa Khánh đến tất cả các ngôi nhà khác của trẻ em. Do Santa Khánh phải cưỡi tuần lộc để đi phát quà, mà lũ tuần lộc ăn rất nhiều Carrot khi phải chịu độ mệt mỏi cao. Do đó Santa Khánh muốn tìm độ mệt mỏi nhỏ nhất để tích kiệm tiền mua carrot cho tuần lộc.
Input
Dòng 1: Gồm 2 số M và N (M,N <= 100)
M dòng tiếp theo, mỗi dòng gồm N ký tự dạng ‘P’ , ’K’ , ’.’
M dòng tiếp theo, mỗi dòng gồm N số chỉ độ cao (0 <= H[i][j]<= 109)
Output
Gồm 1 số duy nhất là kết quả cần tìm.
Input
Output
4 5
.....
.P...
.....
..K..
40 5 34 63 53 
6 50 99 76 64 
8 28 64 43 65 
58 54 60 15 75 
14
Giới hạn: 50% số test có N,M<=60 và N*M <= 2500
Bài 3. VOGCDSUM - Tổng ước chung lớn nhất – Nguồn Spoj.com
Giáo sư Honest là một tay bịp bợm có hạng trong giới khoa học. Ngày hôm qua, hắn vừa tuyên bố rằng đã phát minh ra thuật toán tính ước chung lớn nhất của một dãy số có độ phức tạp O(1/N), tức là input càng lớn thì thuật toán chạy càng nhanh.   
Trong báo cáo khoa học của mình, Honest bày ra thí nghiệm như sau:
Cho một dãy số gồm N số nguyên dương. Honest tính tổng của các ước chung lớn nhất của tất cả các dãy con liên tiếp của dãy số trên (dãy con liên tiếp của một dãy số N phần tử được định nghĩa là dãy con chứa phần tử thứ L, L + 1, ..., R với 1 ≤ L ≤ R ≤ N). 
Honest tuyên bố rằng hắn có thể thực hiện thao tác vừa rồi trong O(N) bằng cách áp dụng thuật toán tính ước chung lớn nhất của một dãy số trên tất cả N * (N + 1) / 2, tức là O(N2), dãy con liên tiếp của dãy số. Vì thế, thuật toán của hắn ta có độ phức tạp là O(1 / N). 
"Không thể nào có chuyện như vậy!!!". Hội đồng khoa học của diễn đàn VNOI muốn lật tẩy trò lừa trẻ con của Honest. Tuy nhiên thì đầu tiên họ cần tìm ra cách để thực hiện lại thí nghiệm của Honest với tốc độ nhanh nhất có thể. Các bạn hãy giúp in ra số dư của kết quả thí nghiệm mà Honest đã tiến hành khi chia cho 109 + 7 nhé. 
Input
Dòng thứ nhất chứa số nguyên N.
Dòng thứ hai chứa N số của dãy A.
Output
Một số duy nhất là phần dư của kết quả tìm được khi chia cho 109 + 7.
Giới hạn
Test 1 (15%): 1 ≤ N ≤ 100, 1 ≤ Ai ≤ 1012
Test2 (15%): 1 ≤ N ≤ 5000, 1 ≤ Ai ≤ 1012
Test 3 (30%): 1 ≤ N ≤ 105, 1 ≤ Ai ≤ 200
Test 4 (40%): 1 ≤ N ≤ 105, 1 ≤ Ai ≤ 1012
Thời gian chạy cho Test 1 và 2 là 1s, Test 3 và 4 là 3s.
Input:
Output:
4
3 6 4 8
34
Bài 4. VMCANDLE - Aladdin và cây đèn cầy – Nguồn Spoj.com
Nến (còn gọi là đèn cầy) thường được thắp trong các buổi tiệc ngoài tời để tạo không khí huyền ảo, ấm cúng, lãng mạn. Hôm nay là sinh nhật Jasmine! Aladdin, Abu và thần đèn đã tổ chức một buổi tiệc thịnh soạn gồm cơ man nào là sơn hào hải vị. Trên bàn tiệc là một hàng N cây nến bằng đúng số tuổi của Jasmine. Điều đặc biệt là những cây nến này có phép (do của thần đèn).
Ban đầu N nến đều đang cháy.
Nếu thổi lần đầu thì cả N nến sẽ tắt.
Thổi lần hai thì các nến số chẵn cháy trở lại.
Thổi sang lần thứ 3 thì nến 3, 6, 9, 12, . nếu đang cháy sẽ tắt, còn nếu đang tắt sẽ cháy.
Tương tự vậy với các lần 4, 5, 6,  , N.
Aladdin nhận thấy là sau khi thổi nến một số lần thì một số nến sẽ không bị tác động nữa, từ đó nghĩ ra một trò chơi. Aladdin đố Jasmine tìm ra cây nến còn sáng thứ K sau khi thổi hết cả N lần. Nếu Jasmine trả lời đúng sẽ nhận được một phần quà đặc biệt mà Aladdin bỏ ra cả mấy ngày để chuẩn bị.
Phải thối hết N lần thì mất công quá L. Tuy nhiên Aladdin có một mẹo, không cần thổi mà cũng không cần biết có bao nhiêu nến tất cả vẫn tính được ngay số thứ tụ của cây nến đang cháy thứ K. Hãy giúp Jasmine giành được quà nào!
Yêu cầu
Cho K. Tìm số thứ tụ của cây nến đang cháy thứ K sau N lần thổi nến
Input
Một số nguyên dương duy nhất K
Giới hạn
K <= 1018
33% số test có K <= 4000
Output
Một số nguyên dương là số thứ tự của cây nến sáng thứ K.
Input
Output
1
2
6
8
21
26

Bài 5. PRAVO - Tam giác vuông – Nguồn Spoj.com
Cho n điểm trên mặt phẳng. Hỏi có bao nhiêu tam giác vuông được tạo thành. 
Input
Dòng đầu tiên chứa số nguyên dương n (3<=n<=1500), số điểm trên mặt phẳng 
Dòng thứ i trong n dòng tiếp theo, mỗi dòng chứa 2 số nguyên xi, yi, tọa độ của một điểm (-109<=xi, yi <= 109). Không có hai điểm nào có cùng tọa độ. 
Output
Gồm một dòng duy nhất là số lượng tam giác vuông tìm được. 
Input:
Output:
3
4 2
2 1
1 3
1
Bài 6. MTWALK - Mountain Walking
Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất. 
Dữ liệu
Dòng 1: N
Dòng 2..N+1: Mỗi dòng chứa N số nguyên, mỗi số cho biết cao độ của một ô. 
Kết quả
Một số nguyên là chênh lệch cao độ nhỏ nhất.
Input
Output
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
2

5. Đánh giá bài viết
Ưu điểm:
Với cách tiếp cận bài toán đơn giản giúp học sinh nắm bắt vấn đề và áp dụng cho các bài tương tự. Các bài tập có sự so sánh với cách lập trình của học sinh trước và khi áp dụng kỷ thuật “chặt nhị phân” từ đó giúp học sinh nắm rõ được tính cần thiết cũng như kỷ thuật để cài đặt thuật toán này.
6. Quá trình thực nghiệm sư phạm
Qua thực tế các năm giảng dạy cũng như ôn thi học sinh giỏi, đã áp dụng hướng dẫn cho học sinh tôi bồi dưỡng làm các dạng bài tập này. Kết quả đa số học sinh khi gặp dạng bài toán này đã làm tốt. Ban đầu gặp những dạng toán này, học sinh thường làm theo các cách thông thường, áp dụng tìm kiếm tuần tự và một số cách tư duy giải toán khác nên không chạy được hết các bộ test theo yêu cầu của đề bài, thường gặp lỗi chạy quá thời gian (Time limit). Sau một thời gian hướng dẫn học sinh cách tư duy, áp dụng kỷ thuật chặt nhị phân, học sinh đã có thể giải quyết hầu hết các bài toán có sử dụng kỷ thuật này. Đặc biệt trong quá trình bồi dưỡng học sinh giỏi, việc nghiên cứu tìm hiểu đề tài này đã giúp học sinh có nhiều đam mê hơn với bộ môn, luôn tìm cách giải để giải quyết tất cả các trường hợp của đề bài. Vì vậy kết quả thi học sinh tin học trong những năm gần đây của bản thân luôn đạt thành tích cao. Cụ thể trong 2 năm học gần nhất:
- Năm học 2016 – 2017: Có 01 học sinh đạt giải nhất, 03 học sinh đạt giải nhì.
- Năm học 2017 – 2018: Có 01 học sinh được tham dự vào đội tuyển Quốc gia tin học. 
PHẦN III. KẾT LUẬN VÀ KIẾN NGHỊ
1. Kết luận 
Ý nghĩa của đề tài
*) Đối với bản thân: 
Trong những năm bồi dưỡng học sinh giỏi, nghiên cứu tài liệu, tham khảo đề thi của các tỉnh, đề thi trên mạng tôi đã hệ thống hóa, tổng hợp các bài tập áp dụng kỷ thuật “chặt nhị phân”. Quá trình tập hợp, giải bài tập giúp tôi nắm vững hơn kiến thức về thuật toán, cách phối hợp các thuật toán và cách xác định tính tối ưu của chương trình. Bên cạnh đó tư duy lập trình, khả năng sáng tạo khi gặp các bài toán phức tạp được nâng cao. 
*) Đối với học sinh, nhà trường:
- Đề tài đã đưa ra được một số các bài tập cơ bản và cách áp dụng kỷ thuật “chặt nhị phân” từ dễ đến khó, giúp học sinh có cách nhìn tổng quát, từ đó học sinh có thể nhận dạng, áp dụng tốt kỷ thuật này.
- Đây là một phần kiến thức quan trọng nhằm nâng cao tư duy giải thuật để áp dụng trong quá trình giảng dạy môn tin học đặc biệt là bồi dưỡng học sinh giỏi.
- Kết quả, điểm thi học sinh giỏi bộ môn Tin học tại đơn vị công tác ngày càng tốt hơn cả về số lượng và chất lượng giải.
*) Đối với đồng nghiệp:
- Đồng nghiệp có thể sử dụng làm tài liệu tham khảo để tự nghiên cứu và bồi dưỡng cho học sinh khá, giỏi.
2. Kiến nghị
- Trong thời gian tới sẻ tiếp tục nghiên cứu, tìm tòi để đề tài được chuyên sâu hơn đặc biệt là các bài toán cần phải linh hoạt trong kỷ thuật “chặt nhị phân”.
- Trong tài liệu giảng dạy tin học 10 và 11 nên bổ sung thêm thời lượng và các dạng toán để áp dụng kỷ thuật “chặt nhị phân”.
Rất mong sự đóng góp ý kiến, trao đổi kinh nghiệm của đồng nghiệp, hội đồng khoa học Sở Giáo dục và Đào tạo Hà Tĩnh để đề tài được hoàn thiện, có hiệu quả cao hơn khi áp dụng vào thực tế giảng dạy.
Tôi xin chân thành cảm ơn.
TÀI LIỆU THAM KHẢO
1. Sách giáo khoa Tin học 10, Tin học 11 NXB Giáo dục.
2. Phan Công Minh, Hồ Sỹ Việt Anh, Ngô Văn Hoàng, Bùi Minh Trí, Nguyễn Cảnh Toàn, Một số vấn đề đáng chú ý trong môn Tin học
3. Hồ Sỹ Đàm, Tài liệu giáo khoa chuyên Tin tập 1 NXB Giáo dục.
4. Lê Minh Hoàng, Giải thuật và lập trình.
5. Tuyển tập đề thi Olympic 30 tháng 4, lần thứ XV – 2009, Nhà xuất bản đại học sư phạm.
6. Tuyển tập đề thi Olympic 30 tháng 4, lần thứ XVII – 2011, Nhà xuất bản đại học sư phạm.
7. Một số website về lập trình Online:
- upcoder.hcmu.edu.vn
- vn.spoj.com
- codeforces.com
- kienthuc24h.com
MỤC LỤC