¶ Kĩ thuật hai con trỏ
Tác giả: Phan Đình Khôi - Đại học Bách Khoa Đà Nẵng
Reviewer: Nguyễn Khánh
¶ Lời mở đầu
Bài viết này sẽ giúp bạn tìm hiểu thêm về kỹ thuật hai con trỏ. Kỹ thuật này được sử dụng khá phổ biến, giúp chương trình tiết kiệm thời gian và không gian xử lý.
¶ Bài toán 1
Cho hai dãy số nguyên đã được sắp xếp không giảm và lần lượt có và phần tử. Hãy ghép chúng thành dãy được bố trí theo thứ tự không giảm.
Giới hạn: và .
¶ Phân tích
Hãy cùng xem ví dụ sau đây.
Cho trước hai dãy số và được sắp xếp không giảm:
Làm cách nào để có thể ghép chúng thành một dãy số cũng được sắp xếp không giảm ?
Trước tiên, hãy cùng xác định phần tử đầu tiên của dãy .
Vì dãy được bố trí theo thứ tự không giảm, cho nên phần tử đầu tiên của dãy phải là phần tử có giá trị nhỏ nhất trong cả hai dãy và .
Ta có thể so sánh hai phần tử nhỏ nhất của hai dãy , và đưa phần tử có giá trị nhỏ hơn vào vị trí đầu tiên của dãy .
Dãy và đã được sắp xếp không giảm, vì thế hai phần tử nhỏ nhất ở đây chính là hai phần tử ở vị trí đầu tiên ở mỗi dãy ( và ).
Bây giờ, phần tử tiếp theo của dãy sẽ là phần tử nhỏ nhất trong các phần tử chưa được đưa vào dãy .
Dãy và đã được sắp xếp không giảm, vì thế sau khi đưa vào dãy , là phần tử nhỏ nhất chưa được chọn ở dãy và là phần tử nhỏ nhất chưa được chọn ở dãy .
So sánh và , chọn phần tử có giá trị nhỏ hơn và đưa vào dãy .
Sau khi đưa vào dãy , trở thành phần tử nhỏ nhất chưa được chọn ở dãy .
Vẫn như thế, phần tử tiếp theo của dãy sẽ là phần tử nhỏ nhất trong các phần tử chưa được đưa vào dãy .
So sánh và , chọn phần tử có giá trị nhỏ hơn dãy và đưa vào dãy .
Sau khi đưa vào dãy , trở thành phần tử nhỏ nhất chưa được chọn ở dãy .
Ta nhận thấy rằng
- Tại mọi thời điểm, phần tử tiếp theo được đưa vào dãy sẽ là phần tử có giá trị nhỏ nhất trong các phần tử chưa được chọn.
- Bằng cách so sánh phần tử nhỏ nhất chưa được chọn ở dãy và phần tử nhỏ nhất chưa được chọn ở dãy , phần tử nhỏ hơn sẽ được chọn vào dãy .
- Ban đầu, lúc dãy chưa có phần tử nào
- là phần tử nhỏ nhất chưa được chọn trong dãy .
- là phần tử nhỏ nhất chưa được chọn trong dãy .
- Khi đưa phần tử vào dãy thì phần tử nhỏ nhất chưa được chọn trong dãy sẽ là .
- Khi đưa phần tử vào dãy thì phần tử nhỏ nhất chưa được chọn trong dãy sẽ là .
¶ Giải pháp
Dựa vào những phân tích ta có giải pháp sử dụng hai con trỏ như sau:
- Dãy có con trỏ , con trỏ này bắt đầu ở vị trí đầu dãy .
- Con trỏ này được thể hiện như phần tử nhỏ nhất chưa được chọn trong dãy .
- Dãy có con trỏ , con trỏ này bắt đầu ở vị trí đầu dãy .
- Con trỏ này được thể hiện như phần tử nhỏ nhất chưa được chọn trong dãy .
- Ta sẽ lặp lại công việc này, cho đến khi đưa hết các phần tử trong dãy và vào dãy :
- Khi các phần tử trong một dãy nào đó, dãy hoặc dãy , đều đã được đưa vào dãy : đưa lần lượt các phần tử trong dãy còn lại vào dãy .
- Ngược lại:
- So sánh hai phần tử ở hai con trỏ.
- Đưa phần tử có giá trị nhỏ hơn vào dãy , nếu hai phần tử có giá trị như nhau thì chọn một trong hai.
- Tăng vị trí con trỏ ở phần tử được đưa vào lên một đơn vị.
Để hiểu rõ hơn, ta hãy cùng xem qua ví dụ sau đây:
-
Đặt và .
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta có thể đưa bất kỳ một trong hai phần tử. Ở đây ta đưa phần tử vào và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì tất cả các phần tử trong dãy đều đã được đưa vào dãy nên từ đưa lần lượt các phần tử chưa được chọn trong dãy vào trong dãy
.gif)
Cài đặt
int i = 1, j = 1;
vector<int> c;
while (i <= n || j <= m){
if (j == m + 1 || (i <= n && a[i] <= b[j]))
c.push_back(a[i++]);
else
c.push_back(b[j++]);
}
for (auto it: c)
cout << it << " ";
Độ phức tạp
Vị trí con trỏ luôn tăng và tăng quá không quá lần, vị trí con trỏ cũng luôn tăng và tăng không quá lần.
Vì thế độ phức tạp của giải pháp là .
¶ Luyện tập
¶ Bài toán 2
Cho một mảng số nguyên có phần tử, mảng này đã được sắp xếp tăng dần. Hãy tìm hai vị trí khác nhau bất kỳ sao cho tổng của hai phần tử ở hai vị trí đó có giá trị là .
Giới hạn: và
¶ Phân tích
Hãy cùng xem ví dụ sau đây.
Cho trước mảng số được sắp xếp tăng dần và :
Làm cách nào để có thể tìm hai vị trí khác nhau mà tổng hai phần tử ở hai vị trí đó có tổng là ?
Trước tiên, ta có một chút nhận xét sau:
- vì dãy tăng dần.
- .
Có thể thấy, tổng của với các phần tử khác trong dãy đều lớn hơn . Vì thế ta không quan tâm đến nữa.
- .
Có thể thấy, tổng của với các phần tử khác trong các phần tử ta quan tâm đều nhỏ hơn . Vì thế ta không quan tâm đến nữa.
- .
Có thể thấy, tổng của với các phần tử khác trong các phần tử ta quan tâm đều lớn hơn . Vì thế ta không quan tâm đến nữa.
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 nào đó.
Ta có một số nhận xét sau:
- Nếu , trong mảng không tồn tại hai vị trí khác nhau mà tổng hai phần tử ở đó có giá trị là .
- Ngược lại:
- Nếu , ta đã tìm được hai vị trí cần tìm ( và ).
- Nếu , không quan tâm đến 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 .
- Nếu , không quan tâm đến 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 .
¶ 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ỏ được đặt ở đầu mảng , con trỏ còn lại được đặt ở cuối mảng .
- Nếu tổng của hai phần tử ở hai vị trí con trỏ
- Nhỏ hơn : tăng vị trí con trỏ lên một đơn vị.
- Lớn hơn : giảm vị trí con trỏ đ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à thì ta đã tìm được hai vị trí cần tìm ( và ), kết thúc chương trình.
Để hiểu rõ hơn, ta hãy cùng xem qua một số ví dụ sau đây:
Ví dụ 1: và .
-
Đặt và .
-
Vì nên giảm vị trí đi một đơn vị.
-
Vì nên tăng vị trí lên một đơn vị.
-
Vì nên giảm vị trí đi một đơn vị.
-
Vì nên tăng vị trí lên một đơn vị.
-
Vì nên hai vị trí cần tìm là hai vị trí và .
.gif)
Ví dụ 2: và .
-
Đặt và .
-
Vì nên giảm vị trí đi một đơn vị.
-
Vì nên tăng vị trí lên một đơn vị.
-
Vì tăng vị trí lên một đơn vị.
-
Vì giảm vị trí đi một đơn vị.
-
Vì giảm vị trí đi một đơn vị.
-
Vì tăng vị trí lên một đơn vị.
-
Vì nên không tìm được hai vị trí cần tìm.
.gif)
Cài đặt
int i = 1, j = N;
while (i < j) {
if (a[i] + a[j] == x) {
cout << i << " " << j;
return 0;
}
if (a[i] + a[j] < x)
i += 1;
else
j -= 1;
}
cout << "No solution";
Độ phức tạp
Vị trí con trỏ luôn tăng, vị trí con trỏ thì luôn giảm.
Hơn nữa, sự thay đổi vị trí hai con trỏ này sẽ dừng lại khi tổng hai phần tử ở hai vị trí con trỏ có tổng là hay khi vị trí bằng vị trí .
Vì thế, việc thay đổi vị trí hai con trỏ sẽ không quá lần, độ phức tạp của giải pháp là .
¶ Luyện tập
¶ Bài toán 3
Cho dãy số nguyên dương có phần tử. Hãy tìm độ dài đoạn con dài nhất trong dãy sao cho tổng các phần tử trong đoạn này không quá .
Dữ liệu đảm bảo các phần tử trong dãy đều có giá trị không quá .
Giới hạn: , và .
¶ Phân tích
Để dễ dàng phân tích, ta tạm gọi
- là tổng các phần tử trong đoạn .
- Một đoạn con là đoạn con "tốt" nếu
Qua đây, bài toán của chúng ta sẽ là tìm độ dài đoạn con "tốt" dài nhất.
Vì dãy là một dãy số nguyên dương cho nên
- .
- Nếu đoạn con là đoạn con "tốt" thì với mọi , đoạn là đoạn con "tốt".
- Nếu đoạn con không là đoạn con "tốt" thì với mọi , đoạn không là đoạn con "tốt".
Với là một vị trí bất kỳ, nếu như là vị trí nhỏ nhất sao cho đoạn là một đoạn "tốt" thì
- mọi thì đoạn con là một đoạn "tốt".
- mọi thì đoạn con không là một đoạn "tốt".
- đoạn con là một đoạn con "tốt" dài nhất trong các đoạn con "tốt" có vị trí kết thúc tại .
Từ đó, với mỗi từ đến , nếu ta xác định được vị trí , ta có thể biết được độ dài của đoạn con "tốt" dài nhất của dãy .
Hãy cùng nhận xét vị trí của với mỗi từ đến qua ví dụ sau đây:
Cho trước dãy và
| Độ dài đoạn con | ||
|---|---|---|
Độ dài của đoạn con "tốt" dài nhất của dãy là giá trị lớn nhất của độ dài các đoạn con "tốt" dài nhất với vị trí kết thúc từ đến .
Ở đây, độ dài đoạn con "tốt" dài nhất của dãy là .
Qua ví dụ vừa rồi, ta thấy rằng, vị trí đối với các giá trị từ đến có giá trị không giảm.
Thật vậy, với mọi thì , vì thế giá trị đối với phải không quá giá trị đối với .
Hơn nữa vì các phần tử trong dãy đều có giá trị không quá cho nên luôn tồn tại vị trí sao cho đoạn là một đoạn "tốt".
¶ Giải pháp
Với những phân tích như trên, ta có giải quyết bài toán với phương pháp hai con trỏ như sau:
- Hai con trỏ và sẽ đặt ở vị trí .
- Hai con trỏ này được thể hiện như hai vị trí , như ở trên phần phân tích.
- Di chuyển lần lượt con trỏ từ đến .
- Sau mỗi lần di chuyển con trỏ , nếu
- : giữ nguyên vị trí con trỏ .
- : tăng dần vị trí con trỏ cho đến khi .
- Hiện tại với vị trí con trỏ và , ta biết đoạn "tốt" dài nhất với vị trí kết thúc tại là đoạn .
- Sau mỗi lần di chuyển con trỏ , nếu
- Độ dài đoạn con "tốt" dài nhất chính là giá trị độ dài lớn nhất của các đoạn "tốt" dài nhất với vị trí kết thúc tại , với mỗi từ đến .
Để hiểu rõ hơn, ta hãy cùng xem qua một số ví dụ sau đây:
và
-
Sử dụng biến để lưu lại giá trị lớn nhất của độ dài đoạn "tốt" có vị trí kết thúc tại , với từ đến .
-
Đặt và
- vì nên đoạn là một đoạn "tốt".
-
Tăng vị trí lên đơn vị
- vì nên đoạn là một đoạn tốt.
-
Tăng vị trí lên đơn vị
- vì nên đoạn là một đoạn tốt.
-
Tăng vị trí lên đơn vị
- vì nên đoạn là một đoạn tốt.
-
Tăng vị trí lên đơn vị
- vì nên tăng vị trí .
-
Tăng vị trí lên đơn vị
- vì nên đoạn là một đoạn tốt.
-
Tăng vị trí lên đơn vị
- vì nên tăng vị trí .
-
Tăng vị trí lên đơn vị
- vì nên tăng vị trí .
-
Tăng vị trí lên đơn vị
- vì nên đoạn là một đoạn tốt.
-
Tăng vị trí lên đơn vị
- vì nên tăng vị trí .
-
Tăng vị trí lên đơn vị
- vì nên tăng vị trí .
-
Tăng vị trí lên đơn vị
- vì nên đoạn là một đoạn tốt.
.gif)
Cài đặt
Để có thể tính được tổng các phần tử từ đến trong khi và đang di động, ta sẽ sử dụng biến để lưu lại tổng của đoạn hiện tại.
Sau khi di chuyển sang phải, biến sẽ cộng thêm giá trị .
Trước khi di chuyển sang phải, biến sẽ trừ đi giá trị .
int ans = 0, sum = 0;
for (int l = 1, r = 1; r <= n; r++) {
sum += a[r];
while (sum > s) {
sum -= a[l];
l++;
}
ans = max(ans, r - l + 1);
}
cout << ans;
Độ phức tạp
Vị trí con trỏ luôn tăng, vị trí con trỏ luôn tăng và luôn tăng không giá trị .
Hơn nữa, mỗi vị trí và tăng không quá lần.
Vì thế độ phức tạp của giải pháp là .
¶ Luyện tập
¶ Bài toán 4
Bạn được cho một dãy số nguyên như sau:
- .
Tìm nhỏ nhất sao cho tồn tại và . Dữ liệu đảm bảo không quá .
Giới hạn: và .
¶ Phân tích
Để dễ dàng phân tích ta định nghĩa hàm như sau:
Dãy số của chúng ta sẽ có dạng
Với phép chia lấy dư cho thì mọi , giá trị của sẽ có giá trị nằm trong khoảng .
Vì thế, dãy số với vô hạn phần tử này sẽ tồn tại với . (theo nguyên lý Dirichlet)
Có thể thấy, khi dãy tồn tại , dãy sẽ xuất hiện chu kỳ. Cụ thể như sau:
Gọi là giá trị nhỏ nhất thỏa mãn tồn tại sao cho .
Khi đó, dãy sẽ có chu kỳ lặp lại các phần tử từ đến
Dãy số có thể biễu diễn như hình sau đây:
Bài toán có thể giải quyết nếu chúng ta phần tử bắt đầu chu kỳ () và độ dài của chu kỳ .
Cụ thể, xem ví dụ sau đây:
Ta có dãy số
Giá trị cần tìm của bài toán là .
Ta có thể tính được giá trị này bằng cách xác định
- phần tử bắt đầu chu kỳ .
- độ dài chu kỳ .
Ở đây, phần tử bắt đầu chu kỳ là và độ dài chu kỳ là .
Giá trị .
¶ Giải pháp
Để xác định giá trị và , ta sử dụng thuật toán Floyd's tortoise and hare
¶ Rùa và Thỏ
Khởi tạo hai con trỏ, (rùa) và (thỏ).
Tại mỗi thời điểm, ta tịnh tiến hai con trỏ này như sau:
- Tortoise (rùa): tịnh tiến một "bước"
- Nếu hiện tại con trỏ đang là , nó sẽ được tịnh tiến đến .
- Vì dãy số của chúng ta có chu kỳ nên ta có công thức tính giá trị của con trỏ sau lần tịnh tiến:
- :
- :
- Hare (thỏ): tịnh tiến hai "bước"
- Nếu hiện tại con trỏ đang là , nó sẽ được tịnh tiến đến .
- Vì dãy số của chúng ta có chu kỳ nên ta có công thức tính giá trị của con trỏ sau lần tịnh tiến:
- :
- :
Ngoài lúc ban đầu, hai con trỏ và sẽ luôn gặp nhau tại thời điểm nào đó. Thật vậy:
- :
- Sau lần tịnh tiến, = và = .
- Tuy nhiên, mới bắt đầu lại chu kỳ cho nên các phần tử từ đến phải đôi một khác nhau.
- Vì thế , và chưa gặp nhau lúc này.
- và
- Sau lần tịnh tiến, = và = .
- Tuy nhiên, mới bắt đầu lại chu kỳ cho nên các phần tử từ đến phải đôi một khác nhau.
- Vì thế , và chưa gặp nhau lúc này.
-
- Sau lần tịnh tiến, = và = .
- Giả sử và gặp nhau thì .
- Vậy, và sẽ gặp nhau sau lần tịnh tiến, trong đó là số nguyên có giá trị lớn hơn hoặc bằng và chia hết cho .
- Trừ lúc khởi tạo, hai con trỏ và sẽ gặp nhau khi giá trị của cả hai con trỏ là .
Cách cài đặt để và gặp nhau:
int tortoise = 1, hare = 1;
while (true) {
tortoise = f(tortoise);
hare = f(f(hare));
if (tortoise == hare)
break;
}
¶ Tìm
Khởi tạo một con trỏ mới , con trỏ này được tịnh tiến giống như con trỏ .
Tịnh tiến cùng lúc hai con trỏ và và dừng lại cho đến khi chúng gặp nhau.
Số lần tịnh tiến ở đây chính là .
Chứng minh:
- Trong những lần tịnh tiến từ đến , con trỏ nhận giá trị từ đến (các giá trị không có trong chu kỳ) . Còn con trỏ , vì đã nằm ở chu kỳ, nên giá trị của sẽ nhận giá trị của các phần tử có trong chu kỳ. Vì thế và chưa gặp nhau.
- Hai con trỏ và gặp nhau tại lần tịnh tiến thứ :
- Con trỏ có giá trị .
- Lúc chưa tịnh tiến , con trỏ có giá trị (đã nêu ở mục Rùa và Thỏ). Vì đã ở trong chu kỳ cho nên, sau khi tịnh tiến lần con trỏ sẽ có giá trị là . Mà là số nguyên dương chia hết cho , cho nên con trỏ có giá trị là .
Cách cài đặt tìm :
int mu = 0, p = 1;
while (p != tortoise) {
p = f(p);
tortoise = f(tortoise);
mu++;
}
¶ Tìm
Bây giờ cả hai con trỏ và đang có giá trị là .
Chúng ta giữ nguyên giá trị , và tịnh tiến cho đến khi có giá trị lại.
Vì đã ở trong chu kỳ cho nên, sau khi tinh tiến lần, sẽ lại có giá trị là .
int lambda = 0;
while (true) {
lambda++;
p = f(p);
if (tortoise == p)
break;
}
Để hiểu rõ hơn, ta hãy cùng xem qua một số ví dụ sau đây:
Ta có dãy số
Giá trị cần tìm của bài toán là .
Ta có thể tính được giá trị này bằng cách xác định
- phần tử bắt đầu chu kỳ .
- độ dài chu kỳ .
Ở đây, phần tử bắt đầu chu kỳ là và độ dài chu kỳ là .
Giá trị .
.gif)
Độ phức tạp
Khi khởi tạo hai con trỏ và ở , hai con trỏ sẽ gặp lại nhau lần đầu tiên sau bước.
Cụ thể là số nguyên nhỏ nhất sao cho có giá trị lớn hơn hoặc bằng và chia chết cho .
Vì thế việc xác định được vị trí và gặp nhau sẽ mất không quá bước. Hơn nữa, việc xác định mất bước, xác định mất bước.
Kết luận: độ phức tạp của bài toán là . (trong đó )