MỤC LỤC
CÁC KÝ HIỆU VIẾT TẮT TRONG SÁNG KIẾN KINH NGHIỆM .......................... 3
I. Lời giới thiệu ............................................................................................................... 4
II. Tên sáng kiến: ............................................................................................................ 5
III. Tác giả sáng kiến: ..................................................................................................... 5
IV. Chủ đầu tư tạo ra sáng kiến:..................................................................................... 5
V. Lĩnh vực áp dụng sáng kiến: ..................................................................................... 5
VI. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: ....................................... 5
VII. Mô tả bản chất của sáng kiến: ................................................................................ 5
PHẦN I: SƠ ĐỒ NỘI DUNG SÁNG KIẾN KINH NGHIỆM ................................ 6
PHẦN II: NỘI DUNG SÁNG KIẾN KINH NGHIỆM ............................................. 7
I. Một số khái niệm cơ bản về phương pháp quy hoạch động ............................... 7
1.1. Khái niệm .................................................................................................... 7
1.2. Các bước giải quyết bài toán bằng phương pháp quy hoạch động. ............ 7
II. So sánh phương pháp quy hoạch động với các phương pháp khác ................ 11
2.1. Phương pháp quy hoạch động và phương pháp đệ quy ............................ 11
2.2. Phương pháp quy hoạch động và phương pháp vét cạn ........................... 15
III. Cài đặt chương trình cho một số bài toán đơn giản thường gặp .................... 15
Ví dụ 1: Bài toán tính an (n là số nguyên dương). ........................................... 16
Ví dụ 2: Tính n! (n là số nguyên dương) ......................................................... 18
Ví dụ 3: Dãy số fibonacci: ............................................................................... 20
Ví dụ 4: Bài toán tháp Hà Nội .......................................................................... 22
Ví dụ 5: Bài toán cái túi ................................................................................... 24
IV. Bài tập tự giải ................................................................................................. 29
Bài toán 1: Dãy con có tổng bằng S ................................................................ 29
Bài toán 2: Dãy con có tổng lớn nhất ............................................................... 29
Bài toán 3: Chia kẹo ......................................................................................... 30
VIII. Những thông tin cần bảo mật: Không ................................................................. 30
1
IX. Các điều kiện cần thiết để áp dụng sáng kiến: Học sinh đội tuyển Tin học lớp 10, 11, 12. ........................................................................................................................... 30
X. Đánh giá lợi ích thu được hoặc dự kiến có thể thu được do áp dụng sáng kiến theo ý kiến của tác giả: ............................................................................................................ 30
XI. Danh sách những tổ chức/cá nhân đã tham gia áp dụng thử hoặc áp dụng sáng kiến lần đầu: ......................................................................................................................... 32
TÀI LIỆU THAM KHẢO ............................................................................................ 33
2
CÁC KÝ HIỆU VIẾT TẮT TRONG SÁNG KIẾN KINH NGHIỆM
Ký hiệu Ý nghĩa
SKKN Sáng kiến kinh nghiệm
THPT Trung học phổ thông
ĐQ Đệ quy
DQ Đệ quy
QHĐ Quy hoạch động
QHD Quy hoạch động
PP Phương pháp
NXB Nhà xuất bản
3
BÁO CÁO KẾT QUẢ
NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN
I. Lời giới thiệu
Hiện nay, công nghệ thông tin xuất hiện ở mọi nơi, sự phát triển nhanh chóng của nó giúp cuộc sống của con người trở nên tốt đẹp hơn. Công nghệ thông tin giúp các nhà khoa học tạo ra những nghiên cứu vượt bậc nhờ việc tính toán và xử lý một khối lượng công việc khổng lồ của máy tính. Chúng có thể thực hiện hàng tỷ phép tính trong vài giây. Rất nhiều phần mềm ra đời nhằm giúp con người giải quyết công việc dễ dàng hơn. Các phần mềm được viết nhờ các Lập trình viên dựa trên các ngôn ngữ lập trình và Pascal là một ngôn ngữ lập trình giúp những người mới học lập trình dễ tiếp cận.
Tại các trường Trung học phổ thông hiện nay, nhiệm vụ quan trọng là đào tạo một cách toàn diện đồng thời chú trọng bồi dưỡng năng lực của học sinh. Chính vì vậy một trong những tiêu chí đánh giá chất lượng giáo dục của trường THPT là kết quả của việc thực hiện hoạt động bồi dưỡng học sinh giỏi. Đối với mỗi giáo viên THPT, bồi dưỡng học sinh giỏi là một nhiệm vụ quan trọng và khó khăn. Nó đòi hỏi giáo viên phải tìm hiểu, học tập rất nhiều kiến thức về chuyên ngành và các phương pháp giảng dạy thích hợp. Đối với giáo viên bộ môn Tin học, bồi dưỡng học sinh giỏi đòi hỏi giáo viên phải hiểu biết về lập trình và cần có các phương pháp giảng dạy thuật toán tốt giúp học sinh dễ dàng tiếp thu và vận dụng. Học sinh muốn đạt kết quả cao trong kỳ thi học sinh giỏi tỉnh và cao hơn cần phải có lượng kiến thức lớn và sâu trong việc lập trình. Những kiến thức này đối với chương trình phổ thông bình thường là không đủ đáp ứng. Nhiệm vụ của giáo viên là cung cấp thêm cho các em kiến thức, phương pháp lập trình để học sinh đạt kết quả tốt trong kỳ thi. Có nhiều phương pháp được dùng để thiết kế thuật toán như: Đệ quy (Recursion), quy hoạch động (Dynamic programming), chia để trị (Divide and conquer), vét cạn (Exhaustivesearch), tham lam (Greedy algorithms) ... Trong đó, mỗi thuật toán chỉ áp dụng cho những lớp bài toán phù hợp. Trong ngành khoa học máy tính, đệ quy là chìa khóa để thiết kế nhiều giải thuật quan trọng và cũng là cơ sở của quy hoạch động (Dynamic Programming). Quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (Overlapping subproblem) và cấu trúc con tối ưu (Optimal substructure). Phương pháp quy hoạch động là một phương pháp hiệu quả trong việc giải bài toán tối ưu hoá rời rạc. Có một số bài toán sử dụng phương pháp quy hoạch động lại cho hiệu quả cao hơn so với các phương pháp khác. Trong các kỳ thi học sinh giỏi tỉnh và cao hơn hiện nay, từ 30% đến 40% các bài thi cần đến quy hoạch động và đây là những bài toán khó, đòi hỏi học sinh phải có tư duy lập trình cao. Có thể có những cách khác để giải bài toán đó. Nhưng vì các bài thi đều có xét đến thời gian thực hiện (chạy) chương trình, cũng như dung lượng bộ nhớ để lưu trữ và thực hiện chương trình đó. Nên một thuật toán hiệu quả là cực kỳ cần thiết. Có nghĩa là cùng một bài toán, cách nào mà thời 4
gian thực hiện càng nhanh, chiếm ít bộ nhớ hơn sẽ được đánh giá cao hơn. Và trong những trường hợp như vậy, quy hoạch động là một trong những thuật toán phù hợp. Chỉ cần làm được những bài này là học sinh gần như có giải. Tuy nhiên, các em thường hay bị nhầm lẫn và khó phân biệt được khi thuật toán sử dụng phương pháp quy hoạch động và các phương pháp khác. Nên việc làm cho các em học sinh phổ thông có thể phân biệt và thấy được sự ưu việt của quy hoạch động từ đó sử dụng thành thạo phương pháp này trong lập trình không phải là vấn đề dễ dàng. Hiểu rõ các thuật toán là bước đầu giúp các em học sinh tự tin đồng thời phân tích bài toán và xác định phương pháp giải đúng đắn sẽ giúp các em có thành tích tốt hơn. Là một giáo viên giảng dạy bộ môn Tin học ở trường trung học phổ thông, sau nhiều năm tham gia dạy bồi dưỡng đội tuyển thi học sinh giỏi, tôi nhận thấy việc bồi dưỡng học sinh giỏi là nhiệm vụ vô cùng quan trọng và việc ứng dụng phương pháp quy hoạch động trong thiết kế thuật toán là một mảng kiến thức rất cần thiết đối với học sinh tham gia đội tuyển học sinh giỏi môn Tin học.
Vì vậy tôi chọn đề tài “Giúp học sinh tiếp cận với phương pháp quy hoạch động bằng một số bài toán đơn giản trong Tin học” làm đề tài nghiên cứu. Hy vọng đây sẽ là một tư liệu hữu ích cho các giáo viên, học sinh và những người quan tâm đến phần kiến thức này.
II. Tên sáng kiến:
Giúp học sinh tiếp cận với phương pháp quy hoạch động bằng một số bài toán
đơn giản trong Tin học.
III. Tác giả sáng kiến:
- Họ và tên: Nguyễn Thị Hà
- Địa chỉ tác giả sáng kiến: Xã Đại Đồng – huyện Vĩnh Tường – tỉnh Vĩnh Phúc
- Số điện thoại: 0977 212 636
- E_mail: nguyenthiha.gvnguyenvietxuan@vinhphuc.edu.vn
IV. Chủ đầu tư tạo ra sáng kiến: Nguyễn Thị Hà
V. Lĩnh vực áp dụng sáng kiến: Dạy bồi dưỡng học sinh đội tuyển Tin học, giáo viên hoặc những người quan tâm tới lập trình.
VI. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: Năm 2017 – 2018.
VII. Mô tả bản chất của sáng kiến:
5
PHẦN I: SƠ ĐỒ NỘI DUNG SÁNG KIẾN KINH NGHIỆM
6
PHẦN II: NỘI DUNG SÁNG KIẾN KINH NGHIỆM
I. Một số khái niệm cơ bản về phương pháp quy hoạch động
1.1. Khái niệm
* Quy hoạch động (Dynamic Programming) là một phương pháp rất hiệu quả giải nhiều bài toán tin học, đặc biệt là những bài toán tối ưu.
* Quy hoạch động trong ngành khoa học máy tính: Là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (Overlapping subproblem) và cấu trúc con tối ưu (Optimal substructure).
Phương pháp quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn cho tới khi giải được bài toán lớn nhất (bài toán ban đầu). Ý tưởng cơ bản của phương pháp quy hoạch động là tránh tính toán lại các bài toán con đã xét, nói cách khác phương pháp quy hoạch động đã thể hiện sức mạnh của nguyên lý chia để trị đến cao độ.
* Một bài toán P muốn giải bằng phương pháp quy hoạch động cần có 2 đặc điểm sau:
- Bài toán P thỏa mãn nguyên lý tối ưu Bellman, nghĩa là có thể sử dụng lời giải tối ưu của các bài toán con từ mức thấp nhất để tìm dần lời giải tối ưu cho bài toán con ở mức cao hơn và cuối cùng là lời giải tối ưu cho bài toán P.
- Bài toán P có các bài toán con phủ chồng lên nhau, nghĩa là không gian bài toán
con “hẹp” không tạo dạng hình cây.
1.2. Các bước giải quyết bài toán bằng phương pháp quy hoạch động.
- Bước 1: Xây dựng hàm mục tiêu
Áp dụng nguyên lý tối ưu của Bellman ta phân rã bài toán ban đầu thành các bài toán con có cùng cấu trúc sao cho việc giải quyết bài toán con cấp i phụ thuộc vào kết quả của các bài toán con trước đó. Cụ thể hóa bước này là ta phải xây dựng được hàm mục tiêu F(i) là nghiệm của bài toán con cấp i.
- Bước 2: Xác định các bài toán cơ sở.
Bài toán cơ sở là các bài toán con nhỏ nhất mà ta có thể biết ngay kết quả hoặc tính được kết quả dễ dàng. Đây chính là cơ sở để tính nghiệm cho các bài toán cấp lớn hơn.
- Bước 3: Xây dựng công thức truy hồi
7
Căn cứ vào ý nghĩa của hàm mục tiêu, tìm mối quan hệ giửa các bài toán con các cấp, ta tiến hành xây dựng công thức tính kết quả của bài toán cấp i dựa vào kết quả của các bài toán con cấp trước đó.
- Bước 4: Lập bảng phương án
Sử dụng công thức truy hồi và nghiệm các bài toán cơ sở tính nghiệm tất cả các
bài toán con và lưu trữ chúng vào bảng phương án.
- Bước 5: Kết luận nghiệm của bài toán.
Dựa vào bảng phương án chỉ ra nghiệm của bài toán. Các bước giải quyết trên
tuy rất cụ thể nhưng vẫn trừu tượng đối với học sinh.
Bài toán 1: Tính an (n là số nguyên dương)
- Bước 1: Hàm mục tiêu: f(i) là lũy thừa của ai
- Bước 2: Các bài toán cơ sở: f(0) = 1;
- Bước 3: Công thức truy hồi: f(i) = a* f(i-1)
- Bước 4: Bảng phương án
i 0 1 2 3 4 5 6 ….. ….
f(i) 1 a a*a1 a*a2 a*a3 a*a4 a*a5
- Bước 5: Nghiệm f(n) của bài toán
Bài toán 2: Tính n!
- Bước 1: Hàm mục tiêu: f(i) là giai thừa của số i
- Bước 2: Các bài toán cơ sở: f(0) = 1; f(1) = 1
- Bước 3: Công thức truy hồi: f(i) = i* f(i-1)
- Bước 4: Bảng phương án
i 0 1 2 3 4 5 6 ….. ….
f(i) 1 1 2*1= 2 3*2=6 4*6 = 24 5*24 = 120 6*120=720
- Bước 5: Nghiệm F(n) của bài toán
Bài toán 3: Tìm số Fibonaci thứ N?
- Bước 1: Hàm mục tiêu: f(i) là số fibonaci thứ i.
- Bước 2: Các bài toán cơ sở: f(0) = 1; f(1) = 1
- Bước 3: Công thức truy hồi: f(i) = f(i-1) + f(i-2)
8
- Bước 4: Bảng phương án
i 1 2 3 4 5 6 7 ….. ….
f(i) 1 1 2 3 5 8 13
- Bước 5: Nghiệm f(n) của bài toán
Bài toán 4: Tháp Hà Nội
Chuyển n chiếc đĩa từ cọc 1 sang cọc 2 theo thứ tự từ lớn đến nhỏ. có sử dụng cọc 3 làm cọc trung gian. Mỗi lần di chuyển được 1 đĩa. Và đĩa đĩa lớn phải ở dưới đĩa nhỏ.
- Bước 1: Hàm mục tiêu: f(i) - Bước 2: Các bài toán cơ sở: f(1): = 1
- Bước 3: Công thức truy hồi: f(i):=2*f(i-1)+1
- Bước 4: Bảng phương án
i 1 2 3 4 5 ….. ….
f(i) 1 3 7 15 31
- Bước 5: Nghiệm f(n) của bài toán
Bài toán 5: Bài toán cái túi
Trong siêu thị có n gói hàng (n <= 100), gói hàng thứ i có trọng lượng là Wi <= 100 và trị giá Vi <= 100. Một tên trộm đột nhập vào siêu thị, sức của tên trộm không thể mang được trọng lượng vượt quá M (M <= 100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất.
- Bước 1: Hàm mục tiêu: F[i,j] = max(F[i-1,j],V[i]+ F[i,j-W[i]])
- Bước 2: Các bài toán cơ sở: F[0,j] = 0
- Bước: Công thức truy hồi tính B[i, j].
Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1, 2, ...,i - 1, i} để
có giá trị lớn nhất sẽ có hai khả năng:
+ Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể bằng cách chọn trong số các gói {1, 2, ..., i - 1} với giới hạn trọng lượng là j. Tức là F[i, j] = F[i - 1, j] + Nếu có chọn gói thứ i (tất nhiên chỉ xét tới trường hợp này khi mà Wi j) thì F[i, j] bằng giá trị gói thứ i là Vi cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói {1, 2, ..., i - 1} với giới hạn trọng lượng j - Wi. Tức là về mặt giá trị thu được: F[i, j] = Vi + F[i - 1, j - Wi] Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể nên nó sẽ là max trong 2 giá trị thu được ở trên.
9
Cơ sở quy hoạch động:
Dễ thấy F[0, j] = giá trị lớn nhất có thể bằng cách chọn trong số 0 gói = 0.
- Bước 4: Bảng phương án
Ta xây dựng bảng phương án dựa trên công thức truy hồi trên. Để kiểm tra kết quả có chính xác hay không (nếu không chính xác chúng ta xây dựng lại hàm mục tiêu). Thông qua cách xây dựng hàm mục tiêu và bảng phương án chúng ta sẽ định hướng việc truy vết.
* Trường hợp mỗi vật được chọn 1 lần
N/M 0 3 1 2 4 5 6 8 9 10 11 12 13 14 15 7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 4 4 4 4 0
2 0 2 0 2 2 2 2 2 2 2 2 4 4 6 6 2
3 1 2 0 3 3 3 3 3 3 3 3 4 5 6 7 3
4 2 3 0 4 5 5 5 5 5 5 5 5 6 7 8 5
4 10 12 13 14 15 15 15 15 15 15 15 15 2 3 0 5
Vậy ta có thể chọn vật 2, 3, 4, 5
* Trường hợp mỗi vật được chọn nhiều lần
3 1 2 4 5 6 N/M 0 8 9 10 11 12 13 14 15 7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 4 4 4 4 0
2 0 2 0 2 4 4 6 8 8 10 10 12 12 14 14 6
3 1 2 0 3 4 5 6 8 9 10 11 12 13 14 15 7
6 2 4 0 4 8 10 12 14 16 18 20 22 24 26 28 30
2 4 0 5 6 10 12 14 16 20 22 24 26 30 32 34 36
Vậy chúng ta có thể chọn vật 4 (3 lần) và vật 5 (3 lần)
- Bước 5: Truy vết:
* Trường hợp 1: Trong bảng phương án F[n,m] chính là giá trị lớn nhất thu được khi chọn trong cả n vật với giới hạn trọng lượng là M.
10
Nếu f[n,M]=f[n-1,M] thì tức là không chọn vật thứ n, ta truy về f[n-1,M]. Còn nếu f[n,M]≠f[n-1,M] thì ta thông báo rằng phép chọn tối ưu có chọn vật thứ n và truy về f[n-1,M-Wn].
* Trường hợp 2: Trong bảng phương án F[n,m] chính là giá trị lớn nhất thu được khi chọn trong cả n vật với giới hạn trọng lượng là M.
Nếu f[n,M] = f[n-1,M] thì tức là không chọn vật thứ n, ta truy về f[n-1,M]. Còn nếu f[n,M] ≠ f[n-1,M] thì ta thông báo rằng phép chọn tối ưu có chọn vật thứ n và truy về f[n,M-Wn].
II. So sánh phương pháp quy hoạch động với các phương pháp khác
2.1. Phương pháp quy hoạch động và phương pháp đệ quy
Về mặt nguyên tắc phương pháp quy hoạch động rất giống với phương pháp đệ
quy.
* Giống nhau: Cả hai phương pháp đều sử dụng lời giải của các bài toán có kích thước bé hơn, đồng dạng với bài toán ban đầu để đưa ra lời giải của bài toán ban đầu.
* Khác nhau:
Quy hoạch động Đệ quy
- Gọi thực hiện các bài toán cả hai chiều: Từ trên xuống (top - down) hoặc từ dưới lên (bottom - up).
- Gọi thực hiện các bài toán có kích thước lớn trước rồi đến các bài toán có kích thước bé hay thực hiện các bài toán từ trên xuống (top - down)
- Các kết quả trung gian không được lưu lại nên khi cần dùng đến phải tính đi tính lại nhiều lần. - Các kết quả trung gian được lưu lại, khi giải các bài toán lớn hơn chỉ cần cần lấy ra không cần tính toán lại.
- Dùng phần lớn bộ nhớ để lưu trữ chương trình con. - Dành phần lớn bộ nhớ để lưu trữ các kết quả trung gian.
- Chiếm dung lượng bộ nhớ rất lớn, thông thường độ phức tạp là hàm mũ. - Tốn ít bộ nhớ hơn và thời gian thực hiện nhanh hơn
Trong hầu hết các bài toán thì quy hoạch động chiếm ưu thế hơn đệ quy nhưng trong một vài trường hợp cả hai bài toán thực hiện đều như nhau. Ta xét một số ví dụ cả về quy hoạch động và đệ quy để thấy được tính ưu việt của quy hoạch động.
Ví dụ 1: Bài toán tính an (n là số nguyên dương)
Quy hoạch động Đệ quy
11
var n,i,a:longint; var n, a:longint;
f:array[0..100] of int64; function lthua(a,n:longint):int64;
function lthua(a,n:longint):int64; begin
begin if n =0 then lthua:=1
f[0]:=1; else lthua:=a*lthua(a,n-1);
for i:=1 to n do f[i]:=a*f[i-1]; end;
lthua:=f[i];
end;
* Nhận xét: * Nhận xét:
- Khi chúng ta gọi hàm lthua(n,a) trong chương trình chính thì ở trong con sẽ gọi hàm lthua(n-1) và lthua(n-2)
- Ta xây dựng mảng f chứa các giá trị trung gian nên khi cần dùng đến chỉ cần lấy ở trong f ra không cần phải tính lại. Nên chương trình thực hiện sẽ nhanh hơn, không tốn bộ nhớ.
- Rồi để gọi hàm lthua(n-1) thì lại phải gọi hàm lthua(n-2) và lthua(n-3) … cứ như vậy các hàm sẽ bị gọi lặp lại rất nhiều lần.
- Như vậy trong bài này khi ta dùng đệ quy để giải bài toán. Mỗi lần muốn dùng lại hàm nào thì nó gọi lại hàm đó nên sẽ tốn nhiều bộ nhớ
Ví dụ 2: Tính n!
Ta có định nghĩa như sau: n! = nếu
Cho một số nguyên dương n (0 < n < 13).
Quy hoạch động Đệ quy
var n,i:longint; var n:longint;
f:array[0..100] of int64;
function gt(n:longint):int64; function gt(n:longint):int64;
begin begin
12
if n<2 then gt:=1 f[0]:=1;
else gt:=n*gt(n-1); f[1]:=1;
for i:= 2 to n do f[i]:=i*f[i-1]; end;
gt:=f[i];
end;
Ví dụ 3: Tính phần tử thứ n của dãy số Fibonaci
Ta có định nghĩa như sau: f(n) = nếu
Cho một số nguyên dương n (0 < n < 50).
Quy hoạch động Đệ quy
var n,i,a: longint; var n: longint;
f: array[0..100] of longint;
function fibo(n:longint): int64; function fibo(n:longint):int64;
begin begin
f[0]:=1; f[1]:=1; if n <2 then fibo:= 1
for i:=2 to n do f[i]:=f[i-1]+ f[i-2]; else fibo(n):=fibo(n-1)+fibo(n-2);
end; fibo:=f[i];
end;
* Nhận xét * Nhận xét:
- Độ phức tạp: O(n).
- Mỗi bài toán con sẽ được lưu lại vào mảng f trước khi tính những bài toán con lớn hơn. Nhờ đó, mà việc tính toán giảm đi đáng kể, mỗi bài toán con chỉ cần tính đúng một lần.
- Độ phức tạp: O(an) với a 1.61803... - Do hàm f(n-1) và f(n-2) được tính một cách độc lập. Số lần gọi cần để tính f(n) là số lần gọi để tính f(n-1) cộng với số lần gọi để tính f(n-2). Nếu tính toán như trên, chúng ta có rất nhiều bài toán con sẽ được tính đi tính lại, điển hình là các số f(1) và f(2).
- Đặc điểm của lời giải bài toán theo phương pháp quy hoạch động: giải quyết bài toán đệ quy từ mức thấp trước, lời giải của chúng được lưu lại và được sử dụng - Đặc điểm của lời giải đệ quy: thực hiện bài toán từ việc phân tích ở mức cao xuống mức thấp.
13
để tìm lời giải của các bài toán ở mức cao hơn.
Ví dụ 4: Bài toán tháp Hà Nội
Chuyển n chiếc đĩa từ cọc 1 sang cọc 2 theo thứ tự từ lớn đến nhỏ. có sử dụng cọc 3 làm cọc trung gian. Mỗi lần di chuyển được 1 đĩa. Và đĩa đĩa lớn phải ở dưới đĩa nhỏ.
Quy hoạch động Đệ quy
var n,i:longint; var n,i:longint;
f:array[0..100] of longint; function thaphanoi(n:longint):longint;
function thaphanoi(n:longint):longint; begin
begin if n = 1 then exit(1)
f[1]:=1; else exit (2*thaphanoi(n-1)+1);
for i:= 2 to n do f[i]:=2*f[i-1]+1; end;
thaphanoi:=f[i];
end;
Ví dụ 5: Bài toán cái túi
Trong siêu thị có n gói hàng (n <= 100), gói hàng thứ i có trọng lượng là Wi <= 100 và trị giá Vi <= 100. Một tên trộm đột nhập vào siêu thị, sức của tên trộm không thể mang được trọng lượng vượt quá M ( M <= 100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất.
Quy hoạch động Đệ quy
procedure qhd; procedure test;
begin var i1,s1,s:longint;
fillchar(f[0],sizeof(f[0]),0); begin
for i:=1 to n do s:=0;
for j:=1 to m do s1:=0;
begin for i1:=1 to n do
dem:=dem+1; begin
f[i,j]:=f[i-1,j]; inc(dem);
14
s:=s+v[f[i1]];
if (j>=w[i]) and (f[i- 1,j-w[i]]+v[i]>c[i,j]) then s1:=s1+w[f[i1]];
if s1>m then exit; f[i,j]:=f[i-1,j- w[i]]+v[i]; end; end; if s>max then max:=s; end; end;
2.2. Phương pháp quy hoạch động và phương pháp vét cạn
Quy hoạch động Vét cạn
- Vét cạn là một trong những thuật toán giải bài toán tối ưu
- Quy hoạch động là tìm một kĩ thuật tìm kết quả trước thông qua một kết quả có sẵn hoặc được tìm thấy
- Thuật toán vét cạn là thuật toán tìm phương án tối ưu của bài toán bằng cách lựa chọn một phương án trong tập hợp tất cả các phương án của bài toán để tìm ra phương án tối ưu. Trong nhiều bài toán, không gian các phương án quá lớn. Vét cạn giúp tìm ra kết quả tối ưu nhưng độ phức tạp lớn, thường là hàm mũ trong khi phương pháp quy hoạch động độ phức tạp là đa thức. Do vậy, khi áp dụng thuật toán vét cạn không đảm bảo về thời gian cũng như kĩ thuật. Vét cạn là xét toàn bộ trường hợp, rồi tìm ra kết quả.
- Ưu điểm là chạy rất nhanh - Ưu điểm của vét cạn là chắc chắn tìm ra lời giải (nếu có)
- Nhược điểm của nó là có thể chạy quá lâu, vượt mức thời gian cho phép
- Nhược điểm của nó là rất khó tìm ra thuật toán, với một số bài toán có thể sẽ không có thuật toán quy hoạch động.
Chú ý: Vét cạn theo nghĩa thông thường là xét hết mọi đối tượng hay mọi trường hợp. Trong lập trình, vét cạn là phương pháp được dùng khi không còn phương pháp nào hiệu quả hơn có thể sử dụng được.
III. Cài đặt chương trình cho một số bài toán đơn giản thường gặp
Vì trong đề tài chỉ nói đến những bài toán đơn giản nên thường là những bài toán dễ tìm ra phương pháp giải và phương pháp giải thường dùng là đệ quy hoặc quy hoạch 15
động. Nên phần ví dụ trong SKKN này mỗi bài toán tôi chỉ xin phép đề cập đến mối tương quan giữa hai phương pháp là đệ quy và quy hoạch động. Tức là trong phần chương trình của từng bài tôi thường có thêm biến “đếm” để đếm số lần lặp thực hiện trong từng bài khi chạy cùng số test để người học có thể thấy được cái nào hay, cái nào ngắn hơn. Giúp người học dể hiểu, dễ phân biệt và rút ra được cái hay và cái chưa hay của quy hoạch động trong từng bài toán.
Ví dụ 1: Bài toán tính an (n là số nguyên dương).
Cách xác định bài toán
- Input: a, n
- Output: giá trị an
Ý tưởng của bài toán
- Ta thấy n = 0 thì f(0) =1
n = 1 thì f(1) = a
n = 2 thì f(2) = f(1)*a
n = 3 thì f(3) = f(2)*a
…..
n = i thì f(i) = f(i-1)*a
- Trong bài toán này có giá trị chặn là n = 0
Cài đặt chương trình
Phương pháp QHĐ Phương pháp ĐQ
uses crt; uses crt;
var n,i,a,dem:longint; var n,a,dem:longint;
g:text; f:text;
f:array[0..100] of int64; function lthua(a,n:longint):int64;
function lthua(a,n:longint):int64; begin
dem:=dem+1; begin
if n =0 then lthua:=1 f[0]:=1;
else lthua:=a*lthua(a,n-1); for i:=1 to n do
begin end;
f[i]:=a*f[i-1]; BEGIN
16
dem:=dem+1; clrscr;
end; dem:=0;
lthua:=f[i]; assign(f,'nhap.inp'); reset(f);
end; //write('nhap a,n:=') ; readln(a,n);
BEGIN readln(f,a,n);
clrscr; close(f);
assign(g,'nhap.inp'); reset(g); assign(f,'xuat.out'); rewrite(f);
dem:=0; lthua(a,n);
//write('nhap a,n:=');readln(a,n);
writeln(f,'KQ BT luy thua thuc hien bang pp DE QUY la:'); readln(g,a,n);
writeln(f,'so lan lap la:=',dem); close(g);
write(f,'luy thua la:=',lthua(a,n)); lthua(a,n);
close(f); assign(g,'xuat.out'); rewrite(g);
END.
writeln(g,'KQ BT lthua thuc hien bang pp QHD la:');
writeln(g,'so lan lap la:=',dem);
write(g,'lthua la:=',lthua(a,n));
close(g);
END.
Chạy thử chương trình
17
* Nhận xét: Qua phần chạy thử bộ test 210 ta thấy chương trình chạy bằng quy hoạch động số lần lặp là 10. Còn chương trình chạy bằng đệ quy số lần lặp lại bằng 11. Số lần lặp sử dụng phương pháp QHĐ ít hơn sử dụng phương pháp ĐQ 1 lần.
Ví dụ 2: Tính n! (n là số nguyên dương)
Cách xác định bài toán
- Input: n
- Output: giá trị giai thừa của n
Ý tưởng của bài toán
- Ta thấy n = 0 thì f(0) =1
n = 1 thì f(1) = 1
n = 2 thì f(2) = f(1)*2
n = 3 thì f(3) = f(2)*3
…..
n = i thì f(i) = f(i-1)*i
- Trong bài toán này có hai giá trị chặn là n = 0 và n = 1
Cài đặt chương trình
Phương pháp QHĐ Phương pháp ĐQ
Uses crt; Uses crt;
var n,i,dem:longint; var dem,n:longint;
f:text; g:text;
f:array[0..100] of int64; function gthua(n:longint):int64;
function gthua(n:longint):int64; begin
begin dem:=dem+1;
f[1]:=1; if n <2 then gthua:=1
for i:= 2 to n do else gthua:=(n*gthua(n-1));
begin end;
dem:=dem+1; BEGIN
f[i]:=i*f[i-1]; clrscr;
end; dem:=0;
18
//write('nhap n:='); readln(n); exit(f[n]);
assign(f,'nhap.inp'); reset(f); end;
readln(f,n); BEGIN
close(f); clrscr;
assign(f,'xuat.out'); rewrite(f); dem := 1;
//write('nhap n:='); readln(n); gthua(n) ;
//n := 15;
writeln(f,'KQ BT tinh GIAI THUA bang PP DE QUY la:'); assign(g,'nhap.inp'); reset(g);
writeln(f,'So lap la:=',dem); readln(g,n);
close(g); writeln(f,'Giai thua cua ',n,' co gia tri la:=',GTHUA(n)); assign(g,'xuat.out'); close(f); rewrite(g); END. gthua(n) ;
writeln(g,'KQ BT tinh GIAI THUA bang PP QHD la:');
writeln(g,'So lan lap la:=',dem);
writeln(g,'Giai thua cua so ',n,' co gia tri la:=',gthua(n));
close(g);
END.
Chạy thử chương trình
19
* Nhận xét: Ta chạy thử với test bằng 5 thì số lần lặp của hai phương pháp trên là như nhau, đều lặp lại 5 lần. Ta thấy rằng trong trường hợp này phương pháp quy hoạch động không hơn gì phương pháp đệ quy.
Ví dụ 3: Dãy số fibonacci:
Tính số hạng thứ n của dãy fibonacci bằng phương pháp đệ quy.
Trong đó chuỗi có giá trị như sau: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Cách xác định bài toán
- Input: n
- Output: giá trị fibonacci của n
Ý tưởng của bài toán
- Ta thấy n = 0 thì f(0) =1
n = 1 thì f(1) = 1
n = 2 thì f(2) = f(1) + f(0)
n = 3 thì f(3) = f(2) + f(1)
…..
n = i thì f(i) = f(i-1) + f(i-2)
- Trong bài toán này có hai giá trị chặn là n = 0 và n = 1
Cài đặt chương trình
Phương pháp QHĐ Phương pháp ĐQ
uses crt; uses crt;
var n,i,a,dem:longint; var n,i,dem:longint;
f:array[0..100] of longint; f:text;
g:text; function dq(n:longint):int64;
function qhd(n:longint):int64; begin
begin dem:=dem+1;
f[0]:=1; f[1]:=1; if n<2 then exit(1)
else exit(dq(n-1)+dq(n-2)); for i:=2 to n do
begin end;
f[i]:=f[i-1]+f[i-2]; BEGIN
20
dem:=dem+1 ; clrscr;
end; dem:=0;
qhd:=f[i]; //Write('nhap n:='); readln(n);
end; assign(f,'nhap.inp'); reset(f);
BEGIN readln(f,n);
clrscr; close(f);
dem := 2; dq(n) ;
// Write('nhap n:='); readln(n); assign(f,'xuat.out'); rewrite(f);
assign(g,'nhap.inp'); reset(g);
writeln(f,'KQ BT tinh so FIBO bang PP DE QUY la:'); readln(g,n);
writeln(f,'So lan lap la:=',dem); close(g); qhd(n);
assign(g,'xuat.out'); rewrite(g); writeln(f,'So FIBO thu ',n,' co gia tri la:=',dq(n));
close(f); writeln(g,'KQ BT tinh so FIBO bang PP QHD la:');
END. writeln(g,'So lan lap la:=',dem);
writeln(g,'So FIBO thu ',n,' co gia tri la:=',qhd(n));
close(g);
END.
Chạy thử chương trình
21
* Nhận xét: Trong bài toán này khi chạy thử với giá trị n nhỏ thì thấy số lần lặp không hơn nhau nhiều. Nhưng khi chạy thử với giá trị n lớn hơn thì đối với phương pháp QHĐ ta thấy số lần lặp là 41. Còn đối với phương pháp ĐQ số lần lặp là 331 160 281, lớn hơn rất nhiều so với QHĐ. Như vậy, trong bài toán này ta chọn PP QHĐ sẽ nhanh hơn ĐQ rất nhiều.
Ví dụ 4: Bài toán tháp Hà Nội
Chuyển n chiếc đĩa từ cọc 1 sang cọc 2 theo thứ tự từ lớn đến nhỏ. có sử dụng cọc 3 làm cọc trung gian. Mỗi lần di chuyển được 1 đĩa. Và đĩa đĩa lớn phải ở dưới đĩa nhỏ.
Cách xác định bài toán
- Input: n
- Output: Số bước thực hiện chuyển đĩa từ cọc này sang cọc khác.
Ý tưởng của bài toán
Đầu tiên ta phải chuyển được tất cả (n-1) đĩa nhỏ qua cột thứ hai, chuyển đĩa to nhất qua cột thứ ba rồi chuyển (n-1) đĩa từ cột thứ hai sang cột thứ ba. Trò chơi sẽ kết thúc!
Nếu gọi S(n) là số bước để di chuyển n đĩa qua cột ta cần thì:
Bước 1: Chuyển (n-1) đĩa bé hơn từ cột (1) sang cột (2). Chúng ta có S(n-1)
bước di chuyển.
Bước 2: Chuyển đĩa to nhất từ cột (1) sang cột (3). Chúng ta có 1 bước di
chuyển.
Bước 3: Chuyển (n-1) đĩa từ cột (2) sang cột (3). Chúng ta có S(n-1) bước di
chuyển.
22
Cài đặt chương trình
Phương pháp QHĐ Phương pháp ĐQ
uses crt; uses crt;
var dem,i,n:longint; var dem,n:longint;
f:array[0..100] of longint; f:text;
g:text; function thaphn(n:longint):longint;
function thaphn(n:longint):longint; begin
begin dem:=dem+1;
// dem:=dem+1; if n=1 then exit(1)
f[1]:=1; else exit (1+2*thaphn(n-1)) ;
for i:=2 to n do end;
begin BEGIN
f[i]:=2*f[i-1]+1; clrscr;
dem := dem+1; dem:=0;
end; assign(f,'nhap.inp');
thaphn:=f[i]; reset(f);
end; readln(f,n);
BEGIN close(f);
clrscr; assign(f,'xuat.out');
dem := 1; rewrite(f);
//write('Nhap vao so chiec dia:='); readln(n); // write('Nhap vao so chiec dia:='); readln(n);
assign(g,'nhap.inp'); reset(g);
writeln(f,'KQ BT thap HA NOI bang PP DQ la:'); readln(g,n);
// thaphn(n); close(g);
lan chuyen la : assign(g,'xuat.out'); rewrite(g); writeln(f,'so ',thaphn(n));
writeln(f,'So lan lap la:=',dem); writeln(g,'KQ BT thap HA NOI bang PP QHD la:');
23
close(f); //thaphn(n);
lan chuyen la : END.
writeln(g,'so ',thaphn(n));
writeln(g,'So lan lap la:=',dem);
close(g);
END.
Chạy thử chương trình
* Nhận xét: Trong bài toán này cả hai phương pháp đều có số lần lặp như nhau.
Ví dụ 5: Bài toán cái túi
Trong siêu thị có n gói hàng (n <= 100), gói hàng thứ i có trọng lượng là Wi <= 100 và trị giá Vi <= 100. Một tên trộm đột nhập vào siêu thị, sức của tên trộm không thể mang được trọng lượng vượt quá M (M <= 100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất.
Cách xác định bài toán
caitui.inp caitui. out
Dòng 1: n, m cách nhau ít nhất một
Ghi giá trị lớn nhất tên trộm có thể lấy
dấu cách
n dòng tiếp theo: Mỗi dòng gồm 2 số Wi, Vi, là chi phí và giá trị đồ vật thứ i.
Ví dụ
24
caitui. out caitui.inp
15 5 15
12 4
2 2
1 1
1 2
4 10
Ý tưởng của bài toán
Giải quyết bài toán trong các trường hợp sau:
Mỗi vật chỉ được chọn một lần.
Mỗi vật được chọn nhiều lần (không hạn chế số lần)
Cách giải:
* Trường hợp mỗi vật được chọn 1 lần
Ta nhận thấy rằng: Giá trị của cái túi phụ thuộc vào 2 yếu tố: Có bao nhiêu vật đang được xét và trọng lượng còn lại cái túi có thể chứa được, do vậy chúng ta có 2 đại lượng biến thiên. Cho nên hàm mục tiêu sẽ phụ thuộc vào hai đại lượng biến thiên. Do vậy bảng phương án của chúng ta sẽ là bảng 2 chiều.
Gọi F[i,j] là 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à trọng của cái túi chưa vượt quá j. Với giới hạn j, việc chọn tối ưu trong số các vật {1,2,…,i-1,i} để có giá trị lớn nhất sẽ có hai khả năng:
Nếu không chọn vật thứ i thì F[i,j] là giá trị lớn nhất có thể chọn trong số các vật
{1,2,…,i-1} với giới hạn trọng lượng là j, tức là:
F[i,j]:=F[i-1,j].
Nếu có chọn vật thứ i (phải thỏa điều kiện W[i] ≤ j) thì F[i,j] bằng giá trị vật thứ i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các vật {1,2,…,i-1} với giới hạn trọng lượng j-W[i] tức là về mặt giá trị thu được:
F[i,j]:=V[i]+F[i-1,j-W[i]]
Vậy chúng ta phải xem xét xem nếu chọn vật i hay không chọn vật i thì sẽ tốt hơn.
Từ đó chúng ta có công thức truy hồi như sau.
F[0,j] = 0 (hiển nhiên) – Bài toán con nhỏ nhất.
25
F[i,j]= max(F[i-1,j], V[i]+F[i-1,j-W[i]]
* Trường hợp mỗi vật được chọn nhiều lần: Tương tự như suy luận ở trên ta xét:
Nếu không chọn vật thứ i thì F[i,j] là giá trị lớn nhất có thể chọn trong số các vật
{1,2,…,i-1} với giới hạn trọng lượng là j, tức là:
F[i,j]:=F[i-1,j].
Nếu có chọn vật thứ i (phải thỏa điều kiện W[i] ≤ j) thì F[i,j] bằng giá trị vật thứ i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các vật {1,2,…,i} (vì vật i vẫn có thể được chọn tiếp) với giới hạn trọng lượng j-W[i] tức là về mặt giá trị thu được:
F[i,j]:=V[i]+F[i,j-W[i]]
Do vậy chúng ta có công thức truy hồi như sau:
F[0,j] = 0 (hiển nhiên) – Bài toán con nhỏ nhất.
F[i,j]= max(F[i-1,j], V[i]+F[i,j-W[i]]
Cài đặt chương trình
Phương pháp QHĐ Phương pháp ĐQ
uses crt; uses crt;
const const
fi='nhap.inp'; fi='nhap.inp';
fn='xuat.out'; fn='xuat.out';
var var
g1,g2:text; g1,g2:text;
n,m,i,j,dem:longint; v,w,f:array[0..100] of longint;
v,w:array[1..100] of longint; n,m,i,j,dem,max:longint;
f:array[0..100,0..100] of longint; kt:array[0..100] of boolean;
//================= //=================
procedure qhd; procedure test;
begin var i1,s1,s:longint;
fillchar(f[0],sizeof(f[0]),0); begin
for i:=1 to n do s:=0; s1:=0;
26
for j:=0 to m do for i1:=1 to n do
begin begin
dem:=dem+1; inc(dem);
f[i,j]:=f[i-1,j]; s:=s+w[f[i1]];
(j>=v[i]) and s1:=s1+v[f[i1]];
if (f[i-1,j-v[i]]+w[i]>f[i,j]) then if s1>m then exit;
end; f[i,j]:=f[i-1,j- v[i]]+w[i]; if s>max then max:=s; end; end; end; //=================== //================== procedure try(i:longint); begin var j:longint; clrscr; begin assign(g1,fi); reset(g1); inc(dem); assign(g2,fn); rewrite(g2); for j:=0 to n do readln(g1,n,m); if (j=0) or (kt[j]) then to n do begin i:=1 for readln(g1,v[i],w[i]);
kt[j]:=false; dem:=0;
f[i]:=j; qhd;
if (i=n) then test
writeln(g2, 'KQ cua BT cai tui giai = pp qhd la: '); else try(i+1);
kt[j]:=true;
writeln(g2, 'gia tri lon nhat co the la: ', f[n,m]); end;
end; writeln(g2, 'so lan lap la: ', dem); //=================== close(g1); close(g2); begin end. clrscr;
assign(g1,fi); reset(g1);
27
assign(g2,fn); rewrite(g2);
readln(g1,n,m);
v[0]:=0; w[0]:=0; dem:=0;
for i:=1 to n do
begin
kt[i]:=true;
readln(g1,v[i],w[i]);
end;
max:=0; try(1);
writeln(g2,' KQ cua BT cai tui bang PP DQ la :');
writeln(g2,' gia tri lon nhat : ',max);
writeln(g2,' so lan lap la: ',dem);
close(g1); close(g2);
end.
Chạy thử chương trình
* Nhận xét: Trong bài toán này ta thấy PP QHĐ có số lần lặp ít hơn rất nhiều so với PP ĐQ.
28
IV. Bài tập tự giải
Bài toán 1: Dãy con có tổng bằng S
Cho N số nguyên dương tạo thành dãy A={A1,…,AN}. Tìm một dãy con của A
có tổng các phần tử bằng S.
Dữ liệu vào từ file DAYCON.INP
Dòng đầu tiên ghi hai số nguyên dương N (0≤N≤200) và S (0≤S≤40000)
Các dòng tiếp theo lần lượt ghi N số hạng của dãy A (0≤Ai≤200)
Kết quả ra ghi ra file DAYCON.OUT
Nếu bài toán vô nghiệm ghi số 0.
Nếu bài toán có nghiệm thì trên dòng thứ nhất ghi số 1. Các dòng tiếp theo, mỗi
dòng ghi hai số là chỉ số trong dãy A và giá trị của một phần tử được chọn.
Bài toán 2: Dãy con có tổng lớn nhất
Cho dãy n số nguyên dương a1, a2, …, an. Một dãy con của dãy nói trên là dãy được lập từ dãy đã cho bằng cách bỏ đi một số số hạng của dãy và giữ nguyên trật tự các số còn lại. Hãy tìm một dãy con thoả mãn tính chất:
Không có ba số liên tiếp nào của dãy ban đầu có mặt trong dãy con
Trong ba số liên tiếp của dãy ban đầu có ít nhất một số có mặt trong dãy con
Tổng các số hạng của dãy con được chọn là lớn nhất có thể được.
Dữ liệu: Vào từ file CHONSO.INP:
Dòng đầu tiên chứa số nguyên dương N (N≤1000)
N dòng tiếp theo, dòng thứ i chứa số nguyên dương ai (ai≤30000)
Kết quả: Ghi ra file văn bản CHONSO.OUT:
Dòng đầu tiên chứa hai số nguyên dương M và T trong đó M là số lượng các số
hạng của dãy con được chọn, T là tổng các số của dãy chon được chọn.
M dòng tiếp theo lần lợt mô tả các số hạng của dãy con được chọn, dòng thứ k
ghi số jk là chỉ só của số hạng được chọn thứ k.
Ví dụ:
CHONSO.INP CHONSO.OUT
6 2 21 4 2
29
3 5 6
6 5 1 7 3
Bài toán 3: Chia kẹo
Có N gói kẹo, gói thứ i có A[i] cái kẹo.
Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch
giữa số kẹo ở hai phần là ít nhất có thể được. 0 Dữ liệu vào: Cho trong file CANDY.INP: Gồm N dòng, dòng thứ i chứa số nguyên
A[i] là số kẹo trong gói thứ i Kết quả: Ghi ra file CANDY.OUT: Dòng đầu tiên ghi 3 số: Tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai phần Dòng 2, 3 là số hiệu các gói kẹo ở mỗi phần được chia. Ví dụ: CANDY.INP CANDY.OUT 14 12 2
3 4 7
12 3
4
7
12 VIII. Những thông tin cần bảo mật: Không IX. Các điều kiện cần thiết để áp dụng sáng kiến: Học sinh đội tuyển Tin học lớp
10, 11, 12. X. Đánh giá lợi ích thu được hoặc dự kiến có thể thu được do áp dụng sáng kiến
theo ý kiến của tác giả: Học sinh được học theo nội dung trình bày trong sáng kiến sẽ có cái nhìn toàn
diện hơn, tự tin hơn khi đối mặt với bài toán trong Tin học từ đó các em sẽ thích học và
chủ động tìm hiểu kiến thức. Nội dung sáng kiến được trình bày logic, phù hợp với
trình độ phát triển tư duy của học sinh từ nhận biết, thông hiểu đến vận dụng, nâng cao
và sáng tạo qua đó giúp cho học sinh phát triển tư duy tổng hợp và rèn luyện các kĩ
năng viết chương trình sử dụng phương pháp quy hoạch động. 30 Bảng số liệu kết quả của học sinh đội tuyển Tin trường THPT Nguyễn Viết Xuân năm học 2017 – 2018 khi chưa thực hiện đề tài: Số học sinh đạt giải STT Khối Số lượng hs Nhất Nhì Ba KK 1 10 5 0 0 0 2 2 11 3 0 0 1 1 3 12 1 0 0 1 0 - Một số học sinh có tiến bộ rõ rệt khi tiếp cận các bài toán sử dụng phương pháp QHĐ. - Nâng cao việc yêu thích học Tin học đối với một bộ phận học sinh và một số em có
định hướng nghề nghiệp sau này. - Bảng số liệu kết quả đạt được của học sinh đội tuyển Tin học – trường THPT Nguyễn
Viết Xuân năm học 2018 – 2019 sau khi thực hiện đề tài: Số học sinh đạt giải STT Khối Số lượng hs Nhất Nhì Ba KK 1 10 5 0 1 2 1 2 11 4 0 1 2 0 3 12 4 0 1 2 1 Bản thân tôi khi viết đề tài này đã phần nào đó rèn luyện cho mình khả năng
nghiên cứu khoa học, tìm tòi và phân tích và tổng hợp tài liệu từ nhiều nguồn khác
nhau, tăng cường khả năng tự học, tự bồi dưỡng chuyên môn. Sáng kiến kinh nghiệm sẽ là tài liệu tham khảo cơ bản về phương pháp quy hoạch động để trao đổi kinh nghiệm với đồng nghiệp và truyền đạt cho học sinh. Mặc dù đã cố gắng rất nhiều trong quá trình viết sáng kiến kinh nghiệm này
nhưng do thời gian có hạn nên chắc chắn sẽ không tránh khỏi những sai sót. Kính mong
quý thầy cô, đồng nghiệp và học sinh chân thành góp ý để sáng kiến kinh nghiệm:
“Giúp học sinh tiếp cận với thuật toán quy hoạch động bằng một số bài toán đơn giải
trong Tin học” được hoàn thiện hơn và trở thành một tài liệu hay, hữu ích trong việc
dạy và học lập trình. 31 XI. Danh sách những tổ chức/cá nhân đã tham gia áp dụng thử hoặc áp dụng sáng
kiến lần đầu: Phạm vi/Lĩnh vực STT Tên tổ chức/cá nhân Địa chỉ áp dụng sáng kiến 1 Nguyễn Thị Hà Trường THPT Nguyễn
Viết Xuân Học sinh đội tuyển Tin
học khối 10, 11, 12 32 TÀI LIỆU THAM KHẢO [1]. Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Lê Minh Hoàng, Nguyễn Thanh Hùng
(2009), Tài liệu giáo khoa chuyên tin, NXB Giáo dục. [2]. Robert Sedgewich – Người dịch: Trần Đan Thư, Vũ Mạnh Tưởng, Dương Vũ Diệu
Trà, Nguyễn Tiến Huy (In lần thứ 5), Cẩm nang thuật toán, NXB Khoa học và kỹ thuật [3]. Lê Minh Hoàng, Bài giảng chuyên đề Giải thuật và lập trình, NXB Đại học sư
phạm Hà Nội, 1999 – 2002. [4]. Trần Lê Hồng Dũ, Phạm Ngọc Chí Nhân – Trường THPT Bến Tre, Các bài toán
về quy hoạch động. [5]. Nguyễn Hưu Điển, Một số vấn đề về thuật toán, NXB Giáo dục [6]. Nguyễn Chí Trung, Giáo trình thuật toán và kỹ thuật lập trình Pascal – NXB Sở
giáo dục và đào tạo Hà Nội. 33Vĩnh Tường,
Vĩnh Tường,
Vĩnh Tường,
Ngày 12 tháng 02 năm 2020
ngày 14 tháng 02 năm 2020
ngày 10 tháng 02 năm 2020
Thủ trưởng đơn vị/
CHỦ TỊCH HỘI ĐỒNG
Tác giả sáng kiến
Chính quyền địa phương
SÁNG KIẾN CẤP CƠ SỞ
(Ký, ghi rõ họ tên)
(Ký tên, đóng dấu)
(Ký tên, đóng dấu)
Nguyễn Thị Hà
