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 đó, việc lựa chọn ngôn ngữ lập trình (NNLT) phù hợp để lập trình dựa trên thuật toán đã tìm ra là rất quan trọng Để hình thành những kỹ năng này, người học cần tiếp xúc với một hệ thống bài toán được tổ chức chặt chẽ, từ đó phát triển thói quen tư duy và kỹ thuật lập trình cơ bản.
Chúng tôi mong muốn hỗ trợ học sinh giải quyết các bài toán Tin học một cách tối ưu Qua quá trình bồi dưỡng học sinh giỏi, chúng tôi đã phát hiện và rút ra một số kỹ thuật cơ bản, quan trọng giúp nâng cao hiệu quả trong việc phát triển 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 (NNLT) mới thay vì Pascal Do đó, chúng tôi đã phát triển tài liệu tham khảo bằng NNLT C++ và Python để hỗ trợ 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ư phương pháp 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 cao nhất, việc kết hợp những kỹ thuật này với các phương pháp khác và tổ chức dữ liệu một cách 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 ý nghĩa và hiệu quả tối ưu cần thiế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ả đáng kể 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 hiệu quả 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ó tài liệu đề cập đến các kỹ thuật tăng tốc chương trình, nhưng vẫn thiếu phân tích về tư duy và cách 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 so sánh các phương pháp giải, kết quả và độ phức tạp vẫn còn hạn chế, và hệ thống bài tập cũng chưa 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 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ừ vị trí thứ hai đến cuối mảng; nếu phát hiện phần tử nào lớn hơn giá trị của "lính canh", ta sẽ cập nhật giá trị của "lính canh".
+ 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
