SKKN Vận dụng thuật toán 2 con trỏ vào giải một số bài toán bồi dưỡng học sinh giỏi, thi vào chuyên phan trên ngôn ngữ lập trình C++ và Python

 kiếm nhị phân hoạt động trên các mảng đã được sắp xếp. Hoạt động theo các trình tự:
So sánh một phần tử đứng chính giữa mảng với giá trị cần tìm.
Nếu bằng nhau, vị trí của nó trong mảng sẽ được trả về. Nếu giá trị cần tìm nhỏ hơn phần tử này, quá trình tìm kiếm tiếp tục ở nửa nhỏ hơn của mảng.
Nếu giá trị cần tìm lớn hơn phần tử ở giữa, quá trình tìm kiếm tiếp tục ở nửa lớn hơn của mảng. Bằng cách này, ở mỗi phép lặp, thuật toán có thể loại bỏ nửa mảng mà giá trị cần tìm chắc chắn không xuất hiện
Code viết bằng ngôn ngữ lập trình C++
Code viết bằng ngôn ngữ lập trình Python
Hướng giải quyết 3: Tìm kiếm bằng 2 con trỏ - Two Pointe Độ phức tạp thời gian sẽ là: O(n).
Phân tích:
Trước tiên, ta có một chút nhận xét sau:
a[1]<a[2]<a[3]<a[4]<a[5]<a[6]<a[7] vì dãy a tăng dần.
a[1]+a[7]=17>X⇒X<a[1]+a[7]<a[2]+a[7]<a[3]+a[7]<a[4]+a[7]<a[5]+a[7
]<a[6]+a[7].
Có thể thấy, tổng của a[7] với các phần tử khác trong dãy đều lớn hơn X. Vì thế ta không quan tâm đến a[7] nữa.
a=[2, 5, 6, 8, 10, 12, 15]
a[1]+a[6]=14<X⇒a[1]+a[2]<a[1]+a[3]<a[1]+a[4]<a[1]+a[5]<a[1]+a[6]<
X.
Có thể thấy, tổng của a[1] với các phần tử khác trong các phần tử ta quan tâm
đều nhỏ hơn X. Vì thế ta không quan tâm đến a[1] nữa.
a=[2, 5, 6, 8, 10, 12, 15]
a[2]+a[6]=17>X⇒X<a[2]+a[6]<a[3]+a[6]<a[4]+a[6]<a[5]+a[6].
Có thể thấy, tổng của a[6] với các phần tử khác trong các phần tử ta quan tâm đều lớn hơn X. Vì thế ta không quan tâm đến a[6] nữa.
a=[2, 5, 6, 8, 10, 12, 15]
a[2]+a[5]=15<16⇒ a[2]+a[5]<a[3]+a[5]<a[4]+a[5] tương tự ta không cần quan tâm đến a[2] nữa.
a=[2, 5, 6, 8, 10, 12, 15] ta có a[3]+a[5]=16=X là kết quả bài toán
Như vậy, tại một thời điểm bất kỳ, những phần tử chúng ta cần quan tâm đến sẽ là các phần tử trong đoạn [i, j] nào đó.
Ý tưởng:
Nếu i=j, trong mảng A không tồn tại hai vị trí khác nhau mà tổng hai phần tử ở đó có giá trị là X.
Ngược lại:
Nếu a[i]+a[j]=X, ta đã tìm được hai vị trí cần tìm (i và j).
Nếu a[i]+a[j]<X, không quan tâm đến a[i] nữa và các phần tử chúng ta cần quan tâm đó là các phần tử trong đoạn [i+1, j].
Nếu a[i]+a[j]>X, không quan tâm đến a[j] nữa và các phần tử chúng ta cần quan tâm đó là các phần tử trong đoạn [i, j−1].
Giải pháp:
Từ những phân tích vừa rồi ta có giải pháp sử dụng hai con trỏ như sau:
Một con trỏ (i) được đặt ở đầu mảng A, con trỏ còn lại (j) được đặt ở cuối mảng A.
Nếu tổng của hai phần tử ở hai vị trí con trỏ
Nhỏ hơn X: tăng vị trí con trỏ i lên một đơn vị.
Lớn hơn X: giảm vị trí con trỏ j đi một đơn vị.
Tiếp tục di chuyển cho đến khi hai con trỏ gặp nhau.
Khi con trỏ chưa gặp nhau mà tổng ở hai vị trí con trỏ có giá trị là X thì ta đã tìm được hai vị trí cần tìm (i và j), kết thúc chương trình.
Link mô phỏng thuật toán: https://youtu.be/39F4jKIn1OI
Code viết bằng ngôn ngữ lập trình C++
Code viết bằng ngôn ngữ lập trình Python
Nhận xét: Qua ba hướng giải quyết trên thì hướng giải quyết 1 có độ phức tạp là O(n2) không đáp ứng được thời gian khi n>104, hướng giải quyết 2 độ phức tạp O(nlogn) và hướng giải quyết 3 có độ phức tạp O(n). So sánh cả 3 hướng giải quyết trên thì hướng giải quyết 3 tốt nhất.
Ví dụ 2:
Cho một dãy số nguyên dương a1, a2, ..., aN (1<N< 2*105), ai≤106 với mọi i=1..N và một số nguyên dương K (K<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 K.
Dữ liệu vào: Đọc từ file SUB.INP gồm 2 dòng, dòng 1 chứa N và K. 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, là độ dài của dãy con tìm được.
Ví dụ:
SUB.INP
SUB.OUT
10 17
5 1 3 5 10 7 4 9 2 8
2
Hướng giải quyết 1. Sử dụng 2 vòng lặp for Độ phức tạp thuật toán: O(n2 )
Ý tưởng: Sử dụng tổng tiền tố ta có T[i]=a1+a2+a3++ai-1+ai=T[i-1]+a[i].
Tính tổng tiền tố: T[i]=T[i-1]+a[i]
Cho 2 vòng lặp for lồng nhau
Giá trị biến i chạy 1 đến n, biến j từ i đến n Nếu T[j]-T[i] >K nếu smin=min(smin,j-i).
Đưa giá trị smin ra
Code viết bằng ngôn ngữ lập trình C++
Code viết bằng ngôn ngữ lập trình Python
Hướng giải quyết 2: Tìm kiếm nhị phân - Binary Search Độ phức tạp thuật toán: O(nlogn)
Ý tưởng:
Gọi T[i] là tổng của các số từ A[1] đến A[i] vì A[i] các số dương nên dãy T là dãy tăng dần Khi đó ta sẽ tiến hành tìm kiếm nhị phân trên dãy T như sau:
Xét T[i] d=1; c=i-1; g=(d+c)/2
Nếu T[i]-T[g]>=K thì kq=min(kq,i-g) và tìm kq tiếp tục ở đoạn bên phải T[g]
Nếu T[i]-T[g]<K thì tìm kq ở đoạn bên trái T[g]
Code viết bằng ngôn ngữ lập trình C++
Code viết bằng ngôn ngữ lập trình Python
Hướng giải quyết 3: Tìm kiếm bằng 2 con trỏ - Two Pointe Độ phức tạp thuật toán: O(n)
Phân tích bài toán: Tìm đoạn con liên tiếp ngắn nhất có tổng >=K;
Ý tưởng:
Gọi sum(i,j) là tổng các phần tử trong đoạn [i,j] , một đoạn con [i,j] ngắn nhất nếu sum(i,j)>=K;
Qua đây bài toàn sẽ là bài toán Vì a dãy dương cho nên:
+ sum(1, j)>sum(2, j)>sum(3, j)>sum(4, j)>.	>sum(j−1, j)>sum(j, j).
+ Nếu đoạn con [i,j] là đoạn có sum(i,j)>=K thì xét đoạn [i,j+1] cũng có sum(i,j+1)>=K ta cần xét đoạn [i-1,j] có thỏa mãn bài toán không, tức là đi tìm đoạn ngắn tốt nhất.
+ Nếu đoạn con [i,j] là đoạn có sum(i,j)=K không tức là ta cần bổ sung vào đoạn đó để sum>=K.
Giải pháp.
Hai con trỏ i và j đặt ở vị trí đầu i=1, j=1 con trỏ i di chuyển nhanh hơn, con trỏ j di chuyển chậm hơn
Di chuyển con trỏ i từ đầu đến cuối (1 đến n) Sau mỗi di chuyển nếu :
+ sum(i, j)<K thì giữ nguyên con trỏ j
+ sum(i, j)>=K thì cập nhật đoạn ngắt nhất và tăng dần con trỏ j cho đến khi sum(i,j)<K.
Đưa ra độ dài đoạn con ngắn nhất của bài toán
Link mô phỏng thuật toán: https://youtu.be/zxN2dvZxapQ
Code viết bằng ngôn ngữ lập trình C++
Code viết bằng ngôn ngữ lập trình Python
Nhận xét: Qua ba hướng giải quyết trên thì hướng giải quyết 1 có độ phức tạp là O(n2) hướng giải quyết này không đáp ứng được thời gian, hướng giải quyết 2 độ phức tạp O(nlogn) và hướng giải quyết 3 có độ phức tạp O(n). Cả hai hướng giải
quyết này đều đáp ứng được thời gian tuy nhiên giữa hướng giải quyết 2 và hướng giải quyết 3 thì hướng giải quyết 3 tối ưu nhất.
Ví dụ 3. Trò chơi với dãy số - Seqgame
Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm N số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là: b1, b2,.., bn, còn dãy số mà bạn thứ hai chọn là: c1, c2, , cn
Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng bi (1 ≤ i ≤ N), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j ≤ N) thì giá của lượt chơi đó sẽ là |bi+cj|.
Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1,2), (1,3), (-2,2),
(-2,3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2,2).
Yêu cầu
Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.
Dữ liệu vào từ tệp SEQGAME.INP gồm:
Dòng đầu tiên chứa số nguyên dương N (N ≤ 105)
Dòng thứ hai chứa dãy số nguyên b1, b2, , bn (|bi| ≤ 109, i=1, 2,
, N)
Dòng thứ ba chứa dãy số nguyên c1, c2, , cn (|ci| ≤ 109, i=1, 2, ,
N)
Hai số liên tiếp trong một dòng được ghi cách nhau bởi dấu cách.
Kết quả ghi vào tệp SEQGAME.OUT là:
Giá nhỏ nhất tìm được.
Ràng buộc
60% số test ứng với 60% số điểm của bài có 1 ≤ N ≤ 1000
Ví dụ
SEQGAME.INP
SEQGAME.OUT
2
1 -2
2 3
0
Hướng giải quyết 1: Dùng 2 for lồng nhau. Độ phức tạp của thuật toán: O(n2)
Duyệt tất cả các trường hợp và cập nhật giá trị nhỏ nhất
Code viết bằng ngôn ngữ lập trình C++
Code viết bằng ngôn ngữ lập trình Python
Hướng giải quyết 2: Tìm kiếm nhị phân - Binary Search Độ phức tạp của thuật toán: O(nlogn)
Đầu tiên ta sẽ sắp xếp dãy a tăng dần. Sau đó, duyệt lần lượt các phần tử b, với mỗi giá trị b[i], ta sử dụng chặt nhị phân trên dãy a để tìm phần tử bé nhất mà lớn hơn hoặc bằng –b[i] và phần tử lớn nhất bé hơn hoặc bằng b[i]. Sau đó chỉ lấy min giá trị tuyệt đối của các tổng số tìm được với b[i].
Code viết bằng ngôn ngữ lập trình C++
Code viết bằng ngôn ngữ lập trình Python
Hướng giải quyết 3: Dùng thuật toán 2 con trỏ - Two Pointe Độ phức tạp của thuật toán: O(nlogn)
Ý tưởng: Sắp xếp hai dãy tăng dần thì ta có: b1<b2<b3<b4<.<bn c1<c2<c3<c4<.	<cn
Để |bi+cj| là nhỏ nhất thì bi+cj tiến về gần giá trị 0. Do sắp xếp hai dãy là dãy tăng dần.
Xét	- Nếu bi+cj >=0 thì muốn tiến gần về 0 thì giảm j
- Nếu bi+cj <0 thì muốn tiến gần về 0 cần tăng giá trị i. Thực hiện như vậy cho đến khi cập nhật |bi+cj| nhỏ nhất.
Giải pháp:
+ Sắp xếp tăng dần từng dãy số
+ Dùng 2 biến chạy xuôi và ngược là i và j. Biến i dùng duyệt xuôi mảng b(N) bắt đầu từ vị trí 1, biến j dùng duyệt ngược mảng c(N) bắt đầu từ vị trí N.
+ Vòng lặp thực hiện trong khi (i=1):
Tính v=bi+cj
Nếu v>=0 thì giảm j (để |v| giảm đi)
Ngược lại nếu v<0 thì tăng i (vì số âm khi được tăng lên thì trị tuyệt đối của nó giảm đi.
Link mô phỏng thuật toán: https://youtu.be/kVt7CK7PabA
Code viết bằng ngôn ngữ lập trình C++
Code viết bằng ngôn ngữ lập trình Python
Nhận xét: Qua ba hướng giải quyết trên thì hướng giải quyết 1 có độ phức tạp là O(n2) hướng giải quyết này không đáp ứng được thời gian, hướng giải quyết 2 độ phức tạp O(nlogn), hướng giải quyết 3 khi sử dụng 2 con trỏ có độ phức tạp O(n), nhưng do chúng ta đã sắp xếp nên mất O(nlogn) thời gian vậy độ thuật toán là O(nlogn). Cả hai hướng giải quyết này đều đáp ứng được thời gian tuy nhiên hướng giải quyết 3 ngắn ngọn và dễ hiểu hơn.
Rèn luyện kỹ năng vận dụng thuật toán 2 con trỏ để giải một số bài toán cơ bản đến nâng cao
Một số bài tập về 2 con trỏ, một con trỏ ở đầu và một con trỏ ở cuối di chuyển vào giữa cho đến khi cả 2 gặp.
Bài 1: Bình phương dãy số.
Cho một mảng số nguyên gồm N phần tử được sắp xếp theo thứ tự không giảm, trả về một mảng bình phương của mỗi số được sắp xếp theo thứ tự không giảm.
Dữ liệu vào từ tệp BinhPhuong.inp gồm:
Dòn