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

 MỤC LỤC 
 Trang 
1. MỞ ĐẦU . .1 
 1.1. Lý do chọn đề tài ...1 
 1.2. Mục đích nghiên cứu .1 
 1.3. Đối tượng nghiên cứu ....2 
 1.4. Phương pháp nghiên cứu ...2 
 1.5. Phạm vi nghiên cứu ...2 
2. NỘI DUNG NGHIÊN CỨU .2 
 2.1. Cơ sở lý luận .................................................................................. ...2 
 2.1.1. Khái niệm về kỹ thuật lập trình ..2 
 2.1.2. Vai trò của kỹ thuật lập trình ..2 
 2.2. Thực trạng ......2 
 2.3. Các kỹ thuật lập trình nâng cao .3 
 2.3.1. Kỹ thuật mảng đánh dấu .3 
 2.3.1.1. Bài toán 1 - Số nhỏ nhất ...3 
 2.3.1.2. Bài toán 2 – Sàng nguyên tố ....5 
 2.3.2. Kỹ thuật mảng đếm .....7 
 2.3.2.1 – Bài toán 1 - Tần số xuất hiện .7 
 2.3.2.2. Bài toán 2 – Hai lớp học ..9 
 2.3.2.3. Bài toán 3 – Sắp xếp đếm phân phối ..10 
 2.3.3. Kỹ thuật quay lui ...11 
 2.3.3.1. Bài toán 1 – In ra tất cả các hoán vị của n số tự nhiên đầu tiên .13 
 2.3.3.2. Bài toán 2 – Liệt kê các dãy nhị phân độ dài N ...14 
 2.3.5. Kĩ thuật tham lam (greedy) ...14 
 2.3.5.1. Bài toán 1 – Tìm đường đi ngắn nhất 15 
 2.3.5.2 Bài toán 2 – Xếp lịch ..17 
 2.3.4. Kỹ thuật quy hoạch động ..19 
 2.3.4.1. Bài toán 1 – Bài toán kinh điển tìm số Fibonaci thứ n ..20 
 2.3.4.2. Bài toán 2 – Vali ....21 
 2.4. Đánh giá các kỹ thuật ...22 
 2.4.1. Đánh giá các kỹ thuật thông qua thời gian thực hiện 22 
 2.7.2.2. Nội dung và phương pháp khảo sát ...45 
 2.7.2.2.1. Nội dung khảo sát ...45 
 2.7.2.2.2. Phương pháp khảo sát và thang đánh giá 45 
 2.7.2.3. Đối tượng khảo sát .46 
 2.7.2.4. Kết quả khảo sát về sự cấp thiết và tính khả thi của các giải pháp đã đề
 xuất ..47 
 2.7.2.4.1. Sự cấp thiết của các giải pháp đã đề xuất 47 
 2.7.2.4.2. Tính khả thi của các giải pháp đề xuất ..48 
 2.7.3. Kết quả đạt được trong công tác bồi dưỡng HSG .48 
 3. KẾT LUẬN VÀ KIẾN NGHỊ ...49 
 3.1. Kết luận 49 
 3.2. Kiến nghị ..50 
TÀI LIỆU THAM KHẢO ..51 
PHỤ LỤC 1 ......52 
 1. Kỹ thuật mảng đánh dấu .52 
 1.1. Bài toán 1- Số nhỏ nhất 52 
 1.2. Bài toán 2 – Sàng nguyên tố 52 
 2. Kỹ thuật mảng đếm .53 
 2.1. Bài toán 1 – Tần số xuất hiện ...53 
 2.2. Bài toán 2 – Hai lớp học ..54 
 2.3. Bài toán 3 – Sắp xếp đếm phân phối ....55 
 3. Kĩ thuật quay lui ..56 
 3.1. Bài toán 1: In ra tất cả các hoán vị của n số tự nhiên đầu tiên (0<N<10) 
 ..56 
 3.2. Bài toán 2: Liệt kê các dãy nhị phân độ dài N .57 
 4. Kỹ thuật tham lam ...58 
 4.1. Bài toán 1 – Tìm đường đi ngắn nhất ..58 
 4.2. Bài toán 2 – Xếp lịch ...62 
 5. Kỹ thuật QHĐ .....63 
 5.1. Bài toán 1 – Bài toán kinhiển đ tìm số Fibonaci thứ n 63 
 5.2. Bài toán 2 – Vali ..64 
 DANH MỤC TỪ VIẾT TẮT 
TT Từ viết tắt Nghĩa từ viết tắt 
1 NNLT Ngôn ngữ lập trình 
2 THPT Trung học phổ thông 
3 HSG Học sinh giỏi 
4 QHĐ Quy hoạch động 
5 HS Học sinh 
 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 nâng cao 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. 
 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 nâng cao để tăng tốc chương trình giúp 
đạt hiệu quả cao trong bồi dưỡng HSG các cấp môn Tin học. 
 2. NỘI DUNG NGHIÊN CỨU 
 2.1. Cơ sở lý luận 
 2.1.1. Khái niệm về kỹ thuật lập trình 
 Kỹ thuật lập trình là kỹ thuật thực thi một giải pháp phần mềm (cấu trúc dữ 
liệu + giải thuật) dựa trên nền tảng một phương pháp luận (methodology) và một 
hoặc nhiều ngôn ngữ lập trình phù hợp với yêu cầu đặc thù của ứng dụng. 
 2.1.2. Vai trò của kỹ thuật lập trình 
 Trẻ em là thế hệ của tương lai, trẻ em cũng cần học các kỹ năng giúp cho trẻ 
có thể làm được những điều mới chứ không hoàn toàn đi theo những gì đã được 
dạy trong quá khứ. Theo nhiều chuyên gia, lập trình là một trong những kỹ năng 
quan trọng trẻ nên được trang bị từ sớm để giúp trẻ phát triển tư duy tính toán và
các kỹ năng tư duy phản biện, kỹ năng trình bày, kỹ năng quản lý thời gian, làm 
việc nhóm.... và quan trọng hơn hết là được thỏa sức sáng tạo “thế giới trong mơ” 
của mình một cách sinh động trên máy tính. Tư duy tính toán (Computational 
Thinking) là cách tư duy sao cho không những giải quyết được vấn đề mà còn có
thể đưa vào máy tính cách giải quyết vấn đề. Nhờ đó, vấn đềsẽ được máy tính xử 
lý một cách chính xác, nhanh chóng và có thể tự động hoàn toàn. Tư duy tính toán
là nền tảng của Trí tuệ nhân tạo, Học máy và nhiều công nghệ khác của tương lai.
Khi được phát triển kỹ năng này từ sớm, trẻ sẽ biết cách tiếp cận giải quyết vấn đề 
từng bước một cách logic và dần biết được cách giải quyết các vấn đề lớn, phức
tạp. 
 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ốc 
chươ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à icà 
đặt chương trình tối ưu, đặc biệt việc tổng hợp lại các kỹ thuật từ cơ bản đến nâng 
 2 
 Tôi sẽ sử dụng mảng B để đánh dấu sự xuất hiện của các phần tử trong mảng 
 6
A. Vì các số ai trong mảng A có giá trị 1 ≤ ai ≤ 10 nên kích thước của mảng B tối 
thiểu là 106. Tôi đánh dấu: B[i] = 1 nếu số i xuất hiện trong mảng A và B[i]=0 nếu 
i không xuất hiện trong A. 
 Khi đó ta có đoạn chương trình đánh dấu đơn giản như sau: 
 memset(B,0,sizeof(B)); 
 fi >> N; 
 for (int i =1; i <= N; i++) 
 { fi >> A[i]; // Đọc ra phần tử thứ i trong mảng A 
 B[A[i]] = 1; // Đánh dấu phần tử A[i] có xuất hiện trong mảng A 
 } 
 Sau khi đã đánh dấu thì việc tìm số nào chưa xuất hiện trở nên rất đơn giản. 
Duyệt từ đầu mảng đến cuối mảng B: Gặp số nào mà B[i]=0 thì dừng lại; và i 
chính là số nguyên dương đầu tiên chưa xuất hiện trong mảng A. Ta có đoạn code 
như sau: 
 i=1; 
 while (B[i]= =1 ) i++; 
 Minh họa từng bước quá trình đánh dấu: 
 6 7 1 2 5 3 2 6 
 Kết quả chạy từng bước quá trình đánh dấu 
 - Ban đầu B[i] = 0 với mọi i (1≤i ≤ 106) 
 0 0 0 0 0 0 0 0  0 
 - Lần 1: - Lần 5 
 + Đọc ra A[1]=6 + Đọc raA[ 5]=5 
 + Đánh dấu B[6] = 1 + Đánh dấu B[5] = 1 
 0 0 0 0 0 1 0 0  0 1 1 0 0 1 1 1 0  0 
 - Lần 2: - Lần 6 
 + Đọc raA[2] =7 + Đọc raA[ 6]=3 
 + Đánh dấu B[7] = 1 + Đánh dấu B[3] = 1 
 0 0 0 0 0 1 1 0  0 1 1 1 0 1 1 1 0  0 
 4 
 Ví dụ: 
 Input Output 
 10 4 
 2 3 5 7 
 20 8 
 2 3 5 7 11 13 17 19 
 a. Ý tưởng thuật toán 
 - Tạo mảng đánh dấu snt để đánh dấu cho tất cả các phần tử có giá trị từ 2 
 đến N -1 và mặc định tất cả đều là số nguyên tố (quy ước có giá trị bằng 1). 
 - Xét số nguyên tố nhỏ nhất đầu tiên – giả sử x, đánh dấu tất cả các bội số 
của x là: 2x, 3x, 4x,nằm trong đoạn [x, N) không phải số nguyên tố (quy ước có 
giá trị bằng 0). 
 - Tìm số tiếp theo được đánh dấu là số nguyên tố trong đoạn [x, N). Nếu 
không còn số nào, thoát chương trình. Nếu còn, gán nócho x và lặp lại bước 2. 
 - Khi kết thúc giải thuật, các số không bị nhđá dấu bằng 0 là các số nguyên tố
 - Đoạn chương trình con thể hiện mảng đánh dấu như sau: 
 void sangnt() 
 { int i,j; 
 //Đánh dấu các số từ 2 đến N là nguyên tố 
 for (i=2; i<N; i++) snt[i]=1;//Sử dụng mảng đánh dấu snt 
 snt[1]=0;dem=0; 
 for (int i = 2; i < N; i++) 
 { if (snt[i] == 1) //Nếu i là nguyên tố 
 { 
 dem++; 
 // Đánh dấu các bội của i không phải nguyên tố. 
 for (int j = 2 * i; j < N; j += i) snt[j]=0; 
 } 
 }} 
 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. Đọc giá trị N từ tệp; 
 Bước 2. Khởi tạo các phần tử của mảng đánh dấu snt đều bằng 1; 
 Bước 3. snt[1] ← 0; dem ← 0; 
 Bước 4. i ← 2; 
 Bước 5. Nếu i ≥ N thì chuyển đến bước 8; 
 Bước 6. Nếu snt[i] = 1 thì làm: 
 6 
 a. Ý tưởng thuật toán: 
 Với bài này ta sẽ sử dụng mảng đếm: 
 - Tạo mảng t với mục đích: t[i] sẽ lưu số lần xuất hiện củaphần tử có giá trị là i. 
 - Khởi tạo các phần tử của mảng t bằng 0. 
 - Đọc các số trong dãy a: đọc đến phần tử a[i] nào thì ta tăng t[a[i]] lên 1 đơn 
vị. Giá trị của a[i] sẽ được xem là một chỉ số trong dãy t.
 Lưu ý: Với kỹ thuật mảng đếm này chỉ áp dụng được khi a[i] có thể làm chỉ 
số của dãy t. 
 Đoạn lệnh chương trình con sau thể hiện mảng đếm t: 
 int t[32001], a[1001]; 
 void doctep() 
 { ifstream fi(“lophoc.inp”); 
 memset(t, 0, sizeof(t)); 
 fi>>N; 
 for(int i=1; i<=N; i++) 
 { fi>>a[i]; 
 t[a[i]]++; 
 }} 
 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. Đọc giá trị N từ tệp; 
 Bước 2. Khởi tạo các phần tử của mảng t bằng 0 
 Bước 3. Max ← 0; 
 Bước 4. Cho i lần lượt nhận các giá trị từ 1 đến N, thực hiện lặp lại: 
 Bước 4.1. Đọc phần tử a[i] từ tệp; 
 Bước 4.2. t[a[i]]← t[a[i]] + 1; 
 Bước 4.3. Nếu Max < a[i] thì Max ← a[i]; 
 Bước 5. Cho i lần lượt nhận các giá trị từ 1 đến Max, thực hiện lặp lại: 
 Bước 5.1. Nếu t[i] > 0 thì ghi giá trịa [i] và t[a[i]] ra tệp trên mỗi dòng; 
 Bước 6. Kết thúc thuật toán. 
 - Cài đặt chương trình: Phần phụ lục 1 (tanso.cpp) 
 8 
 for (int i=1; i<=M; i++) 
 { fi>>x; 
 b[x]++; 
 } 
 fi.close(); 
 } 
 b. Nội dung và cài đặt chương trình 
 - Các bước thực hiện của giải thuật: 
 Bước 1. Đọc giá trị N, M từ tệp; 
 Bước 2. Khởi tạo các phần tử của mảng a và b đều bằng 0;
 Bước 3. Thực hiện lặp lại N lần thao tác sau: 
 Bước 3.1. Đọc giá trị x từ tệp; 
 Bước 3.2. a[x] ← a[x] + 1; 
 Bước 4. Thực hiện lặp lại M lần thao tác sau: 
 Bước 4.1. Đọc giá trị x từ tệp; 
 Bước 4.2. b[x]← b[x] + 1; 
 Bước 5. dem ← 0; 
 Bước 6. Cho i lần lượt nhận các giá trị từ 0 đến 105, thực hiện lặp lại: 
 Bước 6.1. dem ← dem + a[i]*b[i]; 
 Bước 7. Ghi giá trị dem ra tệp rồi kết thúc thuật toán. 
 - Cài đặt chương trình: Phần phụ lục 1 (lophoc.cpp) 
 2.3.2.3. Bài toán 3 – Sắp xếp đếm phân phối 
 9
 Cho n số nguyên dương được lưu trữ trong tệp Sort.inp (ai ≤ 5000, n ≤ 10 ). 
Hãy lập trình sắp xếp dãy số này và ghi kết quả vào tệp Sort.out. 
 Ví dụ: 
 Sort.inp Sort.out 
 14 1 1 2 2 2 3 3 3 3 3 4 4 5 6 
 1 1 3 2 3 3 2 5 4 6 4 2 3 3 
 a. Ý tưởng thuật toán: 
 Đọc qua một lượt từ phần tử a[1] đến a[n] và dùng mảng b đếm số lần xuất 
hiện của mỗi phần tử. Phần tử b[i] dùng để lưu số lần xuất hiện của số i trong dãy 
a. 
 10