Sáng kiến kinh nghiệm THPT: Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi

Mục đích chính của sáng kiến "Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi" là giới thiệu đến giáo viên và học sinh một số kỹ thuật cơ bản dành cho đối tượng HSG khối THPT: Giúp các em học giỏi môn Tin học đạt kết quả cao; Tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho học sinh, giáo viên dạy Tin học bậc THPT.
Nội dung trích xuất từ tài liệu:
Sáng kiến kinh nghiệm THPT: Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT DIỄN CHÂU 5 SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI MỘT SỐ KỸ THUẬT LẬP TRÌNH CƠ BẢN GIÚP ĐẠT HIỆU QUẢ CAO TRONG BỒI DƯỠNG HỌC SINH GIỎI Lĩnh vực: Tin họcNhóm người thực hiện: Nguyễn Thị Luận – Trường THPT Diễn Châu 5Số điện thoại : 0989868255 Email: nguyenluan.dc5@gmail.com Trần Thị Thủy – Trường THPT Nghi Lộc 4Số điện thoại : 0848919111 Email: tttpdl@gmail.comNăm thực hiện : 2022 NGHỆ AN, NĂM 2022 1. MỞ ĐẦU 1.1. Lý do cho ̣n đề tài Chúng ta biết rằng để có kết quả cao trong kì thi tuyển chọn học sinh giỏimôn Tin học nói chung thì phải có vốn kiến thức tốt về thuật toán để giải được cácbài toán khó, sau đó học sinh lựa chọn NNLT để lập trình dựa vào thuật toán đãtìm được và giải bài toán theo yêu cầu. Điều này lại chỉ được hình thành sau khi người học được tiếp xúc với một hệthống các bài toán được tổ chức cẩn thận, chặt chẽ. Hệ thống này giúp xây dựngđược các thói quen tư duy cơ bản cũng như các kỹ thuật cơ bản trong lập trình. Với mong muốn giúp các em giải các bài toán trong Tin học theo hướng tốiưu nhất, qua quá trình bồi dưỡng học sinh giỏi, chúng tôi đã phát hiện, rút ra đượcmột số kỹ thuật cơ bản, rất quan trọng giúp đạt hiệu quả cao trong bồi dưỡng kiếnthức, kỹ năng lập trình cho học sinh. Mặt khác, theo chương trình mới của Bộ giáo dục khuyến khích giáo viêndạy NNLT mới thay Pascal nên chúng tôi viết chương trình bằng NNLT C++ vàPython để làm tài liệu tham khảo mới cho giáo viên và học sinh. Từ những lý do trên chúng tôi đã mạnh dạn trình bày sáng kiến kinh nghiê ̣m:“Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng họcsinh giỏi”. 1.2. Mu ̣c đích nghiên cứu Mục đích chính của sáng kiến là giới thiệu đến giáo viên và học sinh một sốkỹ thuật cơ bản dành cho đối tượng HSG khối THPT: - Giúp các em học giỏi môn Tin học đạt kết quả cao - Tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho học sinh, giáoviên dạy Tin học bậc THPT - Sử dụng NNLT C++ và Python trong chương trình giáo dục phổ thông2018 sắp tới. 1.3. Đố i tươ ̣ng nghiên cứu - Giáo viên và học sinh tham gia bồi dưỡng HSG Tin học. - Tổng hợp lại một số kỹ thuật giúp học sinh phát triển tư duy lập trình thôngqua hệ thống các bài tập được phân loại kỹ lưỡng. 1.4. Phương pháp nghiên cứu - Phương pháp điều tra, nghiên cứu tài liệu. - Phương pháp phân tích, tổng hợp. - Phương pháp khảo sát thực tiễn. - Phương pháp tổng kết kinh nghiệm. 1.5. Phạm vi nghiên cứu Phạm vi nghiên cứu: Một số kỹ thuật cơ bản để tăng tốc chương trình giúpđạt hiệu quả cao trong bồi dưỡng HSG môn Tin học. 1 2. NỘI DUNG NGHIÊN CỨU 2.1. Cơ sở lý luâ ̣n Trong quá trình ôn luyện đội tuyển, học sinh được dạy khá nhiều về cácphương pháp tối ưu thuật toán như: phương pháp tham lam, chia để trị (sắp xếpnhanh, chặt nhị phân…), quay lui, quy hoạch động, Z Algorithm, KMP… Nhưngnếu không biết kết hợp với những kỹ thuật khác, không biết cách tổ chức dữ liệu,những phương pháp này xét về phương diện độc lập sẽ không đạt được sự tối ưucao nhất và không có ý nghĩa. Các kỹ thuật được giới thiệu trong sáng kiến đều là những kỹ thuật rất cơbản, đơn giản và rất dễ tiếp cận đồng thời đem lại một hiệu quả rất đáng kể trongviệc giảm độ phức tạp thuật toán, tiến tới một thuật toán tối ưu nhất. Học sinh dần được làm quen với NNLT C++ hoặc Python. 2.2. Thực trạng Trên thực tế đã có một số tài liệu đề cập đến những kỹ thuật để tăng tốcchương trình, tuy nhiên chưa đi sâu vào phân tích cách tư duy, cách lựa chọn và càiđặt chương trình tối ưu, đặc biệt việc tổng hợp lại các kỹ thuật giúp học sinh có thểso sánh các cách giải, các kết quả, độ phức tạp còn rất ít, hệ thống bài tập cũngkhông nhiều. 2.3. Các kĩ thuật lập trình cơ bản 2.3.1. Kỹ thuật lính canh (Sentinel) - Là kĩ thuật sử dụng 1 biến (mang giá trị đặc biệt) làm “chốt chặn”. - Mục đích chính: tạo điều kiện dừng cho các vòng lặp không xác định sốlần lặp. - Xét một số bài toán cụ thể sau: 2.3.1.1. Bài toán 1 – Tìm max / min Cho dãy gồm N số nguyên a1, a2,…,aN. Hãy tìm giá trị lớn nhất của dãy số. a. Ý tưởng của thuật toán - Xét bài toán tìm kiếm giá trị lớn nhất trong một mảng số, đặt biến kết quảmax bằng giá trị đầu tiên trong mảng (biến này gọi là biến lính canh), xét lần lượtphần tử thứ 2 đến n, nếu có một phần tử nào lớn hơn “lính canh” ban đầu thì thựchiện ...