Sáng kiến kinh nghiệm THPT: Sử dụng phương pháp quy hoạch động để giải một số bài toán có tính truy hồi trong ngôn ngữ lập trình C++

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

Thêm vào BST

Báo xấu

42
lượt xem 9
download

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

Mục đích nghiên cứu sáng kiến "Sử dụng phương pháp quy hoạch động để giải một số bài toán có tính truy hồi trong ngôn ngữ lập trình C++" nhằm giúp học sinh đứng trước 1 bài toán, xác định được là bài toán đó có thể áp dụng được quy hoạch động không và cách giải cụ thể như thế nào, đánh giá, so sánh được thời gian thực hiện chương trình (độ phức tạp của thuật toán). Cách nhận diện và lập công thức quy hoạch động

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: Sử dụng phương pháp quy hoạch động để giải một số bài toán có tính truy hồi trong ngôn ngữ lập trình C++

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN Đơn vị: Trƣờng THPT Phan Đăng Lƣu SÁNG KIẾN KINH NGHIỆM Đề tài: SỬ DỤNG PHƢƠNG PHÁP QUY HOẠCH ĐỘNG ĐỂ GIẢI MỘT SỐ BÀI TOÁN CÓ TÍNH TRUY HỒI TRONG NGÔN NGỮ LẬP TRÌNH C++ Môn/Lĩnh vực: Tin học Ngƣời thực hiện: Nguyễn Thị Thƣơng Hồ Văn Chiến Tổ: Toán - Tin Điện thoại: 0976607114 - 0979783682 Có đính kèm: Mô hình Phần mềm Phim ảnh Hiện vật khác Năm học: 2021 - 2022
MỤC LỤC Phần I. ĐẶT VẤN ĐỀ ............................................................................................... 1 1. Lý do chọn đề tài .................................................................................................. 1 2. Mục tiêu, nhiệm vụ của đề tài............................................................................... 1 3. Đối tƣợng nghiên cứu ........................................................................................... 1 4. Phƣơng pháp nghiên cứu ..................................................................................... 2 Phần II. NỘI DUNG NGHIÊN CỨU ...................................................................... 2 1.Cơ sở lý luận .......................................................................................................... 2 2. Thực trạng vấn đề nghiên cứu .............................................................................. 2 3. Nội dung vấn đề nghiên cứu ................................................................................. 3 3.1. Tên chủ đề ...................................................................................................... 3 3.2. Cơ sở lý thuyết ................................................................................................ 3 3.2.1. Khái niệm về phƣơng pháp quy hoạch động ............................................. 3 3.2.2. Các bƣớc giải bài toán quy hoạch động .................................................... 3 3.2.3. Biện pháp lựa chọn và cài đặt chƣơng trình. ............................................. 4 3.3. Các bài tập áp dụng ......................................................................................... 7 3.3.1. Dạng bài toán về dãy con liên tiếp ........................................................... 7 3.3.2. Dạng bài toán về dãy con không liên tiếp ................................................. 10 3.3.3. Dạng bài toán Dãy con có tổng bằng S. .................................................... 18 3.3.4. Dạng bài toán Biến đổi xâu ....................................................................... 22 3.3.5. Dạng bài toán Ghép cặp ............................................................................ 30 Phần III. KẾT LUẬN VÀ KIẾN NGHỊ .................................................................. 36 3.1. Kết luận ........................................................................................................... 36 3.2. Kiến nghị ......................................................................................................... 36 TÀI LIỆU THAM KHẢO ........................................................................................ 37
Phần I. ĐẶT VẤN ĐỀ: 1. Lý do chọn đề tài: Chúng ta thấy Tin Học đƣợc ứng dụng vào hầu hết tất cả các lĩnh vực của cuộc sống và đã đóng vai trò rất lớn trong sự phát triển của xã hội. Thấy đƣợc tầm quan trọng của Tin học, thế giới nói chung và Việt Nam nói riêng đã có những đầu tƣ lớn cho lĩnh vực này. Đặc biệt trong giáo dục nâng cao dân trí về Tin Học và đào tạo nguồn nhân lực có chất lƣợng cao. Phụ huynh và các thế hệ học sinh sau này cũng đã bắt đầu chú trọng và đã chọn các nghành nghề liên quan đến công nghệ thông tin nhiều hơn. Tuy nhiên trong hệ thống giáo dục nƣớc ta hiện nay môn Tin học chƣa đƣợc quan tâm đúng với tầm quan trọng của nó. Tin Học đang bị xem là môn phụ trong trƣờng học dẫn đến học sinh ít đầu tƣ cho môn học này, gây ra không ít khó khăn cho giáo viên trong nhà trƣờng và đặc biệt chọn đội ngũ học sinh giỏi. Mặt khác môn Tin học có đặc thù riêng, học sinh giỏi đi thi chủ yếu chấm bài tự động trên phần mềm themis nên phụ thuộc lớn vào thời gian thực hiện (thời gian chạy) chƣơng trình và giới hạn độ lớn dữ liệu mà bài toán yêu cầu. Vì vậy lập trình ngoài việc chú ý đến giới hạn dữ liệu bài toán thì cần lựa chọn thuật toán tối ƣu để đảm bảo yêu cầu bài toán đặt ra. Vì vậy để giải bài toán trong Tin Học thƣờng phải xác định đƣợc: - Bài toán thuộc lớp nào. - Sử dụng phƣơng pháp tối ƣu nào để giải nó. Trong quá trình nghiên cứu và bồi dƣỡng học sinh giỏi chúng tôi gặp khá nhiều bài toán về dãy con và bài toán xử lí xâu. Đây là một nội dung khá phổ biến trong các đề thi học sinh giỏi và là một nội dung khá khó. Với mong muốn tìm ra các giải pháp tối ƣu cho các bài toán này, chúng tôi mạnh dạn trình bày sáng kiến kinh nghiệm: SỬ DỤNG PHƢƠNG PHÁP QUY HOẠCH ĐỘNG ĐỂ GIẢI MỘT SỐ BÀI TOÁN CÓ TÍNH TRUY HỒI TRONG NGÔN NGỮ LẬP TRÌNH C++ 2. Mục tiêu, nhiệm vụ của đề tài: Nhằm giúp học sinh đứng trƣớc 1 bài toán, xác định đƣợc là bài toán đó có thể áp dụng đƣợc quy hoạch động không và cách giải cụ thể nhƣ thế nào, đánh giá, so sánh đƣợc thời gian thực hiện chƣơng trình (độ phức tạp của thuật toán). Cách nhận diện và lập công thức quy hoạch động 3. Đối tƣợng nghiên cứu: Sử dụng phƣơng pháp quy hoạch động để giải một số bài toán có tính truy hồi trong C++ nhƣ: Tìm dãy con; đếm dãy con; Tính tổng dãy con; và các bài toán liên quan đến xâu nhƣ tìm xâu con chung dài nhất và biến đổi xâu. 1
4. Phƣơng pháp nghiên cứu: Để trình bày sáng kiến kinh nghiệm này chúng tôi sử dụng kết hợp nhiều phƣơng pháp nhƣ: Nghiên cứu tài liệu, nghiên cứu theo chuyên đề, thực nghiệm, so sánh, phân tích kết quả thực nghiệm, ý kiến đóng góp của đồng nghiệp trong thực tiễn giảng dạy Phần II. NỘI DUNG NGHIÊN CỨU: 1. Cơ sở lý luận: Sự phát triển nhƣ vũ bão của Tin học và những đóng góp lớn của Tin học trong sự phát triển xã hội không thể phủ nhận đƣợc, đặc biệt trong dịp dịch Covid 19 vai trò của Tin học đã đƣợc khẳng định, mọi ngƣời dân nói chung và phụ huynh học sinh nói riêng đã nhìn thấy đƣợc vai trò quan trọng của Tin học trong mọi lĩnh vực kinh tế, văn hóa và giáo dục. Chắc chắn mọi ngƣời đã có cái nhìn nhận khác và thấy môn Tin Học rất quan trọng. Xã hội phát triển, đòi hỏi Tin học cũng phát triển để đáp ứng nhu cầu của xã hội. Để đáp ứng những đòi hỏi của sự phát triển đó phải có kế hoạch đào tạo bồi dƣỡng những cá nhân có niềm say mê và có năng khiếu trong lĩnh vực tin học và trang bị vốn kiến thức cơ sở vững chắc, giúp cho mục tiêu đi trƣớc đón đầu, rút ngắn khoảng cách về trình độ tin học giữa nƣớc ta và thế giới. Trong quá trình nghiên cứu, giảng dạy, chúng ta gặp rất nhiều các bài tập toán tin. Các bài tập dạng này rất phong phú và đa dạng. Thực tế chƣa có thuật toán hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên ngƣời ta đã tìm ra một số thuật toán chung nhƣ: tham lam, quay lui, quy hoạch động, các giải thuật trên đồ thị... Các thuật toán này có thể áp dụng để giải một lớp khá rộng các bài toán hay gặp trong thực tế. Trong quá trình ôn thi học sinh giỏi của trƣờng, việc truyền đạt các kiến thức về một số thuật toán nhƣ: quay lui, quy hoạch động, tham lam, các giải thuật trên đồ thị… là rất cần thiết cho học sinh để phát triển tƣ duy và lập trình giải các bài toán tin học. Tạo lập và củng cố lòng say mê tìm hiểu và khám phá cho học sinh khi giải các bài toán tin. Trong quá trình dạy bồi dƣỡng chúng tôi nhận thấy, nếu học sinh thực hiện tốt việc lựa chọn và cài đặt chƣơng trình tối ƣu khi giải các bài tập về dãy con và các bài tập xử lí xâu nói riêng và các bài tập lập trình nói chung thì chất lƣợng học sinh giỏi sẽ đƣợc nâng cao. 2. Thực trạng vấn đề nghiên cứu: Thực trạng dạy học môn Tin học trong trƣờng phổ thông Phan Đăng Lƣu hiện nay: Hiện nay nhu cầu xã hội đang cần rất nhiều kĩ sƣ Công Nghệ Thông tin và lao động có trình độ cao. Tuy nhiên việc đào và bồi dƣơng học sinh yêu thích môn tin học ở các trƣờng phổ thông gặp rất nhiều khó khăn. 2
- Môn Tin học vẫn đang bị xem là môn “phụ”, không tham gia thi tốt nghiệp hay đại học cao đẳng vì thế môn Tin Học chƣa nhận đƣợc sự quan tâm của nhà trƣờng cũng nhƣ phụ huynh và học sinh. Mặt khác, để lập trình đòi hỏi học sinh phải có một kiến thức cơ bản tốt, phải có khả năng về tƣ duy và đam mê. Vì vậy động viên và tuyển chọn đƣợc các em vào đội tuyển học sinh giỏi môn tin học ở trƣờng rất khó Trong thực trạng đó chúng tôi muốn tìm hiểu, nghiên cứu, và truyền những kinh nghiệm, hiểu biết của mình để truyền lại đam mê cho những học sinh ham thích môn Tin học. 3. Nội dung vấn đề nghiên cứu: 3.1. Tên chủ đề: SỬ DỤNG PHƢƠNG PHÁP QUY HOẠCH ĐỘNG ĐỂ GIẢI MỘT SỐ BÀI TOÁN CÓ TÍNH TRUY HỒI TRONG NGÔN NGỮ LẬP TRÌNH C++ 3.2. Cơ sở lý thuyết: 3.2.1. Khái niệm về phương pháp quy hoạch động: Các thuật toán đệ quy có ƣu điểm dễ cài đặt, tuy nhiên do bản chất của quá trình đệ quy, các chƣơng trình này thƣờng kéo theo những đòi hỏi lớn về không gian bộ nhớ và một khối lƣợng tính toán khổng lồ, nên một thuật toán hiệu quả là cực kỳ cần thiết. 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 đƣợc lựa chọn nhiều nhất. Quy hoạch động (Dynamic programming) 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 trữ toàn bộ hay một phần kết quả tính toán tại mỗi bước với mục đích sử dụng lại. Bản chất của quy hoạch động là thay thế mô hình tính toán “từ trên xuống” (Top-down) bằng mô hình tính toán “từ dưới lên” (Bottom-up). Từ “programming” ở đây không liên quan gì tới việc lập trình cho máy tính, đó là một thuật ngữ mà các nhà toán học hay dùng để chỉ ra các bƣớc chung trong việc giải quyết một dạng bài toán hay một lớp các vấn đề. Không có một thuật toán tổng quát để giải tất cả các bài toán quy hoạch động. Mục đích của phần này là cung cấp một cách tiếp cận mới trong việc giải quyết các bài toán tối ƣu mang bản chất đệ quy, đồng thời đƣa ra các ví dụ từ dễ đến khó để học sinh có thể làm quen và hình thành các kỹ năng trong việc tiếp cận các bài toán quy hoạch động. 3.2.2. Các bước giải bài toán quy hoạch động: Có 4 bƣớc để giải 1 bài toán bằng quy hoạch động: Bước 1: Xây dựng hàm mục tiêu: 3
Á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ùng dạng có kích thƣớc nhỏ hơn, sao cho việc giải quyết các bài toán con một cấp phụ thuộc vào kết quả của các bài toán con trƣớc đó. Bước 2: Xác định 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: Căn cứ vào ý nghĩa hàm mục tiêu, tìm mối liên 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 nó. Lời giải đƣợc lƣu vào mảng 1 chiều hoặc mảng 2 chiều (gọi là bảng phƣơng án) Bước 4: Dựa vào bảng phƣơng án, truy vết để tìm phƣơng án tối ƣu. 3.2.3. Biện pháp lựa chọn và cài đặt chương trình: Khi nào thì dùng thuật toán quy hoạch động: Phƣơng pháp quy hoạch động dùng để giải bài toán tối ƣu có bản chất đệ quy, tức là việc tìm phƣơng án tối ƣu cho bài toán đó có thể đƣa về tìm phƣơng án tối ƣu của một số hữu hạn các bài toán con. Đối với nhiều thuật toán đệ quy chúng ta đã tìm hiểu, nguyên lý chia để trị (divide and conquer) thƣờng đóng vai trò chủ đạo trong việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó làm nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phƣơng pháp quy hoạch động, nguyên lý này càng đƣợc thể hiện rõ: Khi không biết cần phải giải quyết những bài toán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lƣu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn. Đó chính là điểm khác nhau giữa Quy hoạch động và phép phân giải đệ quy và cũng là nội dung phƣơng pháp quy hoạch động. Phép phân giải đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đƣa về phép phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải tiếp bài toán nhỏ hơn đó bất kể nó đã đƣợc giải hay chƣa. 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). Nhận thấy:  Trƣớc khi áp dụng phƣơng pháp quy hoạch động ta phải xét xem phƣơng pháp đó có thoả mãn những yêu cầu dƣới đây hay không:  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 4
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.  Vì quy hoạch động là đi giải tất cả các bài toán con, nên nếu không đủ không gian vật lý lƣu trữ lời giải (bộ nhớ, đĩa…) để phối hợp chúng thì phƣơng pháp quy hoạch động cũng không thể thực hiện đƣợc.  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. Cài đặt chƣơng trình: Các bƣớc cài đặt một chƣơng trình bằng phƣơng pháp quy hoạch động Bước 1. Giải tất cả các bài toán cơ sở (thông thƣờng rất dễ), lƣu các lời giải vào bảng phƣơng án. Bước 2. Dùng công thức truy hồi phối hợp những lời giải của những bài toán nhỏ đã lƣu trong bảng phƣơng án để tìm lời giải của những bài toán lớn hơn và lƣu chúng vào bảng phƣơng án. Cho tới khi bài toán ban đầu tìm đƣợc lời giải. Bước 3. Dựa vào bảng phƣơng án, truy vết tìm ra nghiệm tối ƣu. Các hƣớng thực hiện quy hoạch động: - Quy hoạch động ngƣợc: Phƣơng pháp quy hoạch động ngƣợc là phƣơng pháp đƣợc sử dụng rộng rãi, vì nó khá tƣơng ứng với suy nghĩ tự nhiên của chúng ta. Chúng ta đọc đề bài, suy nghĩ cách giải cho nó. Cách giải đó yêu cầu phải giải những bài toán nhỏ hơn, nhƣ kiểu làm toán ngày phải chứng minh các bổ đề vậy. Chúng ta tiếp tục suy nghĩ cho những bài toán con này, rồi tổng hợp để tìm ra lời giải cho bài toán lớn. Quá trình cứ tiếp tục nhƣ vậy, và quy hoạch động kiểu “ngƣợc” này đang đƣợc xây dựng đúng nhƣ vậy. Ngoài ra, về mặt lập trình, kiểu quy hoạch động này có mối quan hệ tƣơng đối gần gũi với đệ quy. Một bài toán lớn đƣợc giải dựa vào các bài toán con tƣơng tự nhau (và tƣơng tự bài toán lớn) thì việc áp dụng đệ quy có thể là một phƣơng pháp dễ dàng để code. Vì vậy, nhiều trƣờng hợp, có thể coi quy hoạch động là một cách để tối ƣu phƣơng pháp đệ quy để giải một bài toán. Ví dụ: Xâu con chung dài nhất Cho hai xâu ký tự. Tìm độ dài xâu con chung nhỏ nhất giữa chúng. Ví dụ với 2 xâu "quetzalcoatl" và "tezcatlipoca" thì xâu con chung dài nhất sẽ là "ezaloa" với độ dài 6. Với bài toán này, chúng ta sẽ lần lƣợt giải các bài toán con nhƣ sau: Lấy i ký tự đầu tiên từ xâu thứ nhất và j ký tự đầu tiên từ xâu thứ hai và tìm độ dài xâu chung dài nhất giữa 2 xâu con đƣợc lấy ra đó. Dễ dàng thấy đƣợc rằng, lời giải của mỗi bài toán con sẽ phụ thuộc vào i và j, L(i, j). Và bài toán lớn sẽ đƣợc 5
giải bằng cách lần lƣợt giải các bài toán con lần lƣợt từ L(0, 0) và tăng dần độ dài xâu đƣợc lấy ra cho đến khi chúng ta lấy ra toàn bộ xâu của đề bài. Chúng ta hãy bắt đầu lần lƣợt các bài toán con. Đƣơng nhiên, nếu một trong hai xâu là rỗng thì xâu con chung của chúng cũng rỗng. Vậy L(0, j) = L(i, 0) = 0. Nếu cả i và j đều dƣơng, chúng ta cần suy xét một vài trƣờng hợp. 1. Nếu ký tự cuối cùng của xâu thứ nhất không có mặt trong xâu con chung dài nhất, nó có thể bị bỏ qua mà không ảnh hƣởng gì đến kết quả. Công thức ở đây sẽ là L(i, j) = L(i - 1, j). 2. Tƣơng tự nhƣ trƣờng hợp trên, ký tự cuối cùng của xâu thứ hai không ảnh hƣởng đến kết quả thì L(i, j) = L(i, j - 1). 3. Trƣờng hợp cuối cùng, nếu hai ký tự cuối cùng của hai xâu x1, x2 đều có mặt trong xâu con chung dài nhất. Dĩ nhiên là hai ký tự này phải là một thì điều này mới xảy ra, tức là x1 == x2. Trong trƣờng hợp này, khi xoá đi bất cứ một ký tự nào trong hai ký tự đó đều khiến xâu con chung dài nhất ngắn đi 1 ký tự. Vậy rõ ràng là L(i, j) = L(i - 1, j - 1) + 1. Trong cả ba trƣờng hợp trên, chúng ta phải chọn ra trƣờng hợp nào cho kết quả là xâu con chung dài nhất (với bài toán này thì chỉ cần đƣa ra độ dài đó là đủ). - Quy hoạch động xuôi: Ngoài kiểu quy hoạch động ngƣợc này, có một kiểu quy hoạch động “xuôi”. Tuy không phổ biến, kiểu quy hoạch động xuôi cũng khá khó áp dụng, nhƣng quy hoạch động “xuôi” mang đến cho chúng ta nhiều tiện lợi. Kiểu xuôi này cũng cần duyệt qua các bài toán con từ nhỏ đến lớn, nhƣng với mỗi bài toán con, chúng ta tính toán kết quả và từ đó tìm cách thực hiện một số phép tính để giải bài toán lớn hơn. Nghĩa là, với mỗi bài toán con, chúng ta sẽ nhìn về phía trƣớc để xem phải giải bài toán tiếp theo nhƣ thế này từ bài toán hiện tại. Phƣơng pháp này khó áp dụng hơn phƣơng pháp ngƣợc kia, và cũng không phải bài toán nào cũng áp dụng đƣợc. Với mỗi bài toán, việc xác định bƣớc tiếp theo tƣơng đối khó khăn, thậm chí việc kiểm tra tính đúng sai của phƣơng pháp cũng không hề dễ dàng. Nhƣ chúng ta đã thấy ở những phần trƣớc, thông thƣờng, mỗi bài toán cần phải giải bằng cách tổng hợp kết quả từ một vài bài toán con trƣớc đó. Vì vậy, cách quy hoạch động xuôi này chỉ sử dụng một bài toán con để tính toán trƣớc bài toán tiếp theo sẽ chỉ cho ra một phần của kết quả chứ không phải kết quả cuối cùng. Vì vậy, để thực hiện quy hoạch động xuôi, việc điền sẵn một mảng các giá trị trung tính là điều bắt buộc (sau đó chúng ta sẽ cộng dồn kết quả vào mỗi khi giải đƣợc một bài toán con mới). Ví dụ: Xâu con chung dài nhất: Với bài toán này, chúng ta có thể chọn giá trị trung tính là một số âm. Chúng ta sẽ tìm cách quy hoạch động xuôi nhƣ sau: 6
 L(0,0) = 0 là bài toán với hai xâu rỗng  Với mỗi bài toán L(i, j) chúng ta sẽ tìm cách tính toán kết quả cho các bài toán lớn hơn. Lúc này, có 3 hƣớng phát triển tiếp: 1. Lấy thêm một ký tự từ xâu thứ nhất => Kết quả không thay đổi. 2. Lấy thêm một ký tự từ xâu thứ hai => Kết quả cũng không thay đổi. 3. Nếu ký tự tiếp theo của cả hai xâu giống nhau => Lấy tự từ này và độ dài xâu con chung tăng lên 1. 3.3. Các bài tập áp dụng: 3.3.1. Dạng bài toán về dãy con liên tiếp: Mô hình: Bài toán điển hình: Cho dãy a1,a2,..an (1
Tính L[i] : Phần tử đang đƣợc xét là a[i] .Ta tìm đến phần tử a[i-1]< a[i] có L[i- 1]. Khi đó nếu bổ sung a[i] vào sau dãy con a[1]...a[i-1] ta sẽ đƣợc dãy con tăng dần dài nhất xét từ a[1]...a[i]. Kết quả: độ dài lớn nhất của dãy liên tiếp = giá trị lớn nhất của mảng L. Độ phức tạp của thuật toán này là o(n) Cài đặt: 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]. Chƣơng trình tính các giá trị của mảng L nhƣ sau: #include using namespace std; #define N int(1e6+1) int a[N],L[N],n; int main() { freopen("DOANCON1.INP","r",stdin); freopen("DOANCON1.OUT","w",stdout); cin >> n; int res=0; for (int i = 1; i > a[i]; L[1]=1; for (int i = 2; i
 N dòng tiếp theo, mỗi dòng chứa một số nguyên là các phần tử của a. Dữ liệu ra: Ghi vào file CAU1.OUT một số nguyên dƣơng duy nhất là độ dài của dãy con liên tiếp dài nhất tìm đƣợc. Ví dụ: CAU1.INP CAU1.OUT 7 4 -1 1 2 1 2 2 5 Bài này giải bằng phƣơng pháp quy hoạch động: * Công thức: + Xây dựng hàm mục tiêu: L[i] là độ dài của đoạn con liên tiếp không giảm kết thúc tại a[i]. Độ dài đoạn con liên tiếp không giảm dài nhất là: max(L[]) + Bài toán cơ sở: L[1] =1; + Xét a[i] (2≤i≤n): - Nếu a[i-1] ≤ a[i] thì L[i] = L[i-1] +1 (độ dài đoạn con liên tiếp không giảm sẽ nối thêm 1 đơn vị) - Nếu a[i-1] >a[i] thì L[i] =1; (phần tử đầu cho dãy không giảm mới) * Cài đặt chƣơng trình: #include #define N 10001 int a[N], f[N]; int n, res=0; using namespace std; int main() { freopen("cau1.inp", "r", stdin); freopen("cau1.out", "w", stdout); 9
cin>>n; for(int i=1; i>a[i]; L[1]=1; for(int i=2; i= a[i-1]) L[i] =L[i-1] +1; else L[i]=1; res= max(res, L[i]); } cout
Cách 1: Công thức:  Phân rã bài toán: Ta bổ sung 2 phần tử “lính canh” là a[0]= -∞ vào đầu dãy và a[n+1] = +∞ vào cuối dãy. Khi đó dãy con đơn điệu tăng dài nhất chắc chắn sẽ bắt đầu từ a[0] và kết thúc tại a[n]+1. → Tổng quát: Cần tìm độ dài của dãy con tăng dài nhất từ a[i] →a[n+1]  Xây dựng hàm mục tiêu: - Gọi L[i] là độ dài của dãy con tăng dài nhất bắt đầu tại a[i] với (0≤i≤n+1) - Suy ra kết quả của bài toán là: L[n+1] - 2  Bài toán cơ sở: Ta dễ dàng thấy đƣợc L[n+1] =1; (Dãy con bắt đầu từ a[n+1] = -∞, dãy con này gồm 1 phần tử là -∞ nên L[n+1]=1.  Xây dựng công thức: - Xét a[i]: Nếu a[i] L[jmax] thì: 11
{ jmax=j; L[i]=L[jmax] +1; T[i] = jmax; // Lƣu vết vào mảng T } int i=T[0]; while( i != n+1) //Chừng nào chƣa duyệt đến aN+1 { Thông báo chọn a[i]; i=T[i]; } Ví dụ: với A = (7, 4, 5, 8, 6, 7, 10, 9, 11, 8). Hai mảng L và T sau khi tính sẽ là: i 0 1 2 3 4 5 6 7 8 9 10 11 a[i] -∞ 7 4 5 8 6 7 10 9 11 8 +∞ L[i] 8 5 7 6 4 5 4 3 3 2 2 1 T[i] 2 4 3 5 7 6 7 9 9 11 11 Truy vết Độ phức tạp của thuât toán O(n2) Cài đặt chƣơng trình: #include #define inf int(1e9) #define N 1000 using namespace std; int a[N+2], L[N+2], T[N+2]; int n, jmax; int main() { freopen("lis.inp", "r", stdin); freopen("lis.out", "w", stdout); 12
cin>>n; for(int i=1; i>a[i]; a[0] =-inf; a[n+1] =inf; L[n+1]=1; for(int i=n; i>=0; i--) { jmax= n+1; for(int j=i+1; ja[i] && L[j] >L[jmax]) jmax=j; L[i]=L[jmax] +1; T[i] = jmax; //Lưu vết vào mảng T } cout
 Xây dựng công thức: - Xét a[i]: Nếu a[j]
i 0 1 2 3 4 5 6 7 8 9 10 11 a[i] -∞ 7 4 5 8 6 7 10 9 11 8 +∞ L[i] 1 2 2 3 4 4 5 6 6 7 6 8 T[i] 0 0 2 3 3 5 6 6 7 6 9 Truy vết Cài đặt chƣơng trình: #include #define N 1000 #define inf int(1e9) using namespace std; int a[N+2], L[N+2], T[N+2]; vector x; int n; int main() { freopen("lis.inp","r",stdin); freopen("lis.out","w",stdout); cin >> n; for (int i=1; i> a[i]; a[0] = -inf; a[n+1] = inf; L[0] = 1; L[1] = 2; for (int i=2; i
for (int i=x.size() - 1; i>0; i--) cout
- Có 20 số test ứng với 0 < n ≤ 20 - Có 20 số test ứng với 20 < n ≤ 5000 - Có 60 số test ứng với 5000 < n ≤ 105 * Công thức: + Xây dựng hàm mục tiêu: L[i] là thể tích lớn nhất của chiếc bánh xếp chồng kết thúc tại a[i]. + Bài toán cơ sở: L[0] = -inf; L[1] = v[1]; + Công thƣc: L[i] = max(L[j]) +v[i] * Cài đặt chƣơng trình: #include #define N int(1e5) #define inf int(1e9) #define ll long long using namespace std; ll n, r[N+2], h[N+2]; double s[N+2], v[N+2], L[N+2]; int main() { freopen("bcake.inp","r",stdin); freopen("bcake.out","w",stdout); cin>>n; for(int i=1;i> r[i]>>h[i]; v[i] = M_PI * r[i] * r[i] * h[i]; } v[0]=-inf; v[n+1] = inf; L[0] = -inf; L[1] = v[1]; for (int i=2; i
return 0; } Bài này giải bằng phƣơng pháp quy hoạch động + cấu trúc dữ liệu. Tuy nhiên Trong phần này tôi sử dụng quy hoạch động. Để full substak 3 thì phải kết hợp sử dụng cấu trúc dữ liệu. 3.3.3. Dạng bài toán Dãy con có tổng bằng S: Mô hình: Bài toán điển hình: Cho dãy gồm n số nguyên dƣơng a1, a2, …, an và một giá trị S. Hãy chọn ra trong dãy một dãy con (không nhất thiết liên tiếp) có tổng bằng S. Input: SUMS.INP - Dòng 1 chứa số nguyên dƣơng n và S (1 ≤ n ≤ 100, 1 ≤ S ≤ 10000) - Dòng 2 chứa n số nguyên dƣơng a1, a2, …, an (1 ≤ ai ≤ 100) Output: SUMS.OUT - Nếu có thể chọn ra đƣợc dãy con có tổng bằng S thì: + Dòng đầu ghi thông báo: “YES” + Dòng thứ hai đƣa ra dãy các vị trí của dãy con có tổng bằng S - Ngƣợc lại thì thông báo “NO” Ví dụ: SUMS.INP SUMS.OUT 5 11 YES 12435 235  Cách giải và tìm hƣớng giải quyết tối ƣu cho bài toán: Ta phân rã bài toán thành bài toán con: Tìm dãy con từ a[1] → a[i] có tổng bằng t. - Gọi L[i][t] =1 nếu tồn tại dãy con từ a[0] →a[i] có tổng bằng t. - Gọi L[i][t] =0 nếu không tồn tại dãy con từ a[0] →a[i] có tổng bằng t.  Ta có thể tính L[i][t] theo công thức: L[i][t] = 1 (tạo đƣợc tổng t) nếu:L[i-1][t] =1 hoặc L[i-1][t-a[i]] = 1 L[i][t] = L[i-1][t] (nếu không tạo đƣợc tổng t)  Nhận xét: Nếu ta sử dụng công thức trên luôn thì cần sử dụng bảng phương án 2 chiều. Ta nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i-1. Ta có thể cải tiến là sử dụng bảng phương án là mảng một chiều L[0..S], để giảm kích thước 18