ĐẶ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. 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. 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. Đố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.
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. 3 skkn 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. 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. 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 4 skkn 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. 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ỏ. 5 skkn 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. Một số dạng về thuật toán hai con trỏ. 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.
6 skkn 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…. 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, ….
Dữ liệu ra. Ghi kết quả tệp DAONGUOC.OUT Ví dụ: DAONGUOC.OUT 5 54321 12345 Phân tích: Xét ví dụ sau.