SKKN Một số biện pháp nâng cao hiệu quả công tác bồi dưỡng học sinh giỏi môn Tin học bằng ngôn ngữ lập trình C++

.inp
Marathon.out
5 3
9 1 8 6 3
2 5 4
Ý tưởng:
Sử dụng mảng với kiểu dữ liệu pair với chỉ số first lưu thời gian chạy của thì sinh, chỉ số second lưu số báo danh của thí sinh.
Xây dựng hàm bool cmp() để xác định tiêu chí sắp xếp.
Sử dụng hàm sort với tiêu chí sắp xếp cmp để sắp xếp thí sinh theo thời gian chạy tăng dần.
Duyệt mảng sau khi sắp xếp để xuaart kết quả.
Chương trình giải:
Lưu ý:
Trong các bài toán sắp xếp với nhiều tiêu chí khác nhau, để sử dụng hàm sort() sẵn có ta cần xây dựng hàm bool cmp() để xác định tiêu chí sắp xếp. Khi đó ta sắp xếp với lời gọi: sort(a+1,a+1+n,cmp); việc này sẽ giúp ta tiết kiệm thời gian viết lại code hàm sắp xếp.
Bài 2: SEQ (đề thi HSG tỉnh Nghệ An 2016-2017)
Cho dãy số gồm n số nguyên a1, a2, , an và 2 số nguyên không âm L, R (L ≤ R).
Yêu cầu:
Đếm số cặp (i, j) thỏa mãn điều kiện: i ≤ j và L ≤ |ai++aj| ≤ R .
Dữ liệu vào:
Từ file văn bản SEQ.INP gồm:
Dòng đầu tiên chứa 3 số nguyên n, L, R (n ≤ 105 ; 0 ≤ L ≤ R ≤ 109)
Dòng thứ hai chứa n số nguyên dương a1, a2,, an (ai ≤ 109)
Kết quả:
Ghi ra file văn bản SEQ.OUT
Gồm một số nguyên duy nhất là số lượng cặp (i, j) đếm được.
Ví dụ:
SEQ.INP
SEQ.OUT
3 0 1
1 -1 2
4
Hạn chế:	- Có 50% số test ứng với 0 < n ≤ 103
- Có 50% số test ứng với 103 < n ≤ 105
Ý tưởng:
- Sử dụng kết hợp các thuật toán: Sử dụng kĩ thuật mảng nhớ tổng tiền tố; Sắp xếp; Tìm kiếm nhị phân.
- Thực hiện:
+ Đọc giá trị của dãy, kết hợp tạo mảng nhớ tổng a, với a[i] là tổng i phần tử đầu của dãy.
+ Sắp xếp các giá trị trong mảng theo thứ tự tăng dần.
+ Xét các giá trị a[i] với 2≤i≤n, với mỗi giá trị a[i] ta cần tìm kiếm nhị phân 2 vị trí:
Vị trí d: là vị trí mà a[d] bé nhất nhưng a[d] ≥ a[i]-r Vị trí c: là vị trí mà a[c] lớn nhất nhưng a[c] ≤ a[i]-l
Và lúc này số lượng đoạn con thỏa mãn kq sẽ tăng lên kq= kq+(c-d+1); Sau khi thực hiện n-1 lần thì số đoạn con thỏa mãn đề bài chính bằng kq.
Chương trình giải quyết bài toán:
Chuyên đề 4: Xử lý xâu ký tự.
Xử lý xâu ký là yêu cầu thường gặp trong dạy học lập trình và cũng là bài toán thường xuyên xuất hiện trong các đề thi HSG. Các dạng bài toán phổ biến như: Duyệt các phần tử, duyệt xâu con trên xâu; biến đổi, xử lý trên xâu; lưu trữ và xử lý số lớn. Để dễ dàng trong việc giải các bài toán về xâu, ta cần nắm rõ các hàm xử lý trên kiểu dữ liệu xâu để vận dụng một cách linh hoạt vào từng bài tập cụ thể.
Một số thao tác mở rộng với xâu trong C++
Hàm chuyển xâu s thành số n kiểu int:	n = atoi(s.c_str());
Hàm chuyển xâu s thành số n kiểu long:	n = atol(s.c_str());
Hàm chuyển xâu s thành số n kiểu long long: n = atoll(s.c_str());
Hàm chuyển xâu s thành số n kiểu float:	n = atof(s.c_str());
Hàm chuyển số n thành xâu s:
stringstream convert; covert << n; s = convert.str();
Hàm s.size(); lấy chiều dài của xâu s.
s.find(x, vt): Tìm kiếm vị trí đầu tiên xuất hiện xâu x trong xâu s.
s.rfind(x, vt): Tìm kiếm vị trí cuối cùng xuất hiện xâu x trong xâu s.
- .....
Bài toán áp dụng: Chuẩn hóa văn bản:
Một văn bản được gọi là văn bản chuẩn nếu:
Hai từ liền nhau có duy nhất một dấu cách trống.
Dấu ngắt câu (dấu chấm, dấu phẩy, dấu chấm phẩy, dấu chấm hỏi, dấu chấm than) được đặt sát vào từ ngay trước nó, sau đó mới đến dấu cách trống.
Dấu mở ngoặc đặt sát vào phía bên trái của từ bắt đầu mở ngoặc.
Dấu đóng ngoặc đặt sát bên phải từ cuối cùng được đóng ngoặc. Cho một xâu ký tự. Hãy đưa ra xâu đó ở dạng văn bản chuẩn.
Dữ liệu vào: tệp văn bản CHVB.inp chứa một xâu ký tự.
Kết quả ra: Ghi vào tệp văn bản CHVB.inp gồm 1 dòng là kết quả của bài toán.
Ý tưởng:
Xóa các dấu cách thừa: dùng lệnh for lùi duyệt để tìm và xóa.
Xử lý với các dấu câu:
+ Dùng xâu phụ để chứa các dấu câu: s1=".,;?!)";
+ Duyệt từng ký tự i của xâu s:
+/ Nếu s[i] có mặt trong xâu s1 thì xóa dấu cách phía trước nếu có và thêm dấu cách phía sau nếu chưa có.
+/ Nếu s[i] là dấu ngoặc mở thì xóa dấu cách phía sau nếu có và thêm dấu cách phía trước nếu chưa có.
Chương trình giải:
Chuyên đề 5: Đệ quy, quay lui;
Khái niệm về đệ quy.
Ta nói một khái niệm là đệ qui nếu nó gao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó.
Trong tin học, hàm đệ quy là hàm mà bản thân nó có thể gọi lại chính nó.
Đặc điểm của hàm đệ quy:
Trong hàm đệ quy có lời gọi đến chính hàm đó.
Mỗi lần gọi lại hàm đó thì kích thước bài toán đã thu nhỏ hơn trước.
Có một trường hợp đặc biệt: đó là trường hợp suy biến.
Hiệu lực của đệ quy:
Ưu điểm:	Sáng sủa, dễ hiểu, thủ tục rất gọn, đơn giản
Nhược điểm: Đệ quy quay lui, thường tính toán nhiều, thời gian thực hiện rất lâu.
Thiết kế giải thuật đệ quy
Ba bước thiết kế đệ quy
Tham số hóa bài toán: xác định các tham số in và out
Lời gọi đệ quy: Đưa bài toán về bài toán cùng loại nhỏ hơn, dần tiến tới trường hợp suy biến
Tìm trường hợp suy biến (điểm dừng)
Bài toán áp dụng đệ quy:
Bài 1: Đệ quy cơ bản.
Cho 2 số tự nhiên a và n. Hãy tính giá trị an %(109+7)
Dữ liệu vào: Đọc từ tệp DQ1.Inp gồm một dòng duy nhất chứa 2 số nguyên a, n (1<=a, n<=109).
Dữ liệu ra: Ghi kết quả ra tệp DQ1.Out một số nguyên là kết quả của bài toán. Ví dụ
DQ1.inp
DQ1.out
2 8
256
Ý tưởng:
Cách 1: Đặt hằng e =1000000007; Khởi tạo kq =1;
Dùng lệnh for lặp lại n lần. Mỗi lần gán kq=(kq*a)%e.
Việc chia lấy dư cho e ngay lập tức sẽ làm cho giá trị kq luôn nhỏ hơn e và sẽ tránh được việc vượt phạm vi lưu trữ. Cách làm này chưa đảm bảo thời gian chạy 1 giây khi n lớn. Vì vậy ta cần cải tiến như các 2 dưới đây.
Cách 2: Ta có thể dùng đệ quy để tính kết quả theo nguyên tắc sau.:
𝑛	𝑛
𝑎𝑛 % 𝑒 = (𝑎2 % 𝑒) (𝑎2 % 𝑒)	𝑛ế𝑢 𝑛 𝑐ℎẵ𝑛
𝑛	𝑛
𝑎𝑛 % 𝑒 = (𝑎2 % 𝑒) (𝑎2 % 𝑒) ∗ 𝑎	𝑛ế𝑢 𝑛 𝑙ẻ
Khi đó ta có chương trình:
Lưu ý: - Không nên sử dụng hàm pow(a,n) có sẵn, vì sử dụng hàm này có một số trường hợp cho kết quả không đúng mong muốn.
Giá trị cuả a và n có thể là rất lớn, nên ta cần cân nhắc trong việc chọn kiểu dữ liệu và lựa chọn thuật toán.
Trong bài toán này ta đã sử dụng đệ quy cơ bản để làm giảm thời gian thực hiện chương trình.
Bài 2: Đệ quy quay lui:
Cho số tự nhiên N.
Hãy liệt kê ra các hoán vị của tập các số tự nhiên từ 1 đến N.
Dữ liệu vào: Đọc từ tệp Hoanvi.Inp gồm một dòng duy nhất chứa 2 số nguyên a, n (1<=30).
Dữ liệu ra: Ghi kết quả ra tệp Hoanvi.Out mỗi dòng là 1 hoán vị. Ví dụ
Hoanvi.inp
Hoanvi.out
3
123
132
213
231
312
321
Ý tưởng:
Ta biết khi xây dựng hoán vị thì các thành phần xây dựng không được phép lặp lại. Vì vậy ta phải sử dụng một mảng đánh dấu d[] để đánh dấu cho các giá trị đã được chọn, d[j] = 0 có nghĩa j chưa được chọn, d[j] = 1 nghĩa j đã được chọn.
Chuyên đề 6: Quy hoạch động.
Nguyên lý cơ bản của quy hoạch động
Chia bài toán cần giải thành các bài toán con.
Sử dụng bảng để lưu trữ lời giải của các bài toán con đã được giải.
Để xác định giải thuật một bài toán quy hoạch động cần xác định các yếu tố sau:
Tên và ý nghĩa các biến phục vụ công thức lặp.
Cách khai báo các biến đó.
Công thức lặp chuyển từ một bước sang bước tiếp theo.
Giá trị khởi tạo của các biến tham gia tính lặp.
Tham số điều khiển lặp thay đổi từ đâu đến đâu.
Kết quả lưu ở đâu, làm thế nào để xuất ra kết quả.
Bài toán áp dụng: Dãy con tăng dài nhất.
Cho dãy số nguyên A = a1,a2...,an. Dãy con của A là một cách chọn trong dãy A một số phần tử giữ nguyên thứ tự.
Yêu cầu: Hãy tìm một dãy con của A tăng dần có số lượng phần tử nhiều nhất.
Dữ liệu vào: file văn bản QHĐ.INP, gồm 2 dòng:
Dòng 1: ghi số N là số lượng phần tử của dãy N<=1000
Dòng2: ghi N số nguyên ai cách nhau ít nhất một dấu cách |ai|<=100000 Kết quả: ghi ra file văn bản QHD.OUT, gồm 2 dòng:
Dòng 1: ghi M là số lượng phần tử của dãy con
Dòng 2: ghi lần lượt giá trị của các số trong dãy A ban đầu
Ví dụ:
QHD.INP
QHD.OUT
10
1 2 4 8 9 5 7 8 20 9
7
1 2 4 5 7 8 9
Ý tưởng:
Dữ liệu: + Sử dụng mảng D: d[i] độ dài dãy con tăng dài nhất chứa phần tử a[i] tình từ phần tử 1 đến phần tử i.
+ Sử dụng mảng P: p[i] là chỉ số phần tử mà a[i] cần móc nối ở bước thứ i, để dãy con tăng dần kết thúc ở a[i].
Khai báo: Các phần tử của mảng P, D cùng kiểu với N.
- Khởi tạo D[1]=1; P[1]=0;
Công thức lặp:
D[i]=1; P[i]=0
Duyệt các giá trị j=1 đến i-1:
Nếu D[j]+1>D[i] thì P[i]=j; D[i]=D[j]+1;
Phạm vi lặp i=2 đến n.
Kết quả:	+ M= max của mảng D.
+ Duyệt dãy con từ cuối về đầu để lấy kết quả.
Chương trình giải:
Tổ chức thi thử, đánh giá, kinh nghiệm làm bài thi.
Tổ chức thi thử, đánh giá học sinh:
Tổ chức thi thử.
Hàng năm đơn vị chúng tôi đều kết hợp các trường trong huyện tổ chức thi thử, chung đề chung địa điểm để tập duyệt từ tâm lý đến kiến thức cho học sinh, đồng thời đánh giá mức độ của học sinh so với tổng quan các trường trong huyện.
Ngoài ra, trường chúng tôi thường tổ chức thi thử mỗi tháng một lần. Giáo viên trực tiếp bồi dưỡng hoặc đồng nghiệp cùng bộ môn của trường ra đề thi, chấm thi. Các khâu thực hiện đều đảm bảo đúng quy trình tổ chức thi.
Ra đề thi:
Đề thi phải bám sát cấu trúc đề mà Sở GD&ĐT ban hành.
Đề thi cần phải có độ phân hóa tốt để đánh giá năng lực học sinh.
Độ khó của đề thi phụ thuộc vào từng giai đoạn ôn tập và tăng dần theo quá trình đào tạo.
Viết chương trình tham khảo và tạo bộ test chấm.
Để tạo ra bộ test chấm cần có chương trình chuẩn giải quyết bài toán.
Sau khi có chương chuẩn, ta sử dụng chương trình tạo test tự động. Lưu ý phần code để tạo test đầu vào phải đúng cấu trúc tệp inp như đề ra.
Chỉnh sửa tệp đầu vào để quét hết tất cả các tình huống của bài toán, đảm bảo số lượng test đúng như ràng buộc dữ liệu đầu vào cho trong bài toán, chạy chương trình để tạo tệp đầu ra tương ứng.
Chấm thi: Sử dụng phần mềm Themis chấm bài tự động theo bộ test đáp áp đã tạo. Lưu ý cấu hình bài thi đúng đề ra.
Đánh giá học sinh..
Để đánh giá đúng năng lực của học sinh, chúng ta cần theo dõi cả quá trình học tập và rèn luyện. Ta có thể đánh giá năng lực lập trình của học sinh ở mức độ cơ sở và nâng cao, thể hiện ở các mặt:
Tiêu chí đánh giá
Mức cơ sở
Mức nâng cao

Kiến thức về thuật toán:
- Nắm được các thuật toán cơ bản: tìm max, min, tính ước c