MỞ ĐẦU
Ly ́ do cho ̣n đề tài
Để đạt kết quả cao trong kỳ thi tuyển chọn học sinh giỏi môn Tin học, học sinh cần có kiến thức vững về thuật toán để giải quyết các bài toán khó Sau khi tìm ra thuật toán, học sinh sẽ lựa chọn ngôn ngữ lập trình (NNLT) phù hợp để thực hiện giải bài toán theo yêu cầu Việc này chỉ có thể được thực hiện khi người học tiếp xúc với một hệ thống bài toán được tổ chức chặt chẽ, giúp hình thành thói quen tư duy và kỹ thuật lập trình cơ bản.
Để hỗ trợ học sinh giải quyết bài toán Tin học một cách tối ưu, chúng tôi đã phát triển một số kỹ thuật cơ bản trong quá trình bồi dưỡng học sinh giỏi Những kỹ thuật này rất quan trọng và giúp nâng cao hiệu quả trong việc truyền đạt kiến thức và kỹ năng lập trình cho học sinh.
Theo chương trình mới của Bộ Giáo dục, giáo viên được khuyến khích dạy ngôn ngữ lập trình mới thay thế Pascal Vì vậy, chúng tôi đã phát triển tài liệu tham khảo bằng ngôn ngữ lập trình C++ và Python dành 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ọc sinh giỏi”.
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áo viê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ông
Đố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ông qua hệ thống các bài tập được phân loại kỹ lưỡng.
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.
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.
NỘI DUNG NGHIÊN CỨU
Cơ sở lý luâ ̣n
Trong quá trình ôn luyện đội tuyển, học sinh được trang bị nhiều phương pháp tối ưu thuật toán như tham lam, chia để trị, quay lui, quy hoạch động, Z Algorithm và KMP Tuy nhiên, để đạt được hiệu quả tối ưu nhất, việc kết hợp các phương pháp này với kỹ thuật khác và tổ chức dữ liệu hợp lý là rất quan trọng Nếu chỉ xem xét từng phương pháp một cách độc lập, chúng sẽ không mang lại giá trị tối ưu cao nhất.
Các kỹ thuật trong sáng kiến này là những phương pháp cơ bản, dễ tiếp cận và mang lại hiệu quả cao trong việc giảm độ phức tạp của thuật toán, hướng tới việc tối ưu hóa thuật toán một cách tốt nhất.
Học sinh dần được làm quen với NNLT C++ hoặc Python.
Thực trạng
Mặc dù đã có một số tài liệu đề cập đến kỹ thuật tăng tốc chương trình, nhưng vẫn thiếu phân tích sâu về tư duy và lựa chọn cài đặt chương trình tối ưu Việc tổng hợp các kỹ thuật để học sinh có thể so sánh các cách giải, kết quả và độ phức tạp còn rất hạn chế, và hệ thống bài tập hiện có cũng không phong phú.
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
Để tìm giá trị lớn nhất trong một mảng số, ta khởi tạo biến kết quả max bằng giá trị đầu tiên của mảng, gọi là biến lính canh Sau đó, ta lần lượt kiểm tra các phần tử từ thứ 2 đến n; nếu phát hiện phần tử nào lớn hơn giá trị của "lính canh" ban đầu, ta sẽ cập nhật "lính canh" bằng giá trị mới.
+ Lần lượt với i=2 đến n, so sánh số ai với max, nếu ai > max thì gán max=ai b Nội dung và cài đặt chương trình
Các bước thực hiện giải thuật:
Bước 1: Nhập N và dãy a1,a2, , aN
Bước 3: Nếu i > N thì đưa ra giá trị Max và csmax rồi kết thúc;
Bước 4: Nếu ai > Max thì Max ←ai, csmax ←i;
Bước 5: i ← i + 1 rồi quay lại Bước 3;
#include using namespace std; long long n,max,csmax; long long a[10000]; void doctep()
{ifstream fi ("max.inp"); fi>>n; for (int i=0;i>a[i]; fi.close();
{ long long max=a[0];//dat linh canh csmax=0; for(int i=1;i
