Đề xuất một số bài tập vận dụng phương pháp Quy hoạch động để nâng cao chất lượng bồi dưỡng học sinh giỏi Tin học cấp trung học phổ thông

Nội dung tài liệu: Đề xuất một số bài tập vận dụng phương pháp Quy hoạch động để nâng cao chất lượng bồi dưỡng học sinh giỏi Tin học cấp trung học phổ thông

1. CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc ĐƠN YÊU CẦU CÔNG NHẬN SÁNG KIẾN Kính gửi: Sở Khoa học và Công nghệ (Cơ quan thường trực Hội đồng Sáng kiến tỉnh Bắc Giang) Thông tin cá nhân Ngày tháng Chức Trình độ Họ và tên Nơi công tác năm sinh danh chuyên môn Trường THPT Giáo Ninh Thị Thu Hà 06/06/1981 Thạc sĩ Yên Thế viên Là tác giả đề nghị xét công nhận sáng kiến: 1. Tên sáng kiến: Đề xuất một số bài tập vận dụng phương pháp Quy hoạch động để nâng cao chất lượng bồi dưỡng học sinh giỏi Tin học cấp THPT Họ và tên: Ninh Thị Thu Hà Điện thoại: 0982984057 Email: nttha.yt@bacgiang.edu.vn 2. Chủ đầu tư tạo ra sáng kiến: Không có. 3. Lĩnh vực áp dụng sáng kiến: GD&ĐT – áp dụng giảng dạy môn Tin học 4. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: 4/2020. 5. Các tài liệu kèm theo sáng kiến kinh nghiệm. 5.1. Thuyết minh mô tả giải pháp và kết quả thực hiện sáng kiến. 5.2. Quyết định công nhận sáng kiến cơ sở: Quyết định số 351 /QĐ-HĐKH&CN ngày 03/6/2021 của Hội đồng KH&CN về việc công nhận sáng kiến cơ sở ngành giáo dục năm học 2020-2021. 5.3. Biên bản họp Hội đồng sáng kiến cơ sở. 5.4. Phiếu chấm điểm sáng kiến được áp dụng có hiệu quả phạm vi ảnh hưởng cấp tỉnh của thành viên Hội đồng KH&CN, Sở GD&ĐT. Bắc Giang, ngày 07 tháng 6 năm 2021 ĐẠI DIỆN TÁC GIẢ SÁNG KIẾN Ninh Thị Thu Hà
2. 2 THUYẾT MINH MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN 1. Tên sáng kiến: Đề xuất một số bài tập vận dụng phương pháp Quy hoạch động để nâng cao chất lượng bồi dưỡng học sinh giỏi Tin học cấp trung học phổ thông. 2. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: Tháng 4/2020 3. Các thông tin cần được bảo mật: không 4. Mô tả các giải pháp cũ thường làm : Trước đây, khi lập trình giải một bài toán, học sinh thường lựa chọn ngay cách giải dễ cài đặt (sử dụng phương pháp duyệt, đệ quy, ) và tập trung vào việc đưa ra đáp số đúng mà chưa quan tâm đến việc đưa ra đáp số đúng trong thời gian ngắn nhất. Phương pháp duyệt, đệ quy, đảm bảo được việc tìm ra nghiệm đúng, chính xác nhưng nhược điểm thời gian thực thi lâu, độ phức tạp lớn. Do đó phương pháp này thường chỉ phù hợp với các bài toán có kích thước nhỏ. Với yêu cầu ngày càng cao của những bài toán thi học sinh giỏi: đòi hỏi một thuật toán thỏa mãn được giới hạn dung lượng, giới hạn thời gian thực hiện thì phương pháp duyệt, đệ quy không đáp ứng được. 5. Sự cần thiết phải áp dụng giải pháp sáng kiến: Qua nhiều năm bồi dưỡng học sinh giỏi tin học cấp trung học phổ thông, tôi luôn tìm hiểu nhiều tài liệu, tìm các dạng bài tập để hướng dẫn cho học sinh. Tuy nhiên với những bài liên quan đến phương pháp quy hoạch động thường là học sinh bỏ qua (giải bài toán bằng cách khác) hoặc chỉ thuộc công thức của một bài và chỉ làm được một bài đó. Từ thực tế đó, tôi nhận thấy cần có các bài tập tương tự cùng một dạng để học sinh vừa làm quen với mỗi dạng bài toán quy hoạch động đó, vừa rèn kỹ năng giải toán bằng quy hoạch động. Sau thời gian tìm hiểu, áp dụng, tôi nhận thấy các bài tập tôi đề xuất (áp dụng phương pháp quy hoạch động ) đã giúp học sinh không còn lạ lẫm với phương pháp quy hoạch động, đồng thời làm quen, nhận diện được một số bài tập tương tự bài toán quy hoạch động điển hình, từ đó giải được trọn vẹn bài toán đó. Cấu trúc đề thi học sinh giỏi một vài năm gần đây thể hiện rõ ràng sự phân hóa bằng việc: - Bài thi được chấm bằng các test, có so sánh thời gian chạy chương trình của các thí sinh để đánh giá. Các test của mỗi câu được chỉ rõ về số lượng, giới hạn dữ liệu, số điểm tương ứng đạt được. - Các bài toán trong đề có tỉ lệ % theo yêu cầu mức độ mục tiêu của đề. Trong đó có một bài (chiếm tỉ lệ 10-15%) yêu cầu mức độ vận dụng cao,
3. 3 phải tổ chức dữ liệu hợp lý để đảm bảo thời gian chạy chương trình và có sử dụng một số thuật toán thường là thuật toán quy hoạch động. Để đạt được điểm cao, học sinh không những phải giải hết các bài toán mà với mỗi bài toán học sinh còn cần lựa chọn được thuật toán sao cho đáp ứng hết các bộ test trong bài. Việc làm quen với phương pháp quy hoạch động qua một số bài tập ví dụ tạo cơ hội cho học sinh khám phá, tìm tòi sâu hơn về phương pháp này, cũng là cơ hội để khơi nguồn cho học sinh phấn đấu đạt giải cao trong kỳ thi học sinh giỏi cấp tỉnh. 6. Mục đích của giải pháp sáng kiến Xây dựng hệ thống bài tập quy hoạch động điển hình, giúp làm tài liệu tham khảo cho giáo viên, giúp giáo viên có cái nhìn tổng quan về các dạng bài tập quy hoạch động điển hình; đồng thời sử dụng để bồi dưỡng học sinh giỏi giúp học sinh hiểu rõ có nhiều dạng bài quy hoạch động, trong đó có một số bài quy hoạch động điển, và sử dụng phương pháp quy hoạch động giúp tối ưu lời giải bài toán. Cung cấp một bộ tài liệu chuẩn cho học sinh tự học, giúp học sinh củng cố, ghi nhớ công thức, rèn kỹ năng giải toán bằng phương pháp quy hoạch động cho học sinh. Cung cấp cho giáo viên có một tài liệu logic, súc tích về các bài tập quy hoạch động điển hình và các bài tập tương tự thuận lợi cho việc giảng dạy, ôn thi học sinh giỏi các cấp. 7. Nội dung 7.1. Thuyết minh giải pháp mới hoặc cải tiến Trong SKKN tôi đưa ra hai giải pháp, trong đó giải pháp 1 là giải pháp cải tiến và giải pháp 2 là giải pháp mới. * Giải pháp 1: Tín hiệu để nhận diện các dạng bài tập quy hoạch động cơ bản. Giải pháp 1 là giải pháp mới: các tài liệu trước đây cũng đưa ra các dạng quy hoạch động điển hình và công thức quy hoạch động giải các bài đó, tuy nhiên dấu hiệu để nhận đúng bài toán đưa ra áp dụng công thức nào để giải là vấn đề khó khăn cho học sinh. Là giáo viên dạy đội tuyển học sinh giỏi nhiều năm, tôi nhận thấy thực tế học sinh rất khó hiểu công thức quy hoạch động. Học sinh thường học thuộc lòng công thức như một cái máy hoặc công nhận công thức quy hoạch động bằng cách mô phỏng thuật toán với bộ dữ liệu cụ thể trên bảng phương án. Đôi khi học sinh còn nhầm công thức quy hoạch động giữa bài toán này và bài toán khác. Trên cơ sở dạy học và thực tế học sinh nhầm lẫn và không nhận diện được các dạng bài quy hoạch động điển hình, tôi đã hệ thống
4. 4 lại 3 dạng bài quy hoạch động cơ bản và phân tích, chỉ ra dấu hiệu nhận diện 3 dạng bài, cụ thể: Dạng 1: bài dãy con tăng nhiều phần tử nhất. Đặc điểm nhận diện: - Dựa vào tính chất dãy con tăng: Phần tử đứng trước nhỏ hơn phần tử đứng sau - Khi cập nhật L(i) chỉ phụ thuộc vào các phần tử L(j) (j=1..i-1) đứng trước nó. (Li phụ thuộc vào L1,L2, ,Li-1) Ví dụ: * Bài toán: Cho dãy a có n phần tử a1,a2, an. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy. * Đặc điểm nhận diện và công thức quy hoạch động Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a1 đến ai và phần tử cuối cùng là ai. Khi đó L(i) được cập nhập từ các L(j) với j nhận các giá trị từ 1 đến i-1. Vậy công thức quy hoạch động tính L(i) chỉ có thể xây dựng từ L(1), L(2), L(i-1), hay nói cách khác công thức tính L(i) chỉ phụ thuộc vào phần tử đứng trước. Ta có công thức QHĐ để tính L(i) như sau: L(1) = 1 L(i) = max(1, L(j)+1 với mọi phần tử j: 0 < j < i và aj ≤ ai). Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ L(i). Đoạn chương trình tính các giá trị của mảng L như sau: for i := 1 to n do begin L[i] := 1; for j:=1 to i - 1 do if (a[j]<=a[i]) and (L[i]<L[j]) then L[i]:=L[j]+1; end; Dạng 2: bài cái túi (mỗi lần chọn 1 vật). Đặc điểm nhận diện: Mỗi lần cập nhật L(i,t), tùy việc chọn đồ vật vào túi hay không chọn vào túi, chỉ phụ thuộc vào 2 phần tử ngay trước nó L(i-1,t) và L(i-1,t-ai) Ví dụ: * Bài toán: Có n đồ vật, vật thứ i có trọng lượng ai và giá trị bi. Hãy chọn ra một số các đồ vật, mỗi vật một cái để xếp vào 1 cái túi (vali/ ba lô) có trọng lượng tối đa M sao cho tổng giá trị của cái túi là lớn nhất. * Đặc điểm nhận diện và công thức quy hoạch động: Gọi L(i,t) là tổng giá trị lớn nhất khi được chọn i vật từ vật 1 đến vật i cho vào cái túi với tổng khối lượng không vượt quá t. L(n,M) sẽ là đáp số của bài toán (là giá trị lớn nhất có được nếu chọn n vật và tổng khối lượng không vượt M).
5. 5 Tổng giá trị các đồ vật được lựa chọn phụ thuộc vào hai đại lượng: sức chứa của cái túi và trọng lượng các đồ vật. Do đó bảng phương án là mảng hai chiều L(i,t): tổng giá trị lớn nhất của cái túi khi xét từ vật 1 đến vật i với sức chứa tối đa là t (đồ vật i có thể được chọn hay không được chọn). Giải bài toán con cỡ (i,t) phụ thuộc vào tất cả các bài toán con kích thước i1, t1 mà i1 : 1..i-1 và t1 :1..t-1, do đó số lượng bài toán con rất nhiều. Thực ra không phải phụ thuộc vào tất cả các bài toán con trước nó, L(i,t) chỉ phụ thuộc vào hai yếu tố, nếu không lựa chọn đồ vật thứ i vào túi thì chỉ phụ thuộc vào giá trị bài toán con ngay trước nó L(i,t)=L(i-1,t), nếu chọn đồ vật i vào túi thì sức chứa cái túi giảm đi ai và giá trị cái túi tăng lên bi, tức là L(i,t)=L(i-1, t-ai)+bi Tính L(i,t): Vật đang xét là ai với trọng lượng của cái túi không được quá t. Có hai khả năng xảy ra: - Nếu vật ai có trọng lượng lớn hơn trọng lượng cái túi (t<ai) thì L(i,t)=L(i-1,t) - Nếu vật ai có trọng lượng nhỏ hơn trọng lượng cái túi t (t>=ai): Nếu chọn ai đưa vào cái túi thì cái túi đã bị chiếm mất trọng lượng ai, sức chứa túi còn lại là t-ai, vậy trọng lượng cái túi trước đó phải không quá t-ai. Vì mỗi vật chỉ được chọn 1 lần nên giá trị lớn nhất của cái túi lúc đó là L(i-1, t-ai) + bi. Nếu không chọn ai, thì trọng lượng của cái túi như cũ (như lúc trước khi chọn ai) là L(i-1,t). Công thức tính L(i,t) như sau: L(i,0)=0; L(0,t)=0. L(i,t)=L(i–1,t) nếu t < ai. L(i,t)=max(L(i–1,t), L(i–1,t–ai)+bi) nếu t ≥ ai. Trong đó: L(i–1,t) là giá trị có được nếu không đưa vật i vào balô, L(i–1,t–ai)+bi là giá trị có được nếu chọn vật i. Cài đặt: For i:=1 to n do For t:=1 to M do If b[i]<=t then L[i,t]:=max(L[i-1,t-a[i]]+b[i], L[i-1,t]) Else L[i,t]:=L[i-1,t]; Dạng 3: bài di chuyển. Đặc điểm nhận diện: trả lời được câu hỏi: Từ ô nào đến được ô (i,j)? Ví dụ: *Bài toán: Cho bảng A kích thước MxN (M dòng, N cột) trên đó ghi các số nguyên. Một người xuất phát tại ô nào đó của cột 1 cần sang cột n. Quy tắc: Từ ô A(i,j) có thể di chuyển sang 3 ô A(i-1,j+1), A(i,j+1) và A(i+1,j+1). Hãy
6. 6 tìm vị trí ô xuất phát và hành trình đi từ cột 1 đến cột n sao cho tổng các số ghi trên đường đi qua là lớn nhất (nhỏ nhất). * Đặc điểm nhận diện và công thức quy hoạch động: Tìm câu trả lời cho câu hỏi: Từ ô nào đến được ô (i,j)? Bước 1: Vẽ hình (2 bảng kích cỡ mxn của đề bài: 1 bảng đường đi ban đầu A , 1 bảng sẽ là bảng phương án F) Bước 2: Thiết lập tham chiếu sang các ô xung quanh: từ 1 ô ban đầu có thể sang những ô kề cạnh hay kề đỉnh nào (đề bài cho), Bước 3: Lần ngược lại tìm công thức quy hoạch động: để tới được ô (i,j) thì đi qua những ô nào Gọi F[i, j] là số điểm lớn nhất (nhỏ nhất) có thể có được khi tới ô A[i, j]. Rõ ràng đối với những ô ở cột 1 thì F[i, 1] = A[i, 1]. Với những ô (i, j) ở các cột khác: Vì chỉ những ô (i, j – 1), (i – 1, j – 1), (i + 1, j –1) là có thể sang được ô (i, j), và khi sang ô (i, j) thì số điểm được cộng thêm A[i, j] nữa. Chúng ta cần F[i, j] là số điểm lớn nhất (nhỏ nhất) có thể nên F[i, j] = max(F[i, j - 1], F[i –1, j - 1], F[i + 1, j - 1]) + A[i, j] (Hoặc min). Ta dùng công thức truy hồi này tính tất cả các F[i, j]. Cuối cùng chọn ra F[i, n] là phần tử lớn nhất trên cột n của bảng F và từ đó truy vết tìm ra đường đi nhiều điểm nhất A F (1,1) (1,1) A(i-1,j+1) F(i-1,j-1) A(i,j) A(i,j+1) F(i,j-1) F(i,j) A(i+1,j+1) F(i+1,j-1) (m,n) (m,n) Chi tiết tín hiệu nhận diện 3 dạng bài trên được trình bày ở phụ lục 1, dưới đây là bảng đặc điểm nhận dạng mỗi dạng bài trong 3 dạng mà giải pháp 1 đề cập đến: Bảng 1. Tín hiệu nhận diện 3 dạng bài quy hoạch động cơ bản Dạng bài Đặc điểm nhận dạng Dạng 1: Bài toán dãy con - Dựa vào tính chất dãy con tăng: Phần tử đứng tăng có nhiều phần tử nhất trước nhỏ hơn phần tử đứng sau. - Khi cập nhật L(i) chỉ phụ thuộc vào các phần tử L(j) (j=1..i-1) đứng trước nó. (Li phụ thuộc vào L1, L2, , Li-1) Dạng 2: Bài toán cái túi (mỗi Mỗi lần cập nhật L(i,j), tùy việc chọn đồ vật vào
7. 7 vật chọn 1 lần) túi hay không chọn vào túi, chỉ phụ thuộc vào 2 phần tử ngay trước nó L(i-1,j) và L(i-1,j-ai) Dạng 3: Bài toán di chuyển Trả lời được câu hỏi: Từ ô nào đến được ô (i,j)? Cách tìm tín hiệu nhận dạng: -Bước 1: Vẽ hình (2 bảng kích cỡ mxn của đề bài: 1 bảng đường đi ban đầu A , 1 bảng sẽ là bảng phương án F) -Bước 2: Thiết lập tham chiếu sang các ô xung quanh: từ 1 ô ban đầu có thể sang những ô kề cạnh hay kề đỉnh nào (đề bài cho), -Bước 3: Lần ngược lại tìm công thức quy hoạch động: để tới được ô (i,j) thì đi qua những ô nào. * Giải pháp 2: - Tên giải pháp: Lựa chọn các bài tập tương tự bài toán quy hoạch động điển hình và áp dụng vào giảng dạy để củng cố, rèn luyện kỹ năng giải bài toán bằng phương pháp quy hoạch động cho học sinh. Giải pháp 2 là giải pháp cải tiến. Các tài liệu trước đây chỉ đưa ra dạng bài quy hoạch động điển hình và công thức quy hoạch động của dạng bài đó chứ mỗi bài toán tương tự cùng loại không được phân tích đặc điểm nhận diện, chỉ ra tại sao cùng loại dạng bài đó. Để ghi nhớ công thức của một dạng bài mà chỉ làm một bài thì nhàm chán và khó nhớ. Do đó cần hệ thống bài tập tương tự là biến thể của dạng bài đó (các bài tập cùng đặc điểm nhận diện ở giải pháp 1 đưa ra) để giúp học sinh phân tích bài toán để tìm ra điểm chung điểm riêng, rèn luyện kỹ năng làm bài, từ đó giúp học sinh củng cố và ghi nhớ công thức dễ dàng hơn. Trên cơ sở giải pháp 1 đã đưa ra đặc điểm nhận diện 3 dạng bài quy hoạch động điển hình, giải pháp 2 xây dựng hệ thống bài tập tương tự cho dạng bài dãy con đơn điệu tăng (7 bài), bài toán cái túi (7 bài), dạng bài toán di chuyển (9 bài). Mỗi bài tập tương tự được phân tích, chi tiết bảng phương án, đoạn code cài đặt bảng phương án. Hệ thống bài tập tương tự cùng dạng được áp dụng giảng dạy bồi dưỡng học sinh giỏi để củng cố, rèn kỹ năng giải bài toán bằng phương pháp quy hoạch động cho học sinh nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi. Dạng 1: Bài toán dãy con tăng nhiều phần tử nhất. Dạng 1 gồm 7 bài, với mỗi một bài toán tương tự được trình bày gồm: đề bài, tín hiệu nhận diện và công thức quy hoạch động, chi tiết bảng phương án,
8. 8 đoạn chương trình chính. Dưới đây là một bài toán tương tự, chi tiết 6 bài còn lại ở phụ lục 1. Bài 1. Dãy con không giảm dài nhất Cho dãy số nguyên a= a1, a2, , an. (n<=5000, -10000<=ai<=10000). Một dãy con không giảm của dãy đã cho là dãy các phần tử còn lại của dãy đó sau khi ta xóa bỏ một hoặc một số phần tử bất kì của nó, các phần tử của dãy con tạo thành dãy không giảm. Ví dụ: dãy 1, 2, 10, 11, 12 là một dãy con không giảm của dãy 1, 4, 2, 10, 9, 8, 17, 11, 7, 12. Yêu cầu: Tìm dãy con không giảm của dãy a gồm nhiều phần tử nhất. Dữ liệu: đọc từ file văn bản DAYCON.INP gồm: + Dòng 1: ghi số N là số lượng phần tử của dãy + Các dòng tiếp theo: ghi N số a1, a2, , an. các số cách nhau ít nhất một dấu cách Kết quả: ghi ra file văn bản DAYCON.OUT gồm 2 dòng: + Dòng 1: ghi độ dài dãy con tìm được + Các dòng tiếp theo: ghi giá trị các phần tử được chọn vào dãy con từ dãy ban đầu. Ví dụ: DAYCON.INP DAYCON.OUT 11 8 1 2 3 8 9 4 5 6 20 9 10 1 2 3 4 5 6 9 10 Đặc điểm nhận diện và công thức quy hoạch động - Đặc điểm nhận diện: Tính chất của dãy con không giảm là phần tử đứng trước không lớn hơn phần tử đứng sau. Nên khi xét đến phần tử ai, ta cần tìm phần tử aj (j<i) nào đó thỏa mãn tính chất của dãy con không giảm. Giá trị tối ưu cần tìm là max về độ dài - Công thức quy hoạch động: Gọi L[i] là độ dài dãy con không giảm dài nhất các phần tử xét từ a[1..i] và phần tử cuối cùng phải là a[i]. Vậy yêu cầu của bài toán ban đầu: max(L[i]) L[1]: là độ dài dãy con không giảm dài nhất các phần tử xét từ a[1..1] và phần tử cuối cùng phải là a[1]. Vậy: L[1] = 1 Tính L[i]: L[i] = max(1, L[j] + 1), với điều kiện: j < i, a[j] <= a[i] - Bảng phương án:
9. 9 Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ L[i]. Để dễ dàng truy vết tạo mảng T[i] là vị trí của phần tử trước a[i], ta thêm vào dãy phần tử a[0] và a[n+1] để đảm bảo dãy luôn tăng. Khi đó khởi tạo L[0]=1 (dãy xuất phát từ phần tử a[0] có 1 phần tử) i 0 1 2 3 4 5 6 7 8 9 10 11 N+1 a -oo 1 2 3 8 9 4 5 6 20 9 10 +oo L 1 2 3 4 5 6 5 6 7 8 8 9 10 T 0 1 2 3 4 3 6 7 8 8 10 11 Đoạn chương trình tính các giá trị của mảng L (bảng phương án): L[0]=1; for(i=1;i<=n+1;i++) { jmax=0; for(j=0;j<i;j++) if(a[j] L[jmax]) jmax=j; L[i]=L[jmax]+1; T[i]=jmax; } Dạng 2: Bài toán cái túi Dạng 2 gồm 7 bài, với mỗi một bài toán tương tự được trình bày gồm: đề bài, tín hiệu nhận diện và công thức quy hoạch động, chi tiết bảng phương án, đoạn chương trình chính. Dưới đây là một bài toán tương tự, chi tiết 6 bài còn lại ở phụ lục 1. Bài 1. Ba lô –BALOB Có một ba lô có thể chứa tối đa trọng lượng M và có n đồ vật (n 100), đồ vật thứ i có trọng lượng và giá trị ; M, , là các số nguyên dương. Hãy chọn và xếp các đồ vật vào ba lô để tổng giá trị của ba lô là lớn nhất. * Input: đọc từ file văn bản BALOB.INP gồm: + Dòng 1: ghi 2 số n, M (0<M<=200) cách nhau ít nhất một dấu cách. + n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương , (0< , < 256) cách nhau ít nhất một dấu cách *Output:ghi ra file văn bản BALOB.OUT gồm: + Dòng 1: ghi giá trị lớn nhất có thể xếp vào Ba lô + Dòng 2: ghi chỉ số những vật được xếp vào Ba lô *Example: BALOB.INP BALOB.OUT 5 11 11 3 3 5 2 1
10. 10 4 4 5 4 9 10 4 4 Đặc điểm nhận diện và công thức quy hoạch động - Đặc điểm nhận diện: Tại thời điểm i, việc chọn hay không chọn ai vào túi phụ thuộc vào thời điểm i-1 ngay trước nó có tạo ra được tổng t hay tổng t-ai hay không - Công thức quy hoạch động: Gọi L(i,t) là tổng giá trị lớn nhất khi được chọn i vật từ 1 đến i cho vào ba lô với tổng khối lượng không vượt quá t. L(n,m) sẽ là đáp số của bài toán (là giá trị lớn nhất có được nếu chọn n vật và tổng khối lượng không vượt m). Công thức tính L(i,t) như sau: L(i,0)=0; L(0,t)=0. L(i,t)=L(i–1,t) nếu t<Wi. L(i,t)=max(L(i–1,t), L(i–1,t–wi)+vi) nếu t ≥ wi. Trong đó: L(i–1,t) là giá trị có được nếu không đưa vật i vào balô, L(i–1,t–wi)+vi là giá trị có được nếu chọn vật i. Điền giá trị vào bảng phương án L(i,t) t 0 1 2 3 4 5 6 7 8 9 10 11 Wi Vi i 0 0 0 0 0 0 0 0 0 0 0 0 3 3 1 0 0 0 3 3 3 3 3 3 3 3 3 4 4 2 0 0 0 3 4 4 4 7 7 7 7 7 5 4 3 0 0 0 3 4 4 4 7 7 7 7 7 9 10 4 0 0 0 3 4 4 4 7 7 10 10 10 4 4 5 0 0 0 3 4 4 4 7 8 10 10 10 Đoạn chương trình tính các giá trị của mảng L (bảng phương án): void QHD() { int i,j; F[0][0]=0; for(i=1; i<=n; i++) for(j=0; j<=M; j++) { F[i][j]=F[i-1][j]; if((W[i]<=j)&&(F[i][j]<F[i-1][j-W[i]]+V[i])) F[i][j]=F[i-1][j-W[i]]+V[i]; } }
11. 11 Dạng 3: Bài toán di chuyển Với dạng bài di chuyển, tín hiệu nhận dạng là trả lời được câu hỏi: Từ ô nào đến được ô (i,j)?, gồm 9 bài toán tương tự cùng đặc điểm nhận dạng. Với mỗi một bài toán tương tự được trình bày gồm: đề bài, tín hiệu nhận diện và công thức quy hoạch động, chi tiết bảng phương án, đoạn chương trình chính. Sau đây là một bài toán tương tự, chi tiết 8 bài còn lại ở phụ lục 1. Bài 1. Con kiến (FOOD2.*) Trên một sân hình chữ nhật MxN ô (M dòng, N cột), được chia thành các ô vuông đơn vị, mỗi ô chứa một lượng thức ăn. Một con kiến xuất phát từ cột 1 muốn đi qua sân để đến cột thứ N. Con kiến chỉ có thể đi từ ô (i,j) sang 3 ô (i-1, j+1), (i, j+1) và (i+1, j+1) nhưng kiến không thể bò ra khỏi sân. Hãy chỉ ra đường đi giúp con kiến có được nhiều thức ăn nhất. * Input: đọc từ file văn bản FOOD2.INP có cấu trúc: - Dòng 1: ghi 2 số nguyên dương M, N (1 M, N 1000). - M dòng tiếp theo, mỗi dòng có N số tương ứng là lượng thức ăn có trong MxN ô trên sân. * Output: ghi ra file văn bản FOOD2.OUT một số duy nhất là tổng lượng thức ăn nhiều nhất mà con kiến có thể ăn được. * Example FOOD2.INP FOOD2.OUT Giải thích 5 4 2 5 6 2 7 8 1 6 Đường 1: (3,1) -> (2,2) -> (3,3) -> (3,4) 33 9 1 7 9 Đường 2: (3,1) -> (4,2) -> (4,3) -> (3,4) 6 7 1 3 1 4 2 Đặc điểm nhận diện và công thức quy hoạch động - Đặc điểm nhận diện: Từ 1 ô ban đầu (i,j) có thể sang 3 ô kề bên phải nó cùng dòng hoặc trên, dưới 1 dòng: (i-1,j+1), (i,j+1) và (i+1,j+1). Như vậy có thể lần ngược lại tìm công thức quy hoạch động: để tới được ô (i,j) thì phải đi qua các ô (i, j – 1), (i-1, j – 1), (i + 1, j –1). Vậy để tới được ô (i,j) thì phải đi qua các ô (i, j-1), (i-1, j-1), (i + 1, j –1) - Xây dựng công thức quy hoạch động:
12. 12 Gọi F[i, j] là số điểm lớn nhất có thể có được khi tới ô A[i, j]. Rõ ràng đối với những ô ở cột 1 thì F[i, 1] = A[i, 1]. Với những ô (i, j) ở các cột khác: Vì chỉ những ô (i, j – 1), (i – 1, j – 1), (i + 1, j –1) là có thể sang được ô (i, j), và khi sang ô (i, j) thì số điểm được cộng thêm A[i, j] nữa. Chúng ta cần F[i, j] là số điểm lớn nhất (nhỏ nhất) có thể nên F[i, j] = max(F[i, j - 1], F[i –1, j - 1], F[i + 1, j - 1]) + A[i, j] Ta dùng công thức truy hồi này tính tất cả các F[i, j]. Cuối cùng chọn ra F[i, n] là phần tử lớn nhất trên cột n của bảng F và từ đó truy vết tìm ra đường đi nhiều điểm nhất - Đoạn chương trình: void QHD() { for(int i=1;i<=M;i++)F[i][1]=A[i][1]; for(int j=2;j<=N;j++) for(int i=1;i<=M;i++) F[i][j]=max(max(F[i-1][j-1],F[i][j-1]),F[i+1][j-1])+A[i][j]; } 7.2. Thuyết minh về phạm vi áp dụng sáng kiến: Sáng kiến được áp dụng dạy học sinh lớp 11 tham gia các kì thi chọn học sinh giỏi các cấp (cấp huyện và đặc biệt cấp tỉnh). Sáng kiến được áp dụng giảng dạy tại trường THPT Yên Thế và tại 02 trường THPT khác trên địa bàn tỉnh Bắc Giang1. 7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến: -Về lợi ích kinh tế: Tiết kiệm thời gian, công sức của giáo viên khi dạy chuyên đề quy hoạch động trong bồi dưỡng học sinh giỏi. Giải pháp trong sáng kiến kinh nghiệm có thể tiếp tục xây dựng mở rộng các dạng bài tương tự của các bài quy hoạch động cơ bản để thành tư liệu tham khảo cho giáo viên, tự nghiên cứu, xây dựng của những năm học sau. Qua đó tiết kiệm được các chi phí khác như: chi phí đi lại, mua tài liệu tham khảo, - Về lợi ích xã hội: Sáng kiến sau khi được triển khai và áp dụng đã trao quyền chủ động cho học sinh trong mọi hoạt động học tập, kích thích được hứng thú học tập và sáng tạo 1 Các trường THPT: Bố Hạ, Việt Yên số 1
13. 13 của học sinh, làm cho học sinh tự tin vào khả năng của mình đồng thời giải quyết được những khúc mắc của học sinh trong quá trình đánh giá kết quả môn học; từ đó học sinh đạt kết quả cao trong kì thi học sinh giỏi. Để đánh giá lợi ích xã hội tôi đã tiến hành đánh giá việc áp dụng sáng kiến kinh nghiệm dạy đối tượng học sinh khá, giỏi ở khối 11 của trường THPT Yên Thế và hai trường khác trong tỉnh là THPT Bố Hạ, THPT Việt Yên 1. Cụ thể: *Triển khai thực hiện sáng kiến lần 1 (tháng 4/2020) tại trường THPT Yên Thế và THPT Bố Hạ: Giáo viên tham gia thực hiện sáng kiến của trường THPT Yên Thế: Ninh Thị Thu Hà; trường THPT Bố Hạ: Thạch Thị Thương. Đối tượng học sinh là học sinh khá, giỏi, có tư duy ngang nhau (dựa vào kết quả trung bình các môn tự nhiên, điểm trung bình môn Tin). Vì số lượng học sinh đi thi học sinh giỏi môn Tin chỉ được tối đa 2 em, nên mỗi trường chúng tôi chỉ chọn 8 học sinh2 tham gia đánh giá. Chúng tôi sử dụng phương pháp cũ để thực hiện bài kiểm tra3 lần 1: đưa đề bài (bài toán thuộc dạng 1) và cho học sinh tự làm. Sau khi chấm bài của học sinh nhận thấy kết quả rất thấp (chi tiết ở phụ lục 2) do đó chúng tôi buộc phải thay đổi phương pháp dạy bằng cách áp dụng sáng kiến: Chúng tôi bồi dưỡng sáng kiến cho 5 học sinh4 trong số 8 học sinh đã tham gia đánh giá lần 1 của mỗi trường trong thời gian từ 2 đến 3 tuần. Sau đó thực hiện bài kiểm tra số 2 (đề bài là 1 bài toán tương tự thuộc dạng 1). Tham gia làm bài kiểm tra 2 gồm 8 học sinh của mỗi trường, trong đó có 5 học sinh đã được bồi dưỡng sáng kiến. Sau khi chấm bài kiểm tra số 2 nhận thấy kết quả bài làm của các bạn được bồi dưỡng sáng kiến cao hơn hẳn (chi tiết phụ lục 2) Dưới đây là kết quả chấm bài kiểm tra 1 và bài kiểm tra số 2 bằng phần mềm chấm điểm tự động Themis khi thực hiện sáng kiến lần 1: 2 Danh sách học sinh các trường tham gia đánh giá ở phụ lục 2 3 Bài kiểm tra 1,2 thực hiện sáng kiến lần 1: chi tiết ở phụ lục 2 4 Danh sách học sinh tham gia bồi dưỡng sáng kiến ở phụ lục 2
14. 14 Trường THPT Yên Thế: Kết quả bài kiểm tra lần 1 Kết quả bài kiểm tra lần 2 Trường THPT Bố Hạ Kết quả bài kiểm tra lần 1 Kết quả bài kiểm tra lần 2
15. 15 Biểu đồ 1: So sánh kết quả bài kiểm tra số 1 và bài kiểm tra số 2 - thực hiện sáng kiến lần 1 (tháng 4/2020) Chú giải: Điểm bài KT số 1 Điểm bài KT số 2 Nhìn vào biểu đồ 1 nhận thấy: Bài kiểm tra số 1: chủ yếu là thang điểm từ 4 đến 6, không có học sinh nào đạt trên 6 điểm. Bài kiểm tra 2: khoảng 50% điểm từ 7 trở lên, (hầu hết là học sinh được bồi dưỡng sáng kiến), 30% điểm từ 5 trở xuống thì chủ yếu là học sinh không được bồi dưỡng sáng kiến (tên học sinh có chữ K). Trong kỳ thi học sinh giỏi văn hóa cấp tỉnh năm học 2019-2020, cả 4 bạn tham gia bồi dưỡng sáng kiến đi thi học sinh giỏi đạt cả 4 giải: 1 Nhất, 1 Nhì, 1 Ba, 1 Khuyến khích. Hiệu quả của sáng kiến thể hiện rõ rệt ở bảng Bảng 2- kết quả thi học sinh giỏi năm 2019-2020.
16. 16 Bảng2- Kết quả thi học sinh giỏi năm học 2019-20205 Học sinh Điểm Đoạt Số Ngày tháng Họ và tên trường số giải TT năm sinh 1 Nguyễn Đoàn Ngọc Minh 17/10/2003 THPT Yên Thế 16,3 Nhất Khuyến 2 Nguyễn Việt Thành 2/12/2003 THPT Yên Thế 12 khích 3 Hoàng Văn Dũng 5/7/2003 THPT Bố Hạ 12,8 Ba 4 Nguyễn Anh Dũng 7/6/2003 THPT Bố Hạ 15,28 Nhì *Triển khai thực hiện sáng kiến lần 2 (Tháng 12/2020 đến 11/1/2021) tại trường THPT Yên Thế và THPT Việt Yên 1: Cách thức triển khai thực hiện sáng kiến lần 2: tương tự cách thức triển khai thực hiện sáng kiến lần 1. Giáo viên tham gia thực hiện sáng kiến của trường THPT Yên Thế: Ninh Thị Thu Hà; và trường THPT Việt Yên 1: Hoàng Văn Hùng. Học sinh tham gia đánh giá của mỗi trường gồm 8 học sinh, bài kiểm tra lần 1 chúng tôi lấy đề bài thuộc dạng 2. Vì kết quả kiểm tra lần 1 thấp do phương pháp cũ để học sinh tự làm, nên chúng tôi áp dụng sáng kiến cho 5 học sinh ở trường THPT Yên Thế và 4 học sinh ở trường THPT Việt Yên 1. Sau khi thực hiện bài kiểm tra số 2 (lấy một bài toán tương tự của dạng 2), nhận thấy kết quả bài làm của các bạn được bồi dưỡng sáng kiến cao hơn hẳn. Dưới đây là kết quả chấm bài kiểm tra 1 và bài kiểm tra số 2 bằng phần mềm chấm điểm tự động Themis khi thực hiện sáng kiến lần 2: 5 TB số 620/SGDĐT-KTKTCLGD ngày 08/06/2020 của SGDĐT BG về việc thông báo danh sách thí sinh đoạt giải kỳ thi chọn HSG VH cấp tỉnh bậc trung học năm học 2019-2020
17. 17 Trường THPT Yên Thế: Kết quả bài kiểm tra lần 1 Kết quả bài kiểm tra lần 2 Trường THPT Việt Yên 1 Kết quả bài kiểm tra lần 1 Kết quả bài kiểm tra lần 2
18. 18 Biểu đồ 2: So sánh kết quả bài kiểm tra 1 và bài kiểm tra 2 - thực hiện sáng kiến lần 2 (Tháng 12/2020 và tháng 1/2021) Chú giải: Điểm bài KT số 1 Điểm bài KT số 2 Nhìn vào biểu đồ 2 nhận thấy: - So sánh điểm kiểm tra 1 (KT1) và điểm kiểm tra 2 (KT2): Điểm KT 2 cao hơn hẳn, chiếm hơn 60% - Những học sinh có chữ K (không tham gia bồi dưỡng): điểm KT1 và KT2 không khác nhau nhiều, và cùng thấp (dưới 4) - Điểm KT2 cao vượt trội, thang điểm cao từ 6 trở lên chiếm 56% Trong kỳ thi học sinh giỏi văn hóa cấp tỉnh năm học 2020-2021, cả 4 bạn tham gia bồi dưỡng sáng kiến đi thi học sinh giỏi đạt cả 4 giải: 1 Nhất, 2 Nhì, 1 Ba. Hiệu quả của sáng kiến thể hiện rõ rệt ở bảng Bảng 3- Kết quả thi học sinh giỏi năm 2020-2021.
19. 19 Bảng 3 - Kết quả thi học sinh giỏi năm học 2020-20216 Số Ngày tháng Học sinh trường Điểm số Đoạt Họ và tên TT năm sinh giải 1 Nguyễn Việt Thành 05/01/2004 THPT Yên Thế 19 Nhất 2 Ngô Hoàng Phú 19/1/2004 THPT Yên Thế 16,4 Nhì 3 Nguyễn Hải Việt 14/7/2004 THPT Việt Yên 1 17,1 Nhì 4 Trần Hữu Hoàng 2/6/2004 THPT Việt Yên 1 10,7 Ba Nhận xét chung: Qua biểu đồ 1,2: nhận thấy những em được bồi dưỡng sáng kiến thì bài kiểm tra 2 đạt điểm cao hơn hẳn so với học sinh không tham gia bồi dưỡng sáng kiến, từ đó có thể thấy hiệu quả của việc áp dụng sáng kiến cũng như khả năng áp dụng sáng kiến kinh nghiệm trong thực tế bồi dưỡng học sinh giỏi ở trường phổ thông nói chung và trường THPT Yên Thế nói riêng. Qua bảng 2,3: Bảng kết quả thi học sinh giỏi các năm học 2019-2020; 2020-2021 cho thấy học sinh có tham gia bồi dưỡng sáng kiến kinh nghiệm có học sinh đoạt giải Nhất, đây là minh chứng khẳng định hiệu quả thực tế khi áp dụng sáng kiến kinh nghiệm trong bồi dưỡng học sinh giỏi cấp tỉnh. Sáng kiến kinh nghiệm này là tài liệu tham khảo hữu ích, giúp giáo viên nâng cao năng lực chuyên môn, đóng góp hiệu quả cho công tác giảng dạy mũi nhọn bồi dưỡng học sinh giỏi ở trường phổ thông, đồng thời góp phần định hướng phát triển năng lực tư duy, năng lực tự học cho học sinh, giúp học sinh nhận diện được bài toán ứng dụng quy hoạch động. * Cam kết: Tôi xin cam đoan những điều khai trên là trung thực, đúng sự thật và không sao chép hoặc vi phạm bản quyền. 6 QĐ số 183/QĐ-SGDĐT, ngày 18/03/2021 của Giám đốc SGDĐT BG về việc công nhận học sinh đoạt giải trong kỳ thi chọn HSGVH cấp tỉnh cấp trung học năm học 2020-2021
20. 20 Xác nhận của cơ quan, đơn vị Tác giả sáng kiến (Ký và đóng dấu) Ninh Thị Thu Hà Xác nhận của Hội đồng KH&CN, Sở GD&ĐT CHỦ TỊCH HỘI ĐỒNG PHÓ GIÁM ĐỐC SỞ GD&ĐT Bạch Đăng Khoa