Phương pháp tìm số

PHƯƠNG PHÁP TÌM SỐ

Bài toán: Cho các ràng buộc A, B, C, ... hãy tìm một số x thỏa các ràng buộc đã cho

Có hai phương pháp cơ bản để giải quyết bài toán trên.
- Phương pháp thứ nhất là xét từng số x, rồi kiểm tra có thỏa điều kiện A, B, C, ... không, hay cũng có thể chọn 1 điều kiện A làm chuẩn để giới hạn miền x rồi mới quét x để kiểm tra xem x có thỏa điều kiện B, C, ... không
- Phương pháp thứ hai làm xem x gồm có n chữ số: x=x1, x2,...,xn. Rồi tìm từng chữ số một x1, rồi x2, ... cuối cùng là xn. Hẫy cũng có thể tìm x1, rồi tìm x1x2, rồi x1x2x3, ... rồi cuối cùng là x1x2...xn

Tóm tắt hai phương pháp:
Phương pháp 1: xét miền giá trị của x
- Chọn điều kiện A để tìm các số có thể của x thỏa điều kiện A
- Xét các số x thỏa điều kiện A và kiểm tra xem có thỏa điều kiện B, C, ... không

Phương pháp 2: tìm từng chữ số của x
- Xem x=x1,x2, ..., xn
- Xét x1 có bao nhiêu khả năng, chọn những x1 nào thỏa điều kiện A, B, C, ...
- Xét x1x2 có bao nhiêu khả năng, chọn x1x2 nào thỏa điều kiện A, B, C, ...
...
Cho đến khi tìm được giá trị x cần tìm

Tìm kiếm nhị phân và ứng dụng

TÌM KIẾM NHỊ PHÂN

Bài toán 1. Cho dãy a[1], a[2], ..., a[n] không giảm. Hãy tìm vị trí trong dãy a có giá trị bằng x.
Thuật toán: binary_search(a.begin(), a.end(), x)



Bài toán 2. Cho dãy a[1], a[2], ..., a[n] không giảm. Hãy tìm vị trí nhỏ nhất trong dãy a có giá trị lớn hơn hay bằng x.
Thuật toán: lower_bound(a.begin(), a.end(), x)


Bài toán 3. Cho dãy a[1], a[2], ..., a[n] không giảm. Hãy tìm vị trí nhỏ nhất trong dãy a có giá trị lớn hơn x.
Thuật toán: upper_bound(a.begin(), a.end(), x)


Ứng dụng của lower_bound và upper_bound
1. Tìm đoạn phần tử giá trị bằng x
vector<int>::interator l, r;
int left, right;

l = lower_bound(a.begin(), a.end(), x);
r = upper_bound(a.begin(), a.end(), x);

left = l-x.begin();
right = r-x.begin()-1;

2. Đếm số lượng phần tử nhỏ hơn x
left = lower_bound(a.begin(), a.end(), x);
nums= left-a.begin()-1;

2. Đếm số lượng phần tử lớn hơn x
right = lower_bound(a.begin(), a.end(), x);
nums= a.end()-right;