Sáng kiến kinh nghiệm THPT: Phương pháp quy hoạch động và ứng dụng vào giải một số bài toán bồi dưỡng học sinh giỏi, thi chuyên bằng ngôn ngữ lập trình Pascal và C++

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

27
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài nêu ra các định hướng giúp học sinh có thể tiếp cận phương pháp Quy hoạch động để giải một số bài toán tối ưu phù hợp với dữ liệu bài toán; Giúp người đọc tiếp cận ngôn ngữ lập trình C++ tốt hơn trong khi lập trình.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Phương pháp quy hoạch động và ứng dụng vào giải một số bài toán bồi dưỡng học sinh giỏi, thi chuyên bằng ngôn ngữ lập trình Pascal và C++

SỞ GD&ĐT NGHỆ AN TRƯỜNG THPT CON CUÔNG ……………………… SÁNG KIẾN KINH NGHIỆM NÀ M TÊN ĐỀ TÀI: PHƯƠNG PHÁP QUY HOẠCH ĐỘNG VÀ ỨNG DỤNG VÀO GIẢI MỘT SỐ BÀI TOÁN BỒI DƯỠNG HỌC SINH GIỎI, THI CHUYÊN BẰNG NGÔN NGỮ LẬP TRÌNH PASCAL VÀ C++ Nhóm tác giả: 1. Đặng Văn Hảo 2. Ngô Thị Thanh Huyền 3. Phan Thị Thuý An Lĩnh vực: Tin học Đơn vị: Trường THPT Con Cuông Con Cuông - Năm 2022 2
MỤC LỤC Phần I. Đặt vấn đề: ................................................................................................. 5 1. Lí do chọn đề tài ................................................................................................. 5 2. Mục đích nghiên cứu, đóng góp mới của đề tài ............................................... 5 3. Đối tượng nghiên cứu .......................................................................................... 6 4. Phương pháp nghiên cứu ................................................................................... 6 5. Phạm vi nghiên cứu ............................................................................................ 6 6. Cấu trúc của đề tài .............................................................................................. 6 1. Cơ sở lý luận ................................................................................................... 6 2. Cơ sở thực tiễn................................................................................................ 6 Phần II. Nội dung: ................................................................................................... 7 1. Cơ sở lý luận......................................................................................................... 7 1. 1. Giới thiệu .................................................................................................... 7 1. 2. Phương pháp quy hoạch động .................................................................... 7 1.2.1. Khái niệm ............................................................................................. 7 1.2.2. Đặc điểm chung của phương pháp quy hoạch động ............................. 9 1.2.3. Các bước giải bài toán bằng quy hoạch động ....................................... 9 1. 3. Cách tiếp cận quy hoạch động .................................................................... 9 1. 4. Lớp các bài toán được giải bằng quy hoạch động ..................................... 9 1. 5. Ưu điểm và hạn chế của quy hoạch động................................................. 10 1.5.1. Ưu điểm............................................................................................... 10 1.5.2. Hạn chế................................................................................................ 10 2. Cơ sở thực tiễn ................................................................................................... 10 2.1. Thực trạng của vấn đề trước khi áp dụng đề tài ........................................ 11 2.1.1. Đặc điểm tình hình .............................................................................. 11 2.1.2. Thực trạng trước khi nghiên cứu ........................................................ 11 2.1.3. Các giải pháp giải quyết vấn đề .......................................................... 12 2.2. Rèn luyện kỹ năng vận dụng phương pháp Quy hoạch động để giải một số bài toán cơ bản đến nâng cao ........................................................................... 12 2.2.1. Bài toán 1. Tìm dãy con không giảm nhiều phần tử nhất ................... 12 2.2.2. Bài toán 2. Dãy con chung dài nhất ................................................... 15 2.2.3. Bài toán 3. dãy con có tổng bằng s ..................................................... 19 2.2.4. Bài toán 4. chia kẹo ............................................................................. 23 3
2.2.5. Bài toán 5: Xếp đồ vật vào ba lô (mỗi vật có số lượng hạn chế)........ 27 2. 3. Hướng dẫn giải một số bài toán bằng quy hoạch động ............................ 32 2.3.1. Bài toán 1. xâu con chung dài nhất ..................................................... 32 2.3.2. Bài toán 2. Cho thuê máy .................................................................... 33 2.3.3. Bài toán 3. Rô bốt ............................................................................... 35 2.4. Một số bài toán áp dụng phương pháp quy hoạch động tự giải ............... 36 2.4.1. Bài 1: Tổng lớn nhất ........................................................................... 36 2.4.2. Bài toán 2: Phân tích ........................................................................... 37 2.4.3. Bài toán 3: Bố trí phòng họp ............................................................... 38 2.4.4. Bài toán 4: Nối điểm ........................................................................... 38 2.4.5. Bài toán 5: Tính tổng của dãy số ........................................................ 39 2.4.6. Bài toán 6: Dãy Con lớn nhất đan dấu ................................................ 40 2.4.7. Bài toán 7: Sắp xếp xâu ...................................................................... 40 2.4.8. Bài toán 8: Tìm mật khẩu.................................................................... 41 2.4.9. Bài toán 9: TWOVALS ...................................................................... 41 2.5. So sánh kết quả trước và sau khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng ........................................................................................... 42 2.5.1. Trước khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng học sinh giỏi .................................................................................................. 42 2.5.2. Sau khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng học sinh giỏi .................................................................................................. 43 Phần III. Kết luận: ................................................................................................ 45 1. Kết Luận ............................................................................................................. 45 1.1 Với mục tiêu đặt ra đề tài đã làm được: .................................................... 45 1.2. Hướng phát triển của đề tài: ..................................................................... 45 2. Một số kiến nghị đề xuất .................................................................................. 46 TÀI LIỆU THAM KHẢO .................................................................................... 47 PHỤ LỤC ............................................................................................................... 48 4
Phần I. Đặt vấn đề 1. Lí do chọn đề tài Tự học tập, nghiên cứu là một nhiệm vụ quan trọng của mỗi giáo viên để nâng cao trình độ chuyên môn, phục vụ cho công tác giảng dạy và đặc biệt là trong bồi dưỡng đội tuyển học sinh giỏi. Trong những năm gần đây, trong các đề thi học sinh giỏi tỉnh, quốc gia cũng như các bài tập trên các trang giải bài trực tuyến vn.spoj.com, vnoi.info, … có nhiều bài tập nếu chúng ta sử dụng những kiến thức cơ bản như đệ quy, duyệt, chia để trị, … có thể giải quyết được nhưng gặp nhiều khó khăn về mặt tốc độ cũng như giới hạn dữ liệu. Trong khi đó nếu chúng ta sử dụng phương pháp quy hoạch động hoặc các phương pháp trên có kết hợp với quy hoạch động thì cho một hiệu quả cao. Quy hoạch động là một phương pháp rất hiệu quả để giải lớp bài toán trong Tin học. Đặc biệt là những bài toán tối ưu, khi sử dụng phương pháp quy hoạch động chương trình chạy nhanh, cách viết chương trình rõ ràng. Nhưng không phải bài toán nào cũng có thể áp dụng được bằng phương pháp quy hoạch động. Vậy thường những bài toán như thế nào thì áp dụng được phương pháp quy hoạch động và cách giải một bài toán quy hoạch động như thế nào là một vấn đề? Mặt khác hiện nay khi bồi dưỡng thi học sinh giỏi giáo viên có thể lựa chọn 1 trong 3 ngôn ngữ lập trình là Pascal, C++ hoặc là Python. Pascal là ngôn ngữ lập trình đã cũ, câu lệnh dài và không được hỗ trợ nhiều. Python là ngôn ngữ lập trình mới nhất, câu lệnh ngắn gọn, hỗ trợ nhiều trong khi viết chương trình. Tuy nhiên một số bài toán khi chạy chương trình còn hạn chế về mặt thời gian. Chính vì vậy hiện nay thi học sinh giỏi thì ngôn ngữ lập trình C++ được lựa chọn nhiều nhất. Cho nên trong đề tài này tôi sử dụng ngôn ngữ lập trình C++ để viết chương trình cũng như minh hoạ thuật toán. Ngoài ra tôi còn minh hoạ chương trình bằng ngôn ngữ lập trình Pascal (Link code minh hoạ bằng ngôn ngữ lập trình pascal để ở phần phụ lục của đề tài) cho một số bạn đọc dễ hiểu và nắm bắt tốt hơn khi chưa tiếp cận nhiều với ngôn ngữ lập trình C++. Vì những lý do trên, với những kinh nghiệm và tìm hiểu của bản thân, tôi đưa ra đề tài “phương pháp quy hoạch động và ứng dụng vào giải một số bài toán bồi dưỡng học sinh giỏi, thi chuyên bằng ngôn ngữ lập trình Pascal và C++” . 2. Mục đích nghiên cứu, đóng góp mới của đề tài - Đề tài nêu ra các định hướng giúp học sinh có thể tiếp cận phương pháp Quy hoạch động để giải một số bài toán tối ưu phù hợp với dữ liệu bài toán. - Giúp người đọc tiếp cận ngôn ngữ lập trình C++ tốt hơn trong khi lập trình. - Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh 5
tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT, thi Olimpic Tin học trẻ hoặc thi vào các trường chuyên. 3. Đối tượng nghiên cứu - Đối tượng nghiên cứu là học sinh giỏi tin, giáo viên giảng dạy, bồi dưỡng học sinh giỏi môn Tin trong trường THCS và THPT. - Phương pháp quy hoạch động và các bài toán tối ưu. 4. Phương pháp nghiên cứu Để hoàn thành nhiệm vụ, tôi đã nghiên cứu rất nhiều sách và các chuyên đề Tin học dành cho học sinh Chuyên tin, những vấn đề cơ bản nhất về cấu trúc dữ liệu, thuật toán và cài đặt chương trình. Cùng nhau trao đổi, thảo luận, rút kinh nghiệm cùng các đồng nghiệp trong và ngoài trường nhằm nâng cao chất lượng cho đề tài. Lựa chọn một số bài toán giải bằng phương pháp Quy hoạch động trong các đề thi và chương trình tin học chuyên THPT. 5. Phạm vi nghiên cứu Lí thuyết về Quy hoạch động và một số bài tập ứng dụng kĩ thuật xử lí Quy hoạch động hiệu quả trong các đề thi học sinh giỏi, các bài tập trên các trang trực tuyến như: vn.spoj.com, vnoi.info, laptrinh.ntu.edu.vn, chuyentin.pro… 6. Cấu trúc của đề tài Ngoài phần mở đầu, kết luận và kiến nghị, phần nội dung đề tài gồm có 2 nội dung: 1. Cơ sở lý luận Giới thiệu về phương pháp Quy hoạch động, các bước tiếp cận với phương pháp Quy hoạch động, cách nhận diện xem bài toán tối ưu nào có thể giải bằng phương pháp Quy hoạch động và nếu giải thì cách giải như thế nào? Trình bày các dạng, phân tích và cài đặt chương trình cụ thể để bạn đọc dễ hiểu nhất. Qua đó có thể vận dụng để giải quyết các bài toán về sau. 2. Cơ sở thực tiễn Nêu ra thực trạng vấn đề, những hạn chế, khó khăn của học sinh cũng như giáo viên trong việc giải quyết các bài toán lớn, các bài toán ôn thi học sinh giỏi hiện nay. Qua đó giải quyết vấn đề và đưa ra các bài toán điển hình để so sánh sử dụng phương pháp Quy hoạch động và một số phương pháp khác. Sử dụng phương pháp Quy hoạch động có thể vận dụng lập trình giải các bài toán trong các đề thi hay khi ôn luyện. Trang bị kiến thức cho học sinh và giáo viên để giải quyết tốt khi gặp các bài toán có liên quan đến sử dụng phương pháp Quy hoạch động một cách hiệu quả nhất. 6
Phần II. Nội dung: 1. Cơ sở lý luận Giới thiệu về phương pháp Quy hoạch động, các bước tiếp cận với phương pháp Quy hoạch động, cách nhận diện xem bài toán tối ưu nào có thể giải bằng phương pháp quy hoạch động và nếu giải thì cách giải như thế nào? Trình bày các dạng, phân tích và cài đặt chương trình cụ thể để bạn đọc dễ hiểu nhất. Qua đó có thể vận dụng để giải quyết các bài toán về sau. 1. 1. Giới thiệu Phương pháp quy hoạch động do nhà toán học người Mỹ Richard Bellman (1920 – 1984) phát minh năm 1953. Phương pháp quy hoạch động (dynamic programming) là một kỹ thuật được áp dụng để giải nhiều lớp bài toán, đặc biệt là bài toán tối ưu. Vậy bài toán tối ưu là gì?. Đó chính là bài toán có nhiều nghiệm chấp nhận được mỗi nghiệm có một giá trị đánh giá. Mục tiêu đặt ra là tìm nghiệm tối ưu, đó là nghiệm có giá trị đánh giá nhỏ nhất hoặc lớn nhất (tối ưu). Khi tiến hành giải một bài toán phức tạp (bài toán lớn) ban đầu người ta thường đi chia bài toán đó thành các bài toán con độc lập đơn giản để giải, khi tiến hành giải xong các bài toán con ta tổng hợp lời của các bài toán con và đó chính là bài toán lớn cần giải. Đây chính là phương pháp chia để trị được sử dụng rất thông dụng trong quá trình lập trình giải các bài toán trong Tin học. Nhưng đối với những bài toán phức tạp nếu chúng ta sử dụng phương pháp này thì sẽ mất test ở những dữ liệu lớn. Vì chưa tối ưu về mặt thời gian. Chính vì vậy phương pháp Quy hoạch động ra đời nhằm cải tiến về vấn đề này. 1. 2. Phương pháp quy hoạch động 1.2.1. Khái niệm Phương pháp quy hoạch động là một kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu toàn bộ hay một phần kết quả tính toán của mỗi bước trước đó với mục đích sử dụng lại (Công thức truy hồi là công thức thể hiện quan hệ giữa các bước trong một bài toán và kết quả của các bước sau thường dựa vào kết quả của các bước trước đó. Kết quả của bước cuối cùng chính là kết quả bài toán cần tìm). Vậy bản chất của quy hoạch động =Chia để trị+Mảng (Lưu lại kết quả) Phương pháp quy hoạch động sử dụng nguyên lý bottom - up, nghĩa là “ đi từ dưới lên”. Đầu tiên ta phải giải các bài toán con đơn giản nhất, có thể tìm ngay ra nghiệm. Sau đó kết hợp các bài toán con này lại để tìm lời giải cho bài toán lớn hơn và cứ như thế cho đến khi giải được bài toán yêu cầu. với phương pháp này mỗi bài toán con sau khi giải xong đều được lưu trữ lại và đem ra sử dụng nếu cần. Khi đó sẽ tiết kiệm được bộ nhớ và thời gian thực hiện. 7
Ngược lại phương pháp đệ quy giải quyết bài toán theo hướng top – down, nghĩa là để giải bài toán ban đầu, ta phải đi giải các bài toán con của nó. Đây là một phương pháp hay, tuy nhiên phương pháp này sẽ gặp một số hạn chế về mặt thời gian , tốc độ do phải tính toán nhiều lần một số bài toán con giống nhau nào đó. Để thấy rõ hơn ta đi tìm hiểu ví dụ sau: Xét ví dụ 1: dãy Fibonacci là dãy số nguyên sau: F0= 1, F1= 1, Fn = Fn-1+Fn-2 với mọi n>=2 Hãy tính F5 Cách 1 Cách 2 #include #include #include #include int f(int n) main() { { int t; int i,f[10]; if (n
Như vậy để tính được f(5) máy tính phải thực hiện mất 1 lần f(4), 2 lần f(3), 3 lần f(2), 2 lần f(1). Nhưng cách 2 thì không như vậy nó tính f(1), f(2) từ đó tính f(3), và tính được f(4), f(5). Khi đó mỗi giá trị chỉ phải tính một lần và cần lấy f[i] nào thì lấy ra. 1.2.2. Đặc điểm chung của phương pháp quy hoạch động - 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 bài toán lớn hơn cho tới khi giải được bài toán lớn nhất là bài toán ban đầu. - Quy hoạch động cần có bảng phương án: chính là không gian lưu trữ lời giải các bài toán con để tìm cách phối hợp chúng, đây là bảng phương án của quy hoạch động. Thường kết quả cuối cùng của bảng phương án chính là kết quả của bài toán cần tìm. 1.2.3. Các bước giải bài toán bằng quy hoạch động Bước 1: Giải tất các bài toán cơ sở (thường là dễ nhất). lưu các lời giải vào bảng phương án. Đây là điều kiện dừng của bài toán Bước 2: Xây dựng công thức truy hồi : bằng cách phối hợp những lời giải của bài toán nhỏ hơn đã lưu trong bảng phương án để tìm lời giải của bài toán lớn hơn (công thức truy hồi) và lưu vào bảng phương án, nhờ có công thức truy hồi này ta tính được bảng phương án. Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. Đây chính là kết quả của bài toán. 1. 3. Cách tiếp cận quy hoạch động Quy hoạch động thường dùng một trong 2 cách tiếp cận sau : - Tiếp cận từ dưới lên (Bottom up) Là phương pháp đi từ cái riêng đến cái chung, từ các thành phần ở mức cao tới các đối tượng thành phần ở mức thấp, từ mức đơn vị chương trình tới mức tổng thể. - Tiếp cận từ trên xuống ( Top down) Là phương pháp phân rã vấn đề có hệ thống từ trên xuống. Cách tiếp cận từ dưới lên hiệu quả hơn từ trên xuống nên cách tiếp cận từ dưới lên được sử dụng nhiều hơn. 1. 4. Lớp các bài toán được giải bằng quy hoạch động Nhưng không phải bài toán tối ưu nào cũng giải được bằng phương pháp quy hoạch động. Thường những bài toán có đặc điểm sau: - Khi bài toán có tính chất truy hồi. 9
- Bài toán lớn phải phân rã được thành nhiều bài toán con, mà sự phối hợp lời giải của các bài toán con đó cho ta lời giải của bài toán lớn. - Có thể lưu trữ nghiệm của các bài toán con dưới một hình thức nào đó để phối hợp tìm nghiệm của bài toán lớn. - Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn bước. - Kích thước của bài toán lớn. 1. 5. Ưu điểm và hạn chế của quy hoạch động 1.5.1. Ưu điểm - Qua phân tích ở ví dụ 1 ta thấy được ưu điểm của quy hoạch động là tiết kiệm được thời gian thực hiện vì không cần phải tính đi tính lại nhiều lần một số bài toán con giống nhau. - Ngoài ra lời giải của bài toán sử dụng quy hoạch động thường gắn gọn, sáng sủa, có tính chất lời giải cao. 1.5.2. Hạn chế - Việc tìm công thức truy hồi không phải dễ tìm. Để tìm được đòi hỏi sự phân tích tổng hợp rất công phu, khó nhận ra được như thế nào là chính xác nên mất nhiều thời gian để suy nghĩ. - Khi lưu bảng lưu trữ đòi hỏi mảng hai chiều, ba chiều…thì khó có thể xử lý dữ liệu với kích thước cỡ mỗi chiều lớn đến hàng trăm. Và còn bị hạn chế về bộ nhớ vì ta phải lưu trữ nghiệm của các bài toán con. - Không phải lúc nào kết hợp lời giải các bài toán con cũng được kết quả của bài toán lớn mà ta còn phải biết sử dụng và phối hợp uyển chuyển nhiều thuật toán, không được lạm dụng hay coi thường bất cứ một phương pháp nào. - Có những bài toán không thể giải được bằng quy hoạch động. 2. Cơ sở thực tiễn Nêu ra thực trạng vấn đề, những hạn chế, khó khăn của học sinh cũng như giáo viên trong việc giải quyết các bài toán lớn, các bài toán ôn thi học sinh giỏi hiện nay. Qua đó giải quyết vấn đề và đưa ra các bài toán điển hình để so sánh sử dụng phương pháp Quy hoạch động và một số phương pháp khác. Sử dụng phương pháp Quy hoạch động có thể vận dụng lập trình giải các bài toán trong các đề thi hay khi ôn luyện. Trang bị kiến thức cho học sinh và giáo viên để giải quyết tốt khi gặp các bài toán có liên quan đến sử dụng phương pháp Quy hoạch động một cách hiệu quả nhất. 10
2.1. Thực trạng của vấn đề trước khi áp dụng đề tài 2.1.1. Đặc điểm tình hình * Thuận lợi: - Với sự bùng nổ của ngành công nghệ thông tin cũng như chương trình giáo dục phổ thông 2018 các em học sinh, phụ huynh ngày càng quan tâm hơn. - Ngày nay số lượng học sinh có máy tính cá nhân ngày càng nhiều, các em có điều kiện để học tập, nghiên cứu và lập trình được nhiều hơn. - Các cuộc thi lập trình này ngày càng tổ chức nhiều hơn, việc học, xem tài lệu cũng dễ dàng hơn, có thể xem các tài liệu trên web cũng như các kênh như youtube…. * Khó khăn: - Do môn Tin học chưa có trong tổ hợp môn thi tốt nghiệp và đại học nên các em và phụ huynh chưa quan tâm đến nên việc chọn học sinh giỏi cũng như các em chưa thực sự đầu tư chuyên sâu vào lập trình. - Những kiến thức trong chương trình Tin học phổ thông còn hạn chế, hoặc chưa đủ đáp ứng cho việc giải một số bài toán trong các kỳ thi học sinh giỏi Tỉnh khi có yêu cầu dữ liệu lớn cùng thời gian thực hiện ngắn. - Các tài liệu tổng hợp các cách để giải quyết các bài toán yêu cầu cao như vậy chưa có nhiều để học sinh tham khảo, ôn luyện. 2.1.2. Thực trạng trước khi nghiên cứu Ngày nay công nghệ thông tin là một trong những ngành hót, nhân lực còn thiếu, mỗi năm sinh viên ra trường chưa đáp ứng đủ yêu cầu thị trường, mức thu nhập nghành công nghệ thông tin là khá cao, nên việc quan tâm của các em ngày càng nhiều, nhất là trong các cuộc thi lập trình. Năm học này thì trường đại học và khoa học công nghệ Hà Nội đã có 9 ngành cho học sinh đăng kí thi tổ hợp môn: Toán , Lý, Tin Với sự phát triển nhanh về tốc độ cũng như sự quan tâm đến của nghành công nghệ thông tin ngày càng cao thì đề thi học sinh giỏi Tin học cũng đòi hỏi ngày càng nâng cao hơn. Trong các đề thi học giỏi thì người ta quan tâm về thời gian thực hiện và độ lớn của dữ liệu đầu vào. Đa số giáo viên gặp khó khăn trong việc hướng dẫn học sinh giải bài toán thế nào để đạt được trọn vẹn yêu cầu của bài toán. Đối với những bài toán phức tạp và có dữ liệu lớn thì giáo viên và học sinh còn gặp khó khăn, chưa giải quyết vấn đề một cách triệt để. Dẫn đến sẽ mất test. Chương trình chưa tối ưu chỉ ăn test với dữ liệu nhỏ. 11
2.1.3. Các giải pháp giải quyết vấn đề Có những bài toán nhiều khi có vẻ đơn giản, đa số học sinh có thể giải được nhưng khi thực hiện với dữ liệu lớn thì không đáp ứng được thời gian yêu cầu hoặc không thể thực hiện được tất cả các test yêu cầu. Lúc này đòi hỏi phải tìm được thuật toán tối ưu nhất. Đa số khi chấm bài, dùng test chấm mới biết được chương trình đáp ứng được bao nhiêu test so với yêu cầu của đề ra. Điều này chỉ thực hiện được khi ôn luyện cho các em, còn khi các em đi thi thì không tự ước lượng được bài làm đạt kết quả thế nào. Thuật toán Quy hoạch động không gì khác hơn là một sự tối ưu hóa của các kỹ thuật. Nó làm giảm sự phức tạp về thời gian bằng cách sử dụng một số loại thứ tự thay vì nhất thiết phải sắp xếp dữ liệu. Qua đó giúp chương trình chạy nhanh hơn, không gian lưu trữ ít hơn. Hiện nay trong các kì thi học sinh giỏi và thi vào trường chuyên, đề thi thường có những bài toán mà sử dụng phương pháp Quy hoạch động để giải quyết vấn đề mới tối ưu. Chính vì vậy giáo viên và học sinh nắm rõ phương pháp Quy hoạch động là một lợi thế rất lớn khi lập trình giải những bài toán phức tạp và dữ liệu lớn. Như vậy sẽ đạt kết quả cao hơn trong các kì thi học sinh giỏi nói chung và thi vào trường chuyên nói riêng Và trong đề tài này tôi đã trình bày các kiến thức và kĩ năng từ đó vận dụng phương pháp Quy hoạch động để xử lý những bài toán như vậy. Sau khi đọc hiểu về mặt lý thuyết thì người đọc có thể thực hành làm những bài tập điển hình có code, có hướng dẫn. Qua đó sẽ tự tin hơn, tư duy và kỹ năng tốt hơn, nắm rõ và có thể vận dụng để lập trình giải những bài toán cùng dạng sau này. 2.2. Rèn luyện kỹ năng vận dụng phương pháp Quy hoạch động để giải một số bài toán cơ bản đến nâng cao 2.2.1. Bài toán 1. Tìm dãy con không giảm nhiều phần tử nhất Cho dãy số nguyên có n phần tử a1, a2, ..., an . 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 không giảm. Ví dụ: dãy 1, 4, 10, 11, 12 là một dãy con không giảm của 1, 4, 10, 9, 8, 17, 11, 7, 12, 6. * 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 vào: từ file văn bản DAYCON.INP gồm 2 dòng: - Dòng đầu tiên ghi số N (0
* Kết quả: ghi ra file văn bản DAYCON.OUT gồm 2 dòng: - Số max là độ dài dãy con không giảm dài nhất tìm được - Chỉ số xuất hiện của các số hạng của dãy con trong dãy đã cho. * Ví dụ: DAYCON.INP DAYCON.OUT 10 5 6 5 8 12 6 9 7 13 2 13 6 8 12 13 13 *Cách giải: Gọi l[i] là độ dài dãy con không giảm dài nhất, các phần tử lấy trong miền từ an đến ai và phần tử bắt đầu là a[i] (i=n, n-1,..., 0). Bài toán sử dụng thêm 2 phần tử: a[0]= -32768 và a[n+1]=32767 chắc chắn thuộc dãy con không giảm dài nhất. Khi đó độ dài dãy con không giảm dài nhất bắt đầu từ a[n+1] là 1, dãy bắt đầu từ a[i], ..., a[n+1]; Bước 1: Giải các bài toán cơ sở và lưu vào bảng phương án L[n+1]=1; với a[n+1]=32767 nên chắc chắn thuộc dãy con không giảm dài nhất. Bước 2: Tìm công thức truy hồi Khi xét tới phần tử a[i] thì a[i] phải nối vào đầu 1 dãy con không giảm mà bắt đầu phần tử a[j] nào đó phải thõa mãn a[i]=a[i] thì ta phải chọn jmax để dãy con không giảm bắt đầu từ a[jmax] dài nhất. Nên công thức truy hồi của bài toán là: L[i]=max{l[j] | j=i+1,..., n+1 thõa mãn a[i]
Đoạn code tính l[i] như sau: l[n+1]=1; t[n+1]=n+1; for (int i=n;i>=0;i--) { jmax=n+1; for (int j=i+1;j>n; a[0]=-32768; a[n+1]=32767; for (int i=1;i>a[i]; } void qhd() { int jmax; 14
l[n+1]=1; t[n+1]=n+1; for (int i=n;i>=0;i--) { jmax=n+1; for (int j=i+1;j
* Dữ liệu ra: file văn bản DAYCC.OUT gồm: - Dòng 1 ghi số K là số lượng các số hạng của dãy con chung c (nếu không có dãy con chung ghi số 0 ) - Trong K dòng tiếp theo, dòng thứ i (i= 1, 2…, K) ghi hai số X, Y với ý nghĩa là: Số hạng thứ i của dãy c là số hạng thứ X của dãy a và số hạng thứ Y của dãy b. * Ví dụ: DAYCC.INP DAYCC.OUT 7 6 4 3513553 75 153531 64 43 22 *Cách giải: Gọi l[i,j] là độ dài dãy con chung dài nhất khi xét tới phần tử a[i] (i=0,...,n) và phần tử b[j] (j=0,...,m). Khi đó L[n,m] là độ dài dãy con chung dài nhất của an và bm. Bước 1: Giải các bài toán cơ sở và lưu vào bảng phương án L[0,j]=0; dãy a không có phần tử nào, dãy b có j phần tử (j=0,...,m). Nên không có dãy con chung. L[i,0]=0; dãy b không có phần tử nào, dãy a có i phần tử (i=0,...,n). Nên không có dãy con chung. Bước 2: Tìm công thức truy hồi Khi xét tới l[i,j] (tức xét tới a[i] và b[j]) thì có hai khả năng: Khả năng 1: a[i]=b[j] khi đó độ dài dãy con chung được tăng lên một đơn vị L[i,j]=l[i-1,j-1]+1 (i=0,...,n; j=0,...,m) Khả năng 2: a[i] ≠ b[j] khi đó độ dài dãy con chung sẽ phụ thuộc giá trị của l[i,j-1] và l[i-1,j]. Do độ dài dãy con chung lớn nhất nên ta lấy max của chúng L[i,j]=max(l[i-1,j],[i,j-1]) (i=0,...,n; j=0,...,m) Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. * Bảng phương án: dựa vào bài toán cơ sở và công thức truy hồi ở trên ta áp dụng cho ví dụ trên nên có bảng sau: 16
Xét ví dụ trên ta có bảng phương án: L[i,j] 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 2 0 0 1 1 2 2 2 3 0 1 1 1 2 2 3 4 0 1 1 2 2 3 3 5 0 1 2 2 3 3 3 6 0 1 2 2 3 3 3 7 0 1 2 3 3 4 4 Đoạn code tính L[i,j]: for(int i=0;i
Chương trình hoàn chỉnh #include #include using namespace std; ifstream fi("DAYCC.INP "); ofstream fo("DAYCC.OUT "); int n,m,l[100][100],a[100],b[100],c[100]; void nhap() { fi>>n>>m; for (int i=1;i>a[i]; for (int j=1;j>b[j]; } void qhd() { for(int i=0;i
i--; j--; } else if (l[i][j]==l[i-1][j]) i--; else j--; } } int main() { nhap(); qhd(); truyvet(); } 2.2.3. Bài toán 3. dãy con có tổng bằng s Cho dãy a1, a2,…, an. Tìm một dãy con có tổng bằng S. * Dữ liệu vào: từ file văn bản TONGS.INP gồm 2 dòng: - Dòng đầu tiên là 2 số N, S (N
Bước 2: Tìm công thức truy hồi Khi xét tới T[i,j] tức là xét tới phần tử a[i] và khối lượng lúc này là j, ta có 2 khả năng: Khả năng 1: phần tử a[i] sẽ được cộng vào tổng (tức lúc đó nếu chọn phần tử a[i] vào thì tổng vẫn=j). Khi đó giá trị T[i,j] là tổng giá trị lớn nhất có thể chọn các phần tử {1, 2,...,i-1} với giới hạn trọng lượng j. T[i,j]:=T[i-1,j]; Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. * Tính bảng phương án dựa vào kết quả của bài toán cơ sở và công thức truy hồi ở trên ta áp dụng cho ví dụ của bài thu được bảng sau: Xét ví dụ trên ta có bảng phương án: T[i,j] 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 2 0 1 1 1 1 1 1 1 1 1 1 11 12 3 0 1 2 3 3 3 3 3 3 3 3 3 3 4 0 1 2 3 4 5 6 7 7 7 7 7 7 5 0 1 2 3 4 5 6 7 8 9 10 11 12 Code để tính T[i,j]: for(int i=0;i
else t[i][j]=t[i-1][j]; * Độ phức tạp của thuật toán: Với đoạn code trên thì dễ thấy chi phí không gian cài đặt trên là O(ns), chi phí thời gian là O(ns). Với n là số phần tử của dãy a, s là tổng s. * Truy vết tìm kết quả: Theo bài thì ta sẽ lấy một giá trị T[i,s]=s bất kỳ, từ đó truy vết ra các phần tử mà có tổng cộng lại bằng s. truy vết cụ thể trong chương trình hoàn chỉnh dưới. Chương trình hoàn chỉnh #include #include using namespace std; ifstream fi ("TONGS.INP"); ofstream fo ("TONGS.OUT"); int a[100],n,s,t[100][100]; void nhap() { int i; fi>>n>>s; for(i=1;i>a[i]; fi.close(); } void qhd() { for(int i=0;i