(SKKN 2022) vận dụng thuật toán tìm kiếm nhị phân vào giải quyêt tối ưu một số bài toán
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (134.19 KB, 22 trang )
Mụclục:
PHẦN 1. MỞ ĐẦU...................................................................................................1
I. Lí do chọn đề tài...............................................................................................1
II. Mục đích của đề tài............................................................................................1
III. Đối tượng và phạm vi nghiên cứu....................................................................1
IV. Phương pháp nghiên cứu..................................................................................1
PHẦN 2. NỘI DUNG SÁNG KIẾN KINH NGHIỆM.............................................2
I. Cơ sở lý luận.......................................................................................................2
I.1. Bài tốn tìm kiếm..........................................................................................2
I.2. Thuật tốn tìm kiếm nhị phân.......................................................................2
I.3. Hiệu quả của tìm kiếm nhị phân trong các bài tốn tìm kiếm......................2
II. Vận dụng thuật toán giải quyết tối ưu một số bài toán ....................................4
II.1. Một số dạng bài sử dụng thuật toán tìm kiếm nhị phân..............................4
II.2. Một số bài tốn tìm kiếm nhị phân cơ bản..................................................9
II.3. Một số bài toán nâng cao sử dụng thuật tốn tìm kiếm nhị phân..............12
III. . Hiệu quả của sáng kiến.............................................................................18
PHẦN 3. KẾT LUẬN.............................................................................................19
1
PHẦN 1. MỞ ĐẦU
I. Lí do chọn đề tài
Hiện nay tài liệu dạng chuyên đề nâng cao phục vụ cho việc bồi dưỡng học
sinh giỏi môn Tin học là chưa thật sự đầy đủ và tổng quát, đặc biệt là những
chuyên đề khá mới và rất khó, giờ đã được đưa vào các đề thi học sinh giỏi tỉnh
như: Chia để trị, Quy hoạch động, …
Từ thực tiễn giảng dạy tin tại trường THPT tôi thấy rằng để đạt hiệu quả cao
trong bồi dưỡng học sinh giỏi, cần có cách thiết kế bài giảng cho phù hợp với nội
dung kiến thức dựa trên tài liệu chuyên đề đầy đủ rõ ràng từ lýthuyết đến bài tập
và theo đúng xu thế chung của các kì thi học sinh giỏi các cấp hiện nay và trong tương
lai, để mang lại thành tích cao cho đội tuyển học sinh giỏi trong các kì thi.
Xuất phát từ cơ sở trên, tôi chọn đề tài “ Vận dụng thuật tốn tìm kiếm
nhị phân vào giải quyêt tối ưu một số bài toán” , sáng kiến này sẽ giúp học sinh
của trường THPT Cầm Bá Thước vận dụng các kiến thức vào làm tốt các dạng đề
thi học sinh giỏi tỉnh có liên quan đến phương pháp chia để trị, phục vụ cho việc
bồi dưỡng học sinh giỏi của trường.
II. Mục đích của đề tài
- Mục tiêu chính của đề tài là giúp học sinh nắm được thuật tốn tìm kiếm
nhị phân; Tăng khả năng tư duy thuật tốn, phát huy tính sang tạo, Năng lực vận
dụng các kiến thức đã học vào giải quyết các bài tốn.
- Giúp cho việc ơn thi học sinh giỏi đạt kết quả cao.
- Tạo ra nguồn tài liệu tham khảo về phương pháp cũng như thuật toán nhằm
hỗ trợ cho học sinh, giáo viên dạy bồi dưỡng học sinh giỏi tin học.
III. Đối tượng và phạm vi nghiên cứu
1. Đối tượng nghiên cứu
- Thuật tốn tìm kiếm nhị phân và vận dụng vào các bài toán tối ưu sử dụng
ngơn ngữ lập trình C++
- Học sinh giỏi tin khối 11, 12, giáo viên giảng dạy học sinh giỏi tin
2. Phạm vi nghiên cứu
Sử dụng Thuật tốn tìm kiếm nhị phân để giải một số bài toán bồi dưỡng học
sinh giỏi tin học 11, 12.
IV. Phương pháp nghiên cứu
- Thu thập, phân tích các tài liệu và thơng tin liên quan đến Thuật tốn tìm
kiếm nhị phân
- Lựa chọn một số bài tốn để sử dụng Thuật tốn tìm kiếm nhị phân.
- Thiết kế các bài toán đã được lựa chọn trong chương trình tin học 11 để bồi
dưỡng học sinh giỏi.
2
PHẦN 2. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
I. Cơ sở lý luận
I.1. Bài tốn tìm kiếm
Tìm kiếm là việc thường xảy ra trong cuộc sống, chẳng hạn tìm kiếm học
sinh trong trường học, tìm kiếm đồ trong siêu thị, tìm kiếm kiến thức trên mạng
Internet,…Tổng quát, trong một phạm vi nào đó, một tập hợp các đối tượng nào
đó, cần tìm đối tượng cụ thể thỏa mãn yêu cầu nào đó. Các bài tốn tìm kiếm
thường đưa về tìm kiếm phần tử trong mảng chỉ số.
I.2. Thuật tốn tìm kiếm nhị phân
Chia để trị là một tư tưởng rất phổ biến trong cuộc sống và được áp dụng rất
hiệu quả trong Tin học. Tư tưởng cơ bản của phương pháp chia để trị là Người ta
phân bài toán thành các bài toán con, các bài toán con lại tiếp tục được phân thành
các bài toán con nhỏ hơn, cứ tiếp tục như thế cho đến khi ta nhận được bài tốn
con đã có thuật giải hoặc có thể dễ dàng đưa ra thuật giải. Sau đó kết hợp nghiệm
của các bài toán con để nhận được nghiệm của bài toán con lớn hơn để cuối cùng
nhận được nghiệm của bài tốn cần giải. Thơng thường các bài tốn con được phân
chia là cùng dạng với bài toán ban đầu chỉ có cỡ của chúng là nhỏ hơn.
Thuật tốn tìm kiếm nhị phân dựa trên tư tưởng chia để trị. Với những dãy
số đã được sắp xếp, ta thường tìm cách thu hẹp phạm vi tìm kiếm bằng cách phân
đơi vùng tìm kiếm, xác định xem khóa tìm kiếm ở phần đầu hay phần cuối. Sau đó
thu hẹp rồi lại phân đơi. Q trình đó xảy ra cho đến khi khơng tồn tại vùng tìm
kiếm hoặc tìm được số cần tìm.
Thuật tốn tìm kiếm nhị phân thường phát biểu dưới bài toán sau:
“ Cho mảng n phần tử đã được sắp tăng dần và một phần tử x. Tìm xem x có
trong mảng hay khơng”
u cầu: Thuật tốn này chỉ có thể được dung khi dãy số được sắp xếp đơn
điệu theo thứ tự tăng hoặc giảmdần.
I.3. Hiệu quả của tìm kiếm nhị phân trong các bài tốn tìm kiếm
Trong ngơn ngữ lập trình C++, việc sử dụng hàm rất phổ biến và dung hàm
rất dễ dàng mà không phải nhớ một đoạn lệnh dài mà lại có thể tối ưu việc sắp xếp.
Do vậy ta thường dung hàm sort để tối ưu việc sắp xếp các phần tử rồi dung thuật
tốn tìm kiếm nhị phân. Cấu trúc câu lệnh sort như sau:
sort(a,a+n);// sắp xếp mảng a tăng dần từ phần tử 0 đến phần tử thứ n-1
Hoặc sort(a+1, a+n+1);// sắp xếp mảng a tăng dần từ phần tử thứ 1 đến phần
tử thứ n
Hoặc sort(a,a+n,greater<int>());//sắp xếp mảng a giảm dần từ phần tử 0 đến n-1
Hàm sort này có độ phức tạp O(nlogn), sử dụng thuật toán sắp xếp nhanh
Quicksort kết hợp với Selection Sort, có tốc độ sắp xếp nhanh hơn các thuật toán
sắp xếp nổi bọt hay sắp xếp chọn, sắp xếp chèn, hồn tồn có thể sắp xếp được
dưới n=100.000 phần tử thì số bước sắp xếp khoảng 1.700.000, máy tính hồn tồn
có thể thực hiện dưới 1 giây.
3
Cũng có trường hợp mảng tìm kiếm là mảng thường đã sắp xếp sẵn theo giá
trị nên ta dễ dàngtìm kiếm trên mảng đã được sắp xếp.
Tư tưởng của thuật tốn: chọn phần tử ở vị trí giữa làm chốt, chia dãy thành
2 phần có kích thước nhỏ hơn. Sau đó so sánh phần tử cần tìm x với chốt, nếu x
lớn hơn chốt tìm ở nửa sau của dãy, nếu x nhỏ hơn chốt tìm ở nửa trước của dãy
(áp dụng với dãy tăng), quá trình trên tiếp tục cho tới khi tìm được x hoặc dãy chia
khơng cịn phần tử nào.
Thuật toán:
Cho dãy số: A{n} gồm n phần tử ngun tăng dần, tìm phần tử có giá trị
bằng x
Bước 1:Xét đoạn mảng a[L..H] ban đầu L=1; H=n;
Bước 2: Phần tử chốt đầu tiên được chọn giữa dãy. k=(L+H)/2;
Bước 3: so sánh x với a[k], nếu a[k]=x thì đó là nghiệm, đưa ra nghiệm và
kết thúc tìm kiếm
Bước 4: Nếu a[k]>x ta lấy nửa đầu, thực hiện tìm kiếm trên đoạn a[L;k-1]
Bước 5: Nếu a[k]
Bước 6: quay lại bước 2
Có 2 giải thuật đệ qui và khử đệ qui để thực hiện thuật toán
Cách 1: Giải thuật đệ qui
int tim(int L,intH,int x)
{
if (L<=H)
{
int k=(L+H)/2;
if (a[k]==x) return k;
if (a[k]>x) return tim(L,k-1,x);
return tim(k+1,H,x);
}
Cách 2: Giải thuật khử đệ qui
int tim(short L,short H)
{
int k;
while(L<=H)
{
k=(L+H)/2;
if(a[k]==x)
{
return k;
}
if(a[k]>x) H=k-1;
else L=k+1;
4
}
return 0;
}
Độ phức tạp:
Để tìm kiếm một phần tử trong mảng, với cách tìm kiếm tuần tự 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ớ imảng đơn điệu, ta dung 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)
II. Vận dụng thuật toán giải quyết tối ưu một số bài toán
II.1. Một số dạng bài sử dụng thuật tốn tìm kiếm nhị phân
Dạng 1: Cho mảng A tăng dần, tìm vị trí của phần tử có giá trị bằng x
int BS (int dau, int cuoi, int x)
{
while (dau<=cuoi)
{
int giua = (dau + cuoi)/2;
if (a[giua]==x) dau = giua + 1;
else cuoi = giua – 1;
}
Return -1;
}
Với dạng này, nếu tìm thấy x thì
Dau sẽ là vị trí của phần tử nhỏ nhất, đầu tiên lớn hơn x trong mảng
Cuoi sẽ là vị trí của phần tử lớn nhất, cuối cùng bé hơn x trong mảng
Khi đó, việc tìm kiếm sẽ tiến sát đến 2 phần tử kẹp giữa giá trị x trong dãy.
Tính chất này khá thú vị nhưng khó ứng dụng vì nó chỉ đúng khi x được tìm thấy.
Đây là dạng phổ biến nhấ ttrong các bài tốn tìm kiếm nhị phân.
Ví dụ: Cho dãy số (an), với n là số tự nhiên, ai là các số ngun dương. Tìm
phần tử trong dãy an có giá trị bằng x.
Dữ liệu: vào từ bàn phím
- Dịng đầu tiên ghi số nguyên dương n<=105
- Dòng thứ 2 ghi n số nguyên dương phân biệt ai <=1018
- Dòng 3 ghi số nguyên dương T <= 105
- T dòng tiếp theo ghi mỗi dòng ghi số nguyên dương x
Kết quả: ghi ra màn hình T dịng, mỗi dịng thứ I ghi Y nếu trong dãy (a n) tồn tại
phần tử x, ghi N nếu không tồn tại.
Input
Output
5
10
1
5
1
11
33
10
12
2
3
4
7
6
5
8
9
Y
10 N
N
Y
N
Phân tích: Trước hết cần sắp xếp dãy tăng dần bằng hàm sort. Sửa đổi hàm
tim(): nếu tồn tại x thì trả về vị trí khác 0, cịn nếu khơng tồn tại x thì trả về 0. Do
đó ta chỉ cần xét giá trị hàm bằng 0 hay không thì trả về Y hoặc N.
Chương trình:
#include <bits/stdc++.h>
using namespace std;
long longN,i,a[100000];
int tim(short L,shortH,int k)
{
int x;
while(L<=H)
{
x=(L+H)/2;
if(a[x]==k)
{
return 1;
}
if(a[x]>k) H=x-1;
else L=x+1;
}
return 0;
}
int main()
{
cin>>N;
for(i=1;i<=N;i++)
cin>>a[i];
sort(a,a+n+1);
int t,m;
cin>>m;
for (i=1;i<=m;i++)
{
cin>>t;
6
if (tim(1,N,t)==0) cout<<"N";
else cout<<"Y";
}
}
Dạng 2: Cho mảng A tăng dần, tìm vị trí của phần tử đầu tiên có giá trị
nhỏ nhất mà lớn hơn hoặc bằng x.
int BS (int dau, int cuoi, int x)
{
int ans =-1;
While (dau<=cuoi)
{
int giua = (dau + cuoi)/2;
if (a[giua]>=x)
{
ans = giua;
cuoi = giua – 1;
}
else dau = giua +1;
}
return ans;
}
Nếu muốn tìm vị trí của phần tử đầu tiên lớn hơn x, chỉ cần thay điều kiện
thỏa mãn thành a[giua]>x
Ví dụ: Cho dãy số un = n2+1, với n là số tự nhiên. Tìm phần tử đầu tiên của
dãy un có giá trị nhỏ nhất lớn hơn hoặc bằng x.
Dữ liệu: Vào từ bàn phím
- Dòng đầu ghi số nguyên dương n<=106
- Dòng 2 ghi số nguyên dương T<=105
- T dòng tiếp theo mỗi dòng ghi số nguyên dương x
Kết quả ghi ra màn hình T dòng, dòng thứ I ghi phân tử ui tương ứng nhỏ nhất
lớn hơn hoặc bằng x.
Input
Output
10
2
5
5
1
10
5
26
10
50
20
50
7
Phân tích: Với điều kiện đã cho thì dãy đã có tính chất là một dãy tăng. Ta
cần cải tiến hàm tim() bằng cách thay điều kiện a[giua]>=k thì lưu lại chỉ số và thu
hẹp phạm vi tìm kiếm lấy đoạn sau, cịn khơng thì lấy đoạn đầu.
Chương trình:
#include <bits/stdc++.h>
using namespace std;
int N,i,a[10000],T;
int tim(short L,shortH,int k)
{
int x;intans=-1;
while(L<=H)
{
x=(L+H)/2;
if(a[x]>=k)
{
ans=x;
H=x-1;
}
else L=x+1;
}
return ans;
}
int main()
{ cin>>N;
cin>>T;
for(i=1;i<=N;i++)
a[i]=i*i+1;
int t;
for (i=1;i<=T;i++)
{
cin>>t;
cout<
}
Dạng 3: Cho mảng A tăng dần, tìm vị trí của phần tử cuối cùng có giá
trị lớn nhất mà nhỏ hơn hoặc bằng x
int BS (int dau, int cuoi, int x)
{
int ans= -1;
while (dau<=cuoi)
{
int giua = (dau+cuoi)/2;
8
if (a[giua]<=x)
{
ans = giua;
dau = giua +1;
}
else cuoi = giua -1;
}
return ans;
}
Nếu muốn tìm vị trí của phần tử đầu tiên nhỏ hơn x, thay điều kiện thỏa mãn
thành a[giua]
mà nhỏ hơn hoặc bằng x
Dữ liệu vào từ bàn phím
- Dịng đầu ghi số nguyên dương n<=105
- Dòng 2 ghi n số nguyên dương phân biệt ai<=1018
- Dòng 3 ghi số nguyên dương T<=105
- T dòng kế tiếp ghi mỗi dòng ghi số ngun dương x
Kết quả ghi ra màn hình T dịng, dịng thứ I ghi phần tử có giá trị lớn nhất
mà nhỏ hơn hoặc bằng x, nếu không tồn tại thì ghi ra -1.
Input
Output
10
1
1 11 3 4 7 6 5 8 9 10 11
2
2
12
Phân tích: Đầu tiên dung hàm sort để sắp xếp mảng tăng dần. Sau đó ta cải
tiến hàm tim(), tìm phần tử có giá trị lớn nhất mà nhỏ hơn k thì thay điều kiện
a[giua]<=k
Chương trình:
#include <bits/stdc++.h>
using namespace std;
long longN,i,a[100000],T;
int tim(short L,shortH,int k)
{
int x;intans=-1;
while(L<=H)
{
x=(L+H)/2;
if(a[x]<=k)
{
ans=x;
9
L=x+1;
}
else H=x-1;
}
return ans;
}
int main()
{ cin>>N;
for(i=1;i<=N;i++)
cin>>a[i];
sort(a,a+N+1);
int t;
cin>>T;
for (i=1;i<=T;i++)
{
cin>>t;
cout<
}
II.2. Một số bài tốn tìm kiếm nhị phân cơ bản
Bài 1. 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.
Phân tích:
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.
- 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.
Chương trình:
#include<bits/stdc++.h>
using namespace std;
string xau;
int l;
int timkhong(int L,int H)
{
int g;
while (L<=H)
{
g=(L+H)/2;
10
if (xau[g]=='0'&&xau[g+1]=='1')
return g;
else if (xau[g]=='0') L=g+1;
else H=g-1;
}
return 0;
}
int main()
{
cin>>xau;
int n=xau.size(); l=1;xau=' '+xau;
cout<
Bài 2: Tìm kiếm nhị phân trên dãy số nguyên với nhiều câu hỏi, mỗi dòng là
1 giá trị x
Dữ liệu vào:
- Dòng đầu tiên gồm duy nhất một số nguyên dương � (� ≤ 105);
- Dòng thứ hai là một dãy số nguyên � tăng dần gồm � phần tử �1, �2, … , ��
(|�� | ≤ 109);
- Dòng thứ ba là một số nguyên dương� (� ≤ 105) − số lượng câu hỏi;
- � dòng tiếp theo, mỗi dòng là một số nguyên � (|�| ≤ 109).
Dữ liệu ra: Gồm � dịng, mỗi dịng là vị trí số nguyên � tương ứng trên
dãy � hoặc in ra 0 nếu � khơng nằm trên dãy.
Ví dụ
Input
Output
5
1
-4 -1 7 9 12
0
3
4
-4
2
9
Phân tích: Nếu sử dụng thuật tốn tìm kiếm tuần tự, độ phức tạp khi tìm
kiếm sẽ là O(n2) với 105 câu hỏi Q và mỗi câu hỏi ta sử dụng 105 phép tính so sánh
thì máy tính phải thực hiện là10 10, máy tính sẽ khơng cho ra kết quả trong thời gian
1 giây. Sử dụng tính chất tăng dần để tìm kiếm nhị phân với độ phức tạp O(log 2n),
ta có thể sử dụng thuật tốn với nhiều lần tìm kiếm, ở đâycó Q câu hỏi tương ứng
với Q lượt tìm kiếm, mỗi lần ta tìm kiếm một số x thì độ phức tạp giảm cịn là
nO(log2n), tương đương105log2105 xấp xỉ 17.105 phép tốn, máy tính có thể xử lý
trong 1 giây. Ở đây thuật toán được cài đặt theo kiểu đệ quy.
Chương trình:
#include <bits/stdc++.h>
using namespace std;
11
int n,a[1000005],q,x,i;
int find (int l, int r, int m)
{
int mid=(l+r)/2;
if (l<=r)
{
if (a[mid]==m) return mid;
if (a[mid]>m) find(l,mid-1,m);
else find(mid+1,r,m);
}
else return 0;
}
int main()
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
cin>>q;
for(i=1;i<=q;i++)
{
cin>>x;
cout<
}
Bài 3: Cho dãy số nguyên gồm � phần tử �1, �2, … ,�� có tính chất
� 1 ≤ � 2 ≤ ⋯ ≤ � �.
Yêu cầu: Gồm � câu hỏi, mỗi câu hỏi là một số nguyên �, bạn hãy đếm số
lượng giá trị � xuất hiện trên dãy �� với mỗi � tươn gứng.
Dữ liệu vào:
- Dòng đầu tiên là một số nguyên dương � ( � ≤ 105);
- Dịng thứ hai là dãy số ngun �� khơng giảm gồm � phần tử �1, �2, … ,��
(|��| ≤ 109);
-Dòng thứ ba là số nguyên dương � (� ≤ 105);
-� dòng tiếp theo, mỗi dòng là một số nguyên � (|�| ≤ 109).
Dữ liệu ra: Gồm � dòng, mỗi dòng là số lượng số nguyên � trên dãy � với
� tương ứng. Vídụ:
Input
Output
5
0
-1 0 2 2 4
2
2
5
2
12
Phân tích: Bài này mở rộng hơn so với bài 2 ở chỗ đếm số phần tử = x của
dãy. Ta phải xác định đoạn các phần tử =x bằng cách cải tiến hàm find. Ta lấy vị trí
phần tử đầu tiên sát về bên trái bằng hàm floor. Nếu a[i]
Sau đó ta chỉ cần dung thêm biến đếm để xác định độ dài đoạn =x nữa thơi.
Chương trình:
#include <bits/stdc++.h>
using namespace std;
int n,a[1000005],q,x,i;
int find(int l,intr,int m)
{
while (l
if (a[mid]
}
return l;
}
int main()
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
cin>>q;
for(i=1;i<=q;i++)
{
cin>>x;
int t=find(1,n,x);
if (t==0) cout<<'0'<<'\n';
else
{ int d=0,j=t;
while (a[j]==x) {d++;j++;}
cout<
}
}
II.3. Một số bài toán nâng cao sử dụng thuật tốn tìm kiếm nhị phân
Bài 1. Bài toán Ham ming
Dãy số nguyên dương tăng dần, trong đó ước ngun tố của mỗi số khơng q
5 được gọi là dãy Hamming.
Như vậy, 10 = 2×5 sẽ là một số trong dãy Hamming, cịn 26 = 2×13 khơng
thuộc dãy Hamming.
13
Phần đầu của dãy Hamming là 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, . . .
Yêu cầu: Cho số nguyên x (1 ≤ x ≤ 109). Hãy xác định số thứ tự của x trong
dãy Hamming.
Dữ liệu vào:Từ tệp văn bản HAMMING.INP:
- Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 105),
- Các dòng tiếp theo mỗi dòng chứa một số nguyên x.
Kết quả ra: Ghi ra tệp văn bản HAMMING.OUT: kết quả mỗi test đưa ra
trên một dòng dưới dạng số nguyên hoặc thong báo -1 nếu khơng tồn tại số đó
trongdãy Hamming.
Vídụ:
HAMMING.INP
HAMMING.OUT
11
1
1
2
2
6
6
7
-1
8
7
9
8
10
9
11
-1
12
10
13
-1
14
-1
Phân tích: Bởi x<=109 là một số lớn, số phần tử <=10 5 nên ta cần tối ưu
thuật toán. Dãy Hamming là một dãy số có qui luật và có tính chất tăng dần. Ta tìm
cách xây dựng mảng hamming theo giá trị, sắp xếp mảng này tăng dần, sau đó sử
dụng thuật tốn tìm kiếm nhị phân trên mảng này.
Chương trình:
#include <bits/stdc++.h>
using namespace std;
long longhamming[7000] = {};
long longfind(long longx,long long y, long longgt)//hàm tìm kiếm nhị phân
{
long long res = (x + y) / 2;
if ( x<= y ){
if (hamming[res ] == gt)
return res;
if (hamming[res] >gt)
return find(x , res - 1 , gt);
else
14
return find(res + 1 , y , gt);
return -1;
}
void init()//xâydựngmảng hamming
{
hamming[1] = 1;
hamming[0] = 0;
long long dem = 1,i = 1, j = 1, k = 1;
unsigned long longa,b,c,temp;
for(long longi = 0; i<= 29 ; i++)
{
a = pow (2,i);
for (long long j = 0 ; j <= 18 ; j++)
{
b = pow (3,j);
for (long long k = 0; k <= 12; k++)
{
c = pow (5,k);
temp = a*b*c;
if (temp <= 1000000000)
{
hamming[dem] = temp;
dem++;
}
}
}
}
l = dem - 1;
sort(hamming + 1,hamming + dem);//sắpxếpmảnghamming
}
int main()
{
freopen ("hamming.inp", "r", stdin);
freopen ("hamming.out", "w", stdout);
long longi,n,k;
cin>> n;
init();
for (i = 0; i
cin>> k;
cout<< find(1,l,k) << '\n';
}
15
return 0;
}
Bài 2. Bài tốn AMB
Tại vương quốc HT, có N thành phố và 1 con đường duy nhất xuất phát từ thành phố 1
lần lượt đi qua các thành phố 2, 3, 4,…, N. HT muốn xây K bệnh viện ở K thành phố
trong vương quốc mình. Gọi Di = quãng đường ngắn nhất từ thành phố I đến bệnh viện
gần nhất. D = Max{D1,, D2,…, DN}
Bạn hãy viết chương trình tìm D min?
INPUT: AMB.INP
Dịng 1: N, K
Dịng 2: N – 1 số là khoảng cách giữa các thành phố lien tiếp. Số thứ I là khoảng
cách giữa thành phố I và I + 1.
OUTPUT: AMB.OUT
Giá trị nhỏ nhất của D
Hạn chế:
1<= K <= N <= 1000
Di<= 1000
Ví dụ:
AMB.INP
AMB.OUT
4 2
3
3 5 2
Phân tích: Tìm kiếm nhị phân đáp án trong đoạn (0, ∞), với mỗi giá trị tìm
kiếm R, ta kiểm tra tính “xây dựng được” của R như sau (thuật toán tham lam):
- Xét các thành phố từ 1..N, với mỗi thành phố I chưa được “phủ sóng” bởi
một bệnh viện nào đó, ta tiến hành đặt một bệnh viện mới tại thành phố xa nhất về
phía N cịn “phủ sóng” được tới I (khoảng cách tới I khơng q R) và đi “phủ
sóng” các thành phố k sau j mà có khoảng cách tới j khơng vượt q R.
- Kết thúc q trình “phủ sóng”, nếu số bệnh viện phải xây dựng không vượt
quá K, ta cập nhật kết quả.
Chương trình:
#include<bits/stdc++.h>
using namespace std;
long longa[10005], n, k, res;
void doc()
{
int i;
cin>>n>>k;
for (i=1;i<=n-1;i++)
cin>>a[i];
}
16
bool kt(long long x)//kiểm tra q trình “phủ sóng”
{
long longi,j,kc;
j=0;i=1;
do
{
kc=0;
while(kc<=x&&i<=n)
{
kc=kc+a[i];
i++;
}
j++;i--;
kc=0;
while (kc<=x&&i<=n)
{
kc=kc+a[i];
i++;
}
i--;
if (i==n) return true;
i++;
}
while (j!=k);
return false;
}
void tim()
{
long longl,r,i,mid;
l=0;r=0;res=0;
for (i=1;i<=n-1;i++)
r=r+a[i];
while (l<=r)// tìm kiếm nhị phân trong đoạn (l,r)
{
mid=(l+r)/2;
if (kt(mid))
{
res=mid;
r=mid-1;
}
else l=mid+1;
17
}
}
int main()
{
freopen ("amb.inp", "r", stdin);
freopen ("amb.out", "w", stdout);
doc();
tim();
cout<
Bài 3. Cặp số
Cho dãy N số nguyên. Tìm số lượng các cặp số mà có tổng lớn hơn hoặc
bằng số K cho trước.
INPUT: CAPSO.INP
- Dòng đầu ghi 2 số N, K. (2 <= N <= 105, -109<= K, Ai<= 109)
- Dòng 2 ghi N số A1, A2...AN.
OUTPUT: CAPSO.OUT
- Ghi kết quả tìm được. Nếu kết quả >= 109 thì ghi ra phần dư khi chia cho 109.
Ví dụ:
Capso.inp
Capso.out
56
4
2 -3 4 -1 7
Phântích:
Nhìn vào số phần tử <100000 nên ta có thể sử dụng hàm sort. Trước hết ta
cần sắp xếp dãy số tăng dần. Sau đó với mỗi chỉ số I từ 1 đến n-1 ta tìm kiếm xem
có bao nhiêu phần tử từ i+1 đến n và có giá trị bằng x-a[i]. Sử dụng thuật tốn tìm
kiếm nhị phân để tối ưu việc tìm kiếm.
Chương trình:
#include<bits/stdc++.h>
using namespace std;
long longa[100010],n,k,dem;
void doc()
{
long longi;
cin>>n>>k;
for(i=1;i<=n;i++)
cin>>a[i];
}
long longtim(long long vt,long long x)// tìm vị trí số x trong đoạn (vt,n)
18
{
long longl,r,mid;
long long res=0;
l=vt+1;
r=n;
while (l<=r)
{
mid=(l+r) /2;
if (a[mid]
{r=mid -1;
res=n-mid+1;
}
}
return res;
}
void xuli()
{
long longi,tg;
dem=0;
for (i=1;i<=n;i++)
{
tg=k-a[i];
dem=dem+tim(i,tg);
if (dem>=1000000000) dem=dem %1000000000;
}
}
int main()
{
freopen ("capso.inp", "r", stdin);
freopen ("capso.out", "w", stdout);
doc();
sort(a+1,a+n+1);
xuli();
cout<
III. . Hiệu quả của sáng kiến
Sau khi sáng kiến kinh nghiệm này được GV áp dụng cho đội tuyển HSG
tại trường THPT Cầm Bá Thước đạt được kết quả như sau:
100% học sinh đội
tuyển khi gặp các bài toán cùng dạng đã nhận thức được thực trạng khơng giải
quyết các test lớn của chương trình, đồng thời biết vận dụng thuật tốn tìm kiếm
nhị phân để giải quyết bài toán.
19
PHẦN 3. KẾT LUẬN
Qua các bài toán trên chúng ta thấy được phần nào hiệu quả của phương
pháp tìm kiếm nhị phân. Tuy nhiên, với cách sử dụng kĩ thuật này vẫn chưa phải là
thuật toán tối ưu nhất trong tìm kiếm, khơng phải bài tốn nào ta cũng áp dụng
được thuật toán này mà phải tùy vào nội dung bài tốn để có hướng áp dụng cho
phù hợp. Việc này đòi hỏi học sinh phải được tiếp xúc với rất nhiều các bài tốn
tương tự, khi đó kỹ năng áp dụng thuật tốn vào các bài tập mới hồn thiện.
Trong đề tài của mình tơi đã cố gắng đưa ra được một số dạng bài tập
thường gặp sử dụng thuật tốn tìm kiếm nhị phân, mong rằng sẽ giúp ích cho giáo
viên và học sinh trong quá trình giảng dạy và học tập.
Do thời gian có hạn nên nội dung đề tài chắc chắn cịn nhiều thiếu sót, rất
mong nhận được phản hồi góp ý từ đồng nghiệp để có thể hồn thiện hơn và áp
dụng đề tài vào giảng dạy.
XÁC NHẬN
CỦA THỦ TRƯỞNG ĐƠN VỊ
Thường Xuân, ngày 26 tháng 5 năm
2022
Tơi xin cam đoan đây là SKKN của
mình viết, không sao chép nội dung của
người khác.
20
1.
2.
3.
4.
5.
TÀI LIỆU THAM KHẢO
SáchTàiliệuchuyên tin họcquyển 1 – HồSĩĐàm
SáchBàitậptàiliệuchuyên tin họcquyển 1 – HồSĩĐàm
Trang web http:\\laptrinhphothong.vn
Trang web http:\\vnoi.info
Trang web http:\\ntucoder.net
21
DANH MỤC
SÁNG KIẾN KINH NGHIỆM ĐÃ ĐƯỢC HỘI ĐỒNG SKKN
NGÀNH GIÁO DỤC VÀ ĐÀO TẠO HUYỆN, TỈNH VÀ CÁC CẤP
CAO HƠN XẾP LOẠI TỪ C TRỞ LÊN
Họ và tên tác giả: Lê Thanh Chương
Chức vụ và đơn vị công tác: Phó Hiệu trưởng Trường THPT Cầm Bá Thước
Cấp đánh
giá xếp loại
TT
Tên đề tài SKKN
(Ngành GD cấp
huyện/tỉnh;
Tỉnh...)
Kết quả
đánh giá
xếp loại
(A, B,
hoặc C)
Năm học
đánh giá
xếp loại
1.
Một số biện pháp thực hiện
phong trào thi đua “Xây dựng
trường học thân thiện, học sinh
tích cực” ở trường THPT Thường
Xuân 2
Sở GD&ĐT
Thanh Hóa
C
2008
2.
Một số biện pháp quản lý nhằm
nâng cao chất lượng công tác thi
đua, khen thưởng trong cán bộ
giáo viên ở trường THPT Thường
Xuân 2
Sở GD&ĐT
Thanh Hóa
C
2012
3.
Một số biện pháp quản lý hoạt
động trải nghiệm sáng tạo ở
trường THPT Cầm Bá Thước
Sở GD&ĐT
Thanh Hóa
C
2020
