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 trên ngôn ngữ lập trình C++ và Python

PHẦN I: ĐẶT VẤN ĐỀ
1. Lý do chọn đề tài
Bộ trưởng Nguyễn Mạnh Hùng cũng phát biểu: “Mỗi người phải biết 3 ngôn ngữ: Tiếng mẹ đẻ để giữ gìn văn hóa truyền thống, Tiếng Anh để hội nhập quốc tế và ngôn ngữ máy lập trình coding để giao tiếp người với máy”.
Điều đó khẳng định vai trò và vị trí quan trọng của Tin học đối với toàn xã hội. Vì vậy mỗi người, mỗi học sinh cần hiểu và trang bị kiến thức cơ bản về Tin học để có thể theo kịp với thời đại, với sự phát triển của xã hội. Vì vậy khi học tin thì cần trang bị kiến thức, kỹ năng lập trình để giải quyết bài toán dễ dàng hơn.
Trong chương trình giáo dục phổ thông 2018 thì ngôn ngữ lập trình pascal không được đưa vào dạy học thay vào đó là ngôn ngữ lập trình Python. Ngoài Python thì C++ cũng là ngôn ngữ lập trình hiện nay rất phổ biến trong chương trình dạy học cũng như tính ứng dụng của 2 ngôn ngữ này rất nhiều, nhất là trong các kỳ thi tin học trẻ, thi vào chuyên tin, học sinh giỏi tỉnh…
Khi giải các bài toán Tin học người lập trình luôn mong muốn viết chương trình với thuật toán tối ưu, thời gian thực hiện nhanh, bộ nhớ hạn chế…Tuy nhiên, bài toán Tin học thường đa dạng, phong phú nên để có thể tìm được thuật toán tối ưu phù hợp dữ liệu bài toán là việc không hề dễ dàng. Trong lập trình tin học đã có rất nhiều phương pháp giải các bài toán nhưng để đảm bảo thời gian, không gian là không dễ. Vì vậy lựa chọn thuật toán để tối ưu là rất quan trọng.
Qua quá trình giảng dạy, học tập, tìm tòi và đặc biệt là tham gia bồi dưỡng học sinh giỏi nhiều năm qua, tôi đã tích lũy được một số kinh nghiệm về thuật toán 2 con trỏ. Do đó, tôi quyết định viết sáng kiến kinh nghiệm: “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 “.
Đề tài tập trung nghiên cứu về thuật toán 2 con trỏ, đưa ra những ứng dụng của 2 con trỏ khi giải các bài toán trên máy tính. Nhằm giúp học sinh vận dụng thuật toán này linh hoạt, giúp cải thiện về thời gian và không gian khi gặp các dạng bài toán này.
Để hoàn thành nhiệm vụ của đề tài, tôi đã nghiên cứu rất nhiều sách và các chuyên đề Tin học dành cho học sinh giỏi, các tài liệu trên các trang web. Tuy nhiên rất ít tài liệu trình bày cụ thể về cách sử dụng thuật toán này một cách đầy đủ và dễ hiểu.
2. Mục đích nghiên cứu
– Đề tài nêu ra các định hướng giúp học sinh có thể tiếp cận thuật toán 2 con trỏ để giải một số bài toán, tối ưu phù hợp với dữ liệu bài toán.
– Giúp học sinh tiếp cận ngôn ngữ lập trình C++ và Python sớm, tốt hơn.
– Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT hoặc thi vào các trường chuyên.
3. Nhiệm vụ nghiên cứu của đề tài
– Đề tài phân tích các thuật toán trong các dạng toán quen thuộc, so sánh độ phức tạp thuật toán và định hướng lựa chọn thuật toán tối ưu trong các trường hợp dữ liệu cụ thể nhằm giải bài toán hiệu quả nhất.
– Minh họa bằng các ví dụ, hình ảnh, video cụ thể. Đồng thời liên hệ các đề thi vào trường chuyên, đề thi học sinh giỏi tỉnh thời gian qua.
4. Đối tượng nghiên cứu của đề tài
– Độ phức tạp thuật toán và giải pháp lựa chọn thuật toán tối ưu trong các dạng bài toán quen thuộc trên ngôn ngữ lập trình C++ và Python.
– Phương pháp bồi dưỡng năng lực giải quyết vấn đề cho học sinh.
5. Phạm vi nghiên cứu của đề tài
– Chương trình Tin học THCS, THPT để bồi dưỡng học sinh giỏi Tin học và thi vào trường chuyên THPT.
PHẦN II: NỘI DUNG NGHIÊN CỨU
1. Cơ sở lý luận
Giới thiệu về thuật toán, các bước tiếp cận với thuật toán, khi nào thì ta sử dụng thuật toán hai con trỏ. Trình bày các dạng, phân tích và cài chương trình cụ thể để bạn đọc dễ hiểu nhất. Qua đó có thể vận dụng để giải quyết các bài toán về sau.
1.1. Giới thiệu
“Khi lựa chọn thuật toán dùng để giải quyết bài toán, thuật toán hiệu quả nhất là những thuật toán đơn giản và được thực thi tốt nhất”. Trong Cấu trúc dữ liệu và giải thuật thì thuật toán hai con trỏ là một thuật toán khá đơn giản và hiệu quả. Thường được ứng dụng để giải các bài toán trong lập trình, thuật toán này khá phổ biến đối với các kỳ thi tin học hiện nay.
Hai con trỏ là một dạng thuật toán trong đó hai con trỏ lặp lại trên cấu trúc dữ liệu cho đến khi một hoặc cả hai con đáp ứng điều kiện cần thiết.
Tuy nhiên; “thuật toán hai con trỏ” có một số khái niệm hạn chế. Hơn nữa, nó là một thuật toán đơn giản và hiệu quả, khi biết sử dụng đúng cách, nó sẽ mang lại rất nhiều hiệu quả.
Thuật toán hai con trỏ là một trong những bài thường gặp nhất trong bất kỳ cuộc thi lập trình. Cách tiếp cận này tối ưu hóa thời gian chạy bằng cách sử dụng một số thứ tự (không nhất thiết phải sắp xếp) của dữ liệu. Nó thường được áp dụng trên danh sách (mảng) và danh sách liên kết. Điều này thường được sử dụng để tìm kiếm các cặp trong một mảng được sắp xếp. Cách tiếp cận này hoạt động trong không gian không đổi. Mục đích chính của thuật toán này là giảm độ phức tạp của giải pháp dựa trên O(n3) hoặc O(n2) thành giải pháp thời gian tuyến tính.
Trong đề tài này, chúng tôi đã xem xét các khái niệm cơ bản và cung cấp các ví dụ khác nhau. Lấy các ví dụ minh họa cũng như một số bài tập rèn luyện tư duy và cách tiếp cận về thuật toán này từ cơ bản đến nâng cao giúp các các em có thể va chạm các dạng bài tập một cách đa dạng hơn, để biết khi nào và làm thế nào để áp dụng thuật toán hai con trỏ.
Ngoài ra chúng tôi còn xây dựng các hình ảnh, video cụ thể để mô phỏng thuật toán. Qua đó người đọc dễ hiểu, dễ nắm bắt được phương pháp một cách tốt nhất.
1.1.1. Con trỏ là gì?
Một con trỏ là một tham chiếu đến một đối tượng. Đối tượng đó lưu trữ một địa chỉ bộ nhớ có giá trị khác nằm trong bộ nhớ máy tính, hoặc trong một số trường hợp, của phần cứng máy tính được ánh xạ bộ nhớ. Nói một cách đơn giản hơn – một biến lưu trữ địa chỉ cho một mảng cũng là một con trỏ. Ví dụ, chúng tôi đã tính toán kích thước của các con trỏ trong chương trình C++ và Python.
Đặt câu hỏi thuật toán con trỏ và hai con trỏ có thể so sánh như thế nào?
Con trỏ lưu trữ địa chỉ của các đối tượng và chúng ta sẽ sử dụng thực tế này để trỏ đến các đối tượng khác nhau bằng cách sử dụng các biến trong thuật toán hai con trỏ. Do đó, trong trường hợp này, chúng cũng được gọi là con trỏ.
Thuật toán hai con trỏ không gì khác hơn là một sự tối ưu hóa của các kỹ thuật. Nó làm giảm sự phức tạp về thời gian bằng cách sử dụng một số loại thứ tự thay vì nhất thiết phải sắp xếp dữ liệu.
1.1.2. Làm thế nào để sử dụng thuật toán hai con trỏ?
Trước khi chúng ta bắt đầu, hãy nhớ rằng hai con trỏ trong thuật toán này đại diện cho hai chỉ số, số lần di chuyển của con trỏ này không phụ thuộc vào con trỏ kia.
Các bước trong cách tiếp cận hai con trỏ:
Một số hình ảnh của thuật toán 2 con trỏ.

Như trong hình trên, cách tiếp cận hai con trỏ có ba bước chính:
Khởi tạo con trỏ – Con trỏ có thể ở bất kỳ đâu tùy thuộc vào yêu cầu của bài toán chúng ta đặt ví trí xuất phát và kết thúc cho hợp lí. Chúng ta có thể sử dụng cả hai con trỏ bắt đầu ở cùng một vị trí tức là bắt đầu của mảng hoặc xâu, một con trỏ di chuyển chậm và con trỏ kia di chuyển nhanh hơn và có thể sử dụng một con trỏ ở vị trí bắt đầu và một con khác ở vị trí cuối cùng.
Chuyển động của con trỏ – Điều này sẽ quyết định cách chúng ta đưa ra cách tiếp cận bài toán, xác định giải pháp. Con trỏ có thể di chuyển theo cùng một hướng hoặc chúng có thể di chuyển theo hướng ngược lại. Mỗi lần di chuyển của các con trỏ là một đơn vị, cũng có trường hợp hai con trỏ này có thể đứng lệch nhau một đơn vị.
Điều kiện dừng – Điều này quyết định khi nào chúng ta dừng lại. Khi hai con trỏ gặp nhau hoặc một trong hai con trỏ di chuyển chạm điểm cuối của bên kia.
1.2. Một số dạng về thuật toán hai con trỏ. 1.2.1. Hai 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 nhau.
Trong ngôn ngữ lập trình thì ta thường làm quen với nhiều dạng bài tập khác nhau, nhất là một số dạng bài tập liên quan đến sắp xếp bạn có thể nghĩ đến ý tưởng hai con trỏ. Để bạn làm bài tập tốt hơn cũng như trong các kì thi bạn trang bị một số thuật toán để ứng dụng giải quyết bài toán tốt hơn. Dưới đây là một thuật toán hai con trỏ: một con trỏ ở đầu và một con trỏ ở cuối mảng hoặc chuổi nào đó tùy thuộc vào bài toán, chọn di chuyển 2 con trỏ cho hợp lý theo yêu cầu bài toán. Thông thường dạng thuật toán này mảng sắp xếp …thì thực hiện 3 bước sau:
Bước 1: Gán một con trỏ i đầu, con trỏ j cuối
Bước 2: Hai con trỏ di chuyển vào giữa
Bước 3: Điều kiện để hai con trỏ dừng khi chúng gặp nhau.
Hình ảnh minh họa:

Ví dụ: Cho một dãy số nguyên gồm N số hạng a1, a2, a3….aN. Biết 0<N<=105, |ai|<=109. Viết chương trình đảo ngược các phần tử trong dãy số nguyên trên.
Dữ liệu vào từ tệp DAONGUOC.INP gồm:
– Dòng 1 Số N phần tử.
– Dòng 2 là dãy gồm N số từ a1, a2, a3, …., aN.
Dữ liệu ra. Ghi kết quả tệp DAONGUOC.OUT Ví dụ:
DAONGUOC.INP DAONGUOC.OUT
5
1 2 3 4 5 5 4 3 2 1
Phân tích: Xét ví dụ sau.
Ta có dãy số: a1, a2, a3, …, aN-3, aN-2, aN-1, aN
Dãy cần tìm là: aN, aN-1, aN-2, aN-3, …, a3, a2, a1
Đối với bài toán này cách khá đơn giản chúng ta có thể duyệt ngược từ cuối mảng về phía đầu mảng và đưa ra các phần tử của mảng, chúng ta có thể duyệt từ đầu đến cuối hoặc nữa mảng và đưa các phần tử ra. Ngoài cách trên chúng tôi giới thiệu cách sử dụng thuật toán hai con trỏ.
Ta nhận thấy dãy cần đưa ra aN, aN-1, aN-2, aN-3, …, a3, a2, a1 là dãy đảo ngược của dãy a1, a2, a3, …, aN-3, aN-2, aN-1, aN. Vậy phần tử ở vị trí đầu tiên (a1) và phần tử ở vị trí cuối cùng (aN) của dãy a hoán đổi nhau, phần tử ở vị trí thứ 2 (a2) và phần tử ở vị trí thứ N-1 (aN-1) của dãy a hoán đổi nhau, tương tự có các cặp (a3, aN-2), (a4, aN-3), …. Như vậy ta chỉ cần hoán đổi các cặp đó cho nhau thì ta được kết quả bài toán. Ngoài ra ta thấy các cặp duyệt từ trái qua phải cứ mỗi cặp chỉ số tăng một đơn vị, duyệt từ phải qua trái mỗi cặp chỉ số giảm 1 đơn vị. Vì vậy ta sử dụng thuật toán hai con trỏ, một con trỏ di chuyển trái sang phải, con trỏ kia di chuyển ngược lại.
Cách tiếp cận: Cách tiếp cận sử dụng thuật toán hai con trỏ.
• Chúng tôi chỉ sử dụng hai con trỏ, một con trỏ ở đầu mảng và một con trỏ khác ở cuối mảng.
• Hoán đổi các phần tử khi con trỏ trỏ tới phần tử ở vị trí đó cho đến khi con trỏ đầu lớn hơn hoặc bằng con trỏ cuối thì kết thúc. Mỗi lần hoán đổi thì tăng con trỏ đầu và giảm con trỏ cuối một đơn vị Giải pháp:
• Đầu tiên lấy hai con trỏ i và j.
• i = 1 và j = N.
• Bây giờ hãy chạy một vòng lặp while với điều kiện i < j. Bên trong vòng lặp while: o Hoán đổi A[i] và A[j]. o Và sau khi hoán đổi, tăng i lên một và giảm dần j một
• Đưa ra kết quả bài toán
Link mô phỏng thuật toán: https://youtu.be/WGz-uOsUWEo
Độ phức tạp thời gian sẽ là: O(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

1.2.2. Một con trỏ di chuyển chậm và một con trỏ di chuyển với tốc độ nhanh hơn.
Đối với một số bài tập bạn thường gặp như dãy con liên tiếp, xâu con thì bạn có thể áp dụng hai con trỏ để giải quyết bài toán, chúng ta sử dụng hai con trỏ ở đầu mảng hoặc xâu nào đó tùy thuộc vào bài toán mà di chuyển hai con trỏ cho hợp lý đáp ứng yêu cầu bài toán, tuy nhiên dạng bài toán này thường sử dụng một con trỏ di chuyển nhanh hơn con trỏ kia, khi đáp ứng yêu cầu bài toán thì con trỏ kia tiến hành di chuyển để đáp ứng bài toán tối ưu hơn. Thông thường dạng thuật toán này thì thực hiện 3 bước sau:
Bước 1: Gán hai con trỏ i, j đầu
Bước 2: Hai con trỏ di chuyển về phía sau
Bước 3: Điều kiện để dừng một trong hai con trỏ di chuyến đến cuối Hình ảnh minh họa:

Ví dụ: Xóa các ký tự trùng lặp liền kề khỏi một chuỗi.
Cho một chuỗi S hãy xóa các kí tự trùng lặp liền kề ra khỏi chuỗi. Nói cách khác loại bỏ các kí tự giống nhau liên tiếp, ngoại trừ một kí tự.
VD: S=”aaaAAbbcccbd” kết quả “aAbcbd”.
Phân tích: Cho xâu S=”aaaAAbbcccbd” đưa ra kết quả S=”aAbcbd”.
S=”aaaAAbbcccbd”
So sánh s[i] và s[j] để tìm kí tự khác nhau.
S=“aaaAAbbcccbd”; so sánh S[0]= ‘a’ với S[1]= ‘a’ bằng nhau
S= “aaaAAbbcccbd”; so sánh S[0]= ‘a’ với S[2]= ‘a’ bằng nhau
S=“aaaAAbbcccbd”; so sánh S[0]= ‘a’ với S[3]= ‘A’ khác nhau thay vị trí S[1] bằng S[3]; ta được S=“aAaAAbbcccbd” ;
S=“aAaAAbbcccbd”; so sánh S[1]= ‘A’ với S[4]= ‘A’ bằng nhau
S=“aAaAAbbcccbd”; so sánh S[1]=‘A’ với S[5]= ‘b’ khác nhau thay vị trí S[2] bằng S[5] ta được S=“ aAbAAbbcccbd”.
S= “aAbAAbbcccbd” ; so sánh S[2]= ‘b’ với S[6]= ‘b’ bằng nhau
S= “aAbAAbbcccbd” ; so sánh S[2]=‘b’ với S[7]= ‘c’ khác nhau thay vị trí S[3] bằng S[7] ta được S=“ aAbcAbbcccbd”
S=“aAbcAbbcccbd” ; so sánh S[3]= ‘c’ với S[8]= ‘c’ bằng nhau
S=“aAbcAbbcccbd”; so sánh S[3]= ‘c’ với S[9] =‘c’ bằng nhau
S=“aAbcAbbcccbd”; so sánh S[3]= ‘c’ với S[10]= ‘b’ khác nhau thay vị trí S[4] bằng S[10] ta được S=“aAbcbbbcccbd”.
S=“aAbcbbbcccbd”; so sánh S[4]= ‘b’ với S[11]= ‘d’ khác nhau thay vị trí S[5] bằng S[11] ta được S=“aAbcbdbcccbd”. Kết quả S= “aAbcbdbcccbd”
Cách tiếp cận: Str=”aaaAAbbcccbd”
Tôi thực hiện di chuyển các phần tử khác nhau rồi đưa về phía trước của xâu theo yêu cầu đề bài.
– Duyệt từ đầu đến cuối xâu
– Cần so sánh phần tử thứ i và phần tử thứ j
+ Nếu 2 phần tử khác nhau thì tại vị trí thứ i+1 gán phần tử vị trí thứ j, di chuyển j một đơn vị, lấy vị trí thứ i+1 so sánh với kí tự vị trí thứ j.
+ Nếu 2 phần tử giống nhau thì di chuyển j một đơn vị
– Kết quả là copy từ đầu xâu đến vị trí thứ i+1 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.
• Tạo hai con trỏ i và j đều được khởi tạo bằng 0.
• Bây giờ chạy một vòng lặp cho đến khi j < độ dài của chuỗi đầu vào S và thực hiện các bước sau:
o Khi ký tự thứ i bằng với ký tự thứ j thì tăng j lên 1 đơn vị o Nếu ký tự i không bằng ký tự j thì hãy thực hiện các bước sau:
▪ Tăng i lên 1 đơn vị
▪ Cập nhật ký tự ở vị trí thứ i với ký tự ở vị trí thứ j.
• Bây giờ chuỗi cần tìm cuối cùng của chúng ta sẽ là đoạn [0, i].
Độ phức tạp thời gian: O (N)
Link mô phỏng: https://youtu.be/5DzUbORvp4U

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

1.2.3. Hai con trỏ di chuyển trên hai mảng hoặc xâu
Đây là dạng bài tập dùng trên hai mảng, chúng ta có thể di chuyển một con trỏ ở đầu mảng thứ nhất và con trỏ kia ở cuối mảng thứ hai hoặc hai con trỏ ở đầu 2 mảng, một con di chuyển chậm và con trỏ kia di chuyển nhanh hơn tùy thuộc bài toán để chọn 1 trong 2 dạng dưới đây. Dạng thuật toán này thì thực hiện 3 bước sau:
Bước 1: Gán hai con trỏ i, j đầu
Bước 2: Hai con trỏ di chuyển về phía sau
Bước 3: Điều kiện để dừng một trong hai con trỏ di chuyển đến cuối Hình ảnh minh họa hai con trỏ ở đầu hai mảng hoặc xâu: