Sáng kiến kinh nghiệm THPT: Sử dụng Quy hoạch động trong việc lập trình giải một số bài toán để bồi dưỡng học sinh giỏi bằng Ngôn ngữ Python

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

Thêm vào BST

Báo xấu

1
lượt xem 0
download

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

Sáng kiến "Sử dụng Quy hoạch động trong việc lập trình giải một số bài toán để bồi dưỡng học sinh giỏi bằng Ngôn ngữ Python" được hoàn thành với mục tiêu nhằm giúp học sinh giỏi tiếp cận ngôn ngữ lập trình Python đáp ứng với chương trình mới Giáo dục phổ thông 2018.

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 Quy hoạch động trong việc lập trình giải một số bài toán để bồi dưỡng học sinh giỏi bằng Ngôn ngữ Python

Së gi¸o dôc vµ ®µo t¹o nghÖ an ---    --- SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI: SỬ DỤNG QUY HOẠCH ĐỘNG TRONG VIỆC LẬP TRÌNH GIẢI MỘT SỐ BÀI TOÁN ĐỂ BỒI DƯỠNG HỌC SINH GIỎI BẰNG NGÔN NGỮ PYTHON Lĩnh vực: Tin học NĂM HỌC 2023-2024
Së gi¸o dôc vµ ®µo t¹o nghÖ an trƯêng trung häc phæ th«ng cöa lß ---    --- SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI: SỬ DỤNG QUY HOẠCH ĐỘNG TRONG VIỆC LẬP TRÌNH GIẢI MỘT SỐ BÀI TOÁN ĐỂ BỒI DƯỠNG HỌC SINH GIỎI BẰNG NGÔN NGỮ PYTHON Lĩnh vực: Tin học Người thực hiện: Nguyễn Thị Thanh Vân Tổ bộ môn: Toán – Tin Đơn vị: Trường THPT Cửa Lò Số điện thoại: 0982027669 Email: vanntt.c3cualo@nghean.edu.vn NĂM HỌC 2023-2024
MỤC LỤC NỘI DUNG Trang PHẦN I - ĐẶT VẤN ĐỀ 1 I - Lý do chọn đề tài. 1 II – Mục đích nghiên cứu. 2 III - Đối tượng, thời gian nghiên cứu. 2 IV - Phương pháp nghiên cứu 2 V – Tính mới, cấp thiết, cải tiến đóng góp của đề tài. 2 PHẦN II - NỘI DUNG NGHIÊN CỨU. 3 I – CƠ SỞ LÝ LUẬN 3 1. Lý luận về chương trình giáo dục phổ thông 2018 3 2. Lý luận về tầm quan trọng của việc bồi dưỡng học sinh giỏi 4 3. Lý luận về việc lựa chọn ngôn ngữ Python trong việc bồi dưỡng học sinh giỏi môn Tin học 4 4. Lý luận về độ phức tạp của thuật toán 4 II – CƠ SỞ THỰC TIỄN 5 1. Thực trạng trước khi thực hiện giải pháp của sáng kiến 5 2. Thực trạng về công tác bồi dưỡng học sinh giỏi môn Tin học ở trường Trung học phổ thông. 5 III – GIẢI PHÁP VỀ VẤN ĐỀ NGHIÊN CỨU 6 1. Khái niệm về Quy hoạch động 6 2. Các nguyên tắc Quy hoạch động 6 3. Các bước giải bài toán bằng Quy hoạch động 6 4. Nhận dạng bài toán về Quy hoạch động 7 5. Sử dụng Quy hoạch động lập trình giải một số bài toán học sinh giỏi bằng Ngôn ngữ Python 7 6. Các dạng toán Quy hoạch động điển hình 28 6.1 Dãy các phần tử dài nhất thoả mãn bài toán 28
6.2 Dạng bài toán cái túi và ứng dụng 33 6.3 Biến đổi xâu 35 6.4 Ghép cặp 39 6.5 Quy hoạch động vị trí cấu hình 41 IV. KHẢO SÁT TÍNH CẤP THIẾT VÀ TÍNH KHẢ THI CỦA GIẢI PHÁP ĐỀ XUẤT 44 V. THỰC NGHIỆM GIẢI PHÁP 49 VI- HIỆU QUẢ CỦA ĐỀ TÀI 49 PHẦN III. PHẦN KẾT LUẬN 51 I – KẾT LUẬN 51 II – KIẾN NGHỊ VÀ PHÁT TRIỂN 51
PHẦN I. ĐẶT VẤN ĐỀ I. LÝ DO CHỌN ĐỀ TÀI Nhiệm vụ trọng tâm của năm học 2023- 2024 với chủ đề “Tiếp tục đổi mới quản lý và nâng cao chất lượng giáo dục” tích cực đổi mới kiểm tra, đánh giá thúc đẩy đổi mới phương pháp dạy và học theo chuẩn kiến thức, kỹ năng và năng lực của chương trình giáo dục phổ thông 2018. Đẩy mạnh hơn nữa việc ứng dụng công nghệ thông tin trong dạy học và công tác quản lí chuyên môn nhằm phát huy tính tích cực, chủ động, tự lực, sáng tạo của học sinh, vận dụng kiến thức, kỹ năng vào giải quyết các vấn đề thực tiễn góp phần phát triển năng lực học sinh. Cần tìm ra những giải pháp, những kinh nghiệm tích luỹ được trong quá trình học tập, giảng dạy và bồi dưỡng học sinh giỏi để phục vụ việc học tập của học sinh ngày càng tốt hơn. Tin học là một môn học được ứng dụng nhiều trong hầu hết tất cả các lĩnh vực và đã góp phần quan trọng việc thúc đẩy sự phát triển kinh tế, xã hội, khoa học kỹ thuật…Tin học đã làm cho xã hội có nhiều nhận thức mới về cách tổ chức các hoạt động. Nhiều quốc gia trên thế giới ý thức rất rõ tầm quan trọng của Tin học và 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. Bản thân tôi nhận thấy, là một giáo viên Tin học cần truyền cho các em học sinh những kiến thức cơ bản về Tin học ứng dụng và khoa học máy tính. Đặc biệt góp phần định hướng những học sinh có năng lực và đam mê Tin học vào đội ngũ nhân lực Công nghệ thông tin chất lượng cao của đất nước. Môn Tin học tạo ra một thế hệ mới có tư duy về phần giải thuật và lập trình đóng vai trò rất quan trọng trong chương trình Tin học ở bậc Trung học phổ thông hiện nay. Năm học 2022-2023 và 2023-2024, đa số các trường Trung học phổ thông sử dụng ngôn ngữ lập trình C++ để bồi dưỡng học sinh giỏi nhưng riêng trường tôi đã triển khai chủ động dạy Ngôn ngữ Python cho đội tuyển. Để giải quyết những bài toán Tin một cách nhanh chóng, dễ dàng hơn. Khi học sinh đi thi học sinh giỏi thì trong lập trình cần quan tâm đến tối ưu của thuật toán. Thuật toán tối ưu là thuật toán có độ phức tạp ít nhất, thời gian chạy nhanh nhất. Mặt khác, trong các bài thi học sinh giỏi yêu cầu một test chạy tối đa không quá 1 giây. Các bài toán với dữ liệu lớn thông thường từ 104 trở lên học sinh phải biết cách thiết kế thuật toán sao cho có độ phức tạp O(n) hoặc O(logn) mới có kết quả như mong muốn. Để giải quyết vấn đề này, tôi đã tuyền lửa cho học sinh đam mê lập trình có giải pháp tốt nhất đem lại hiệu quả cao nhất, đó là sử dụng phương pháp quy hoạch động. Qua nhiều năm bồi dưỡng học sinh giỏi đều đạt kết quả cao tại kỳ thi học sinh giỏi cấp Tinh, tôi đúc rút ra kinh nghiệm đưa ra đề tài: “Sử dụng Quy hoạch động trong việc lập trình giải một số bài toán để bồi dưỡng học sinh giỏi bằng Ngôn ngữ Python”, với mong muốn phần nào giúp học sinh cũng như giáo viên có tài liệu tham khảo phục vu ̣cho việc học tập và giảng dạy, đặc biệt trong công tác bồi dưỡng học sinh giỏi cấp Trung học phổ thông. 1
II. MỤC ĐÍCH NGHIÊN CỨU Trong quá trình nghiên cứu và giảng dạy, tôi nhận thấy việc vận dụng các kiến thức về quy hoạch động vào việc giải một số bài toán rất hiệu quả. Vì vậy, tôi viết đề tài này với mục đích: - Thứ nhất, trao đổi cùng với các đồng nghiệp về việc vận dụng phương pháp Quy hoạch động trong việc lập trình giải một số bài toán. - Thứ hai, là tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng học sinh giỏi cấp Tỉnh môn Tin học. III. ĐỐI TƯỢNG NGHIÊN CỨU - Chương trình giáo dục phổ thông 2018. - Phương pháp quy hoạch động - Ngôn ngữ lập trình Ngôn ngữ Python - Cấu trúc đề thi học sinh giỏi Tỉnh môn Tin học tỉnh Nghệ An. - Đối tượng học sinh giỏi khối 11, 12. IV. PHƯƠNG PHÁP NGHIÊN CỨU Kết hợp nhiều phương pháp nghiên cứu: nghiên cứu lý thuyết, nghiên cứu thực tiễn dạy học, phân tích, tổng hợp, điều tra, thực nghiệm qua việc bồi dưỡng học sinh giỏi cấp Tỉnh. V. TÍNH MỚI, CẤP THIẾT, CẢI TIẾN, ĐÓNG GÓP MỚI CỦA ĐỀ TÀI - Tính mới: Giúp học sinh giỏi tiếp cận ngôn ngữ lập trình Python đáp ứng với chương trình mới Giáo dục phổ thông 2018. - Tính cấp thiết: Học sinh đội tuyển học sinh giỏi cần vận dụng linh hoạt phương pháp quy hoạch động vào giải quyết một số bài toán một cách nhanh chóng, đơn giản với độ phức tạp ít nhất để bài thi đạt điểm tối đa. - Tính cải tiến: Đề tài đã đưa ra phương pháp quy hoạch động và hệ thống bài tập thích hợp, lô gic, khoa học nhằm giúp học sinh đam rnê luyện kỹ năng lập trình, phát triển tư duy và biết áp dụng Tin học vào thực tiễn. Lâu nay, giáo viên thường sử dụng ngôn ngữ C++ để lập trình nhưng tôi đã mạnh dạn cải tiến chuyển sang ngôn ngữ Python là một ngôn ngữ mới để giải quyết một số bài toán bồi dưỡng đội tuyển học sinh giỏi. - Tính đóng góp của đề tài: Giúp học sinh và giáo viên có tài liệu tham khảo phục vu cho việc học tập và giảng dạy, đặc biệt trong công tác bồi dưỡng học sinh giỏi ̣ cấp Tỉnh. 2
PHẦN II. NỘI DUNG NGHIÊN CỨU I. CƠ SỞ LÝ LUẬN 1. Lý luận về Chương trình giáo dục phổ thông 2018. Chương trình Giáo dục phổ thông 2018 theo định hướng phát triển phẩm chất và năng lực người học thông qua nội dung giáo dục với những kiến thức và kỹ năng cơ bản, thiết thực mà hiện đại; chú trọng thực hành vận dụng kiến thức, kỹ năng đã học để giải quyết các vấn đề trong học tập và đời sống thông qua các phương pháp, hình thức tổ chức dạy học phát huy tính chủ động và sáng tạo của mỗi học sinh. Giúp em các hình thành và phát triển những năng lực tổng hợp như: ngôn ngữ, tính toán, khoa học, công nghệ, thẩm mĩ, thể chất và đặc biệt là năng lực tin học. Trong bối cảnh hiện nay, ngành giáo dục đã và đang từng bước thực hiện chương trình giáo dục phổ thông mới. Từng cá nhân giáo viên đang từng bước đưa thế hệ học trò hội nhập môi trường công nghệ 4.0 bằng cách vận dụng công nghệ số vào quá trình dạy học. Tuy nhiên, việc không linh hoạt chúng có thể dẫn đến nhàm chán hoặc lựa chọn công cụ chưa phù hợp cũng không mang lại hiệu quả cao. Là môn học đi đầu trong ngành mũi nhọn, đảm bảo vừa nâng cao chất lượng dạy học, giáo dục đáp ứng yêu cầu nhiệm vụ chương trình Giáo dục phổ thông 2018; vừa giúp cho người học có được tâm thế, hành trang số sẵn sàng thay đổi, linh hoạt và sáng tạo công cuộc đổi mới, hội nhập Quốc tế. Chương trình môn Tin học ở cấp Trung học phổ thông giúp học sinh củng cố và nâng cao năng lực tin học đã được hình thành, phát triển ở giai đoạn giáo dục cơ bản, đồng thời cung cấp cho học sinh tri thức mang tính định hướng nghề nghiệp thuộc lĩnh vực tin học hoặc ứng dụng tin học, cụ thể là: - Giúp học sinh có những hiểu biết cơ bản về hệ thống máy tính, một số kĩ thuật thiết kế thuật toán, tổ chức dữ liệu và lập trình; củng cố và phát triển hơn nữa cho học sinh tư duy giải quyết vấn đề, khả năng đưa ra ý tưởng và chuyển giao nhiệm vụ cho máy tính thực hiện theo thiết kế của mình. - Giúp học sinh có khả năng hoà nhập và thích ứng được với sự phát triển của xã hội số, ứng dụng công nghệ thông tin và truyền thông trong học và tự học; tìm kiếm và trao đổi thông tin theo cách phù hợp, tuân thủ pháp luật, có đạo đức, ứng xử văn hoá và có trách nhiệm; có hiểu biết thêm một số ngành nghề thuộc lĩnh vực tin học, chủ động và tự tin trong việc định hướng nghề nghiệp tương lai của mình. - Giúp học sinh có khả năng ứng dụng Tin học tạo ra sản phẩm số phục vụ cộng đồng và nâng cao hiệu quả công việc; có khả năng lựa chọn, sử dụng, kết nối các thiết bị số, dịch vụ mạng và truyền thông, phần mềm và các tài nguyên số khác. 3
2. Lý luận về tầm quan trọng của việc bồi dưỡng học sinh giỏi Việc bồi dưỡng học sinh giỏi, đào tạo nguồn nhân tài cho đất nước là một nhiệm vụ rất quan trọng và cần thiết vì những người tài bao giờ cũng là nhân tố quan trọng để thúc đẩy xã hội phát triển. Đã từ lâu công tác bồi dưỡng học sinh giỏi là nhiệm vụ trọng tâm của các trường Trung học phổ thông. Vì vậy các Nhà trường đặc biệt quan tâm và tất cả giáo viên đều có nhiệm vụ tham gia bồi dưỡng học sinh giỏi. Tổ chức bồi dưỡng học sinh giỏi và thi học sinh giỏi nhằm: Động viên khích lệ những học sinh và giáo viên trong dạy và học, góp phần thúc đẩy việc cải tiến, nâng cao chất luợng giáo dục. Phát hiện học sinh có năng khiếu về Tin học để tiếp tục bồi dưỡng và định hướng nghề nghiệp đúng sở thích, sở trường, nhằm tạo nguồn nhân lực, nhân tài chất lượng cao cho đất nước. 3. Lý luận về việc lựa chọn ngôn ngữ Python trong việc bồi đưỡng học sinh giỏi môn Tin học. Trong quy định của các kỳ thi học sinh giỏi môn Tin học, thí sinh có thể lập trình bằng ngôn ngữ C++ (trên DevC++, Code Block), Python để giải các bài toán. Trong hai ngôn ngữ lập trình này, Python là ngôn ngữ mới được đưa vào dạy học trong chương trình phổ thông 2018 nên được lựa chọn hàng đầu vì nó có những điểm mạnh sau: - Python được thiết kế với ưu điểm mạnh là dễ đọc, dễ học và dễ nhớ. Python là ngôn ngữ có hình thức rất sáng sủa, cấu trúc rõ ràng, thuận tiện cho người mới học lập trình và là ngôn ngữ lập trình dễ học; được dùng rộng rãi trong phát triển trí tuệ nhân tạo. Cấu trúc của Python còn cho phép người sử dụng viết mã lệnh với số lần gõ phím tối thiểu. Python hoàn toàn tạo kiểu động và dùng cơ chế cấp phát bộ nhớ tự động; Python luôn được xếp hạng vào những ngôn ngữ lập trình phổ biến nhất. Đây là một tiêu chí mới cực kỳ quan trọng trong lập trình thi đấu cũng như trong các kỳ thi học sinh giỏi các cấp. Ngôn ngữ Python xu thế phát triển, làm việc rất hiệu quả và tiện lợi. 4. Lý luận về độ phức tạp của thuật toán Nói về độ phức tạp của thuật toán thì ta quan tâm tới hai yếu tố: độ lớn của kiểu dữ liệu và thời gian chạy chương trình. Độ phức tạp thuật toán ta quan tâm đến thời gian hơn.Thuật toán tối ưu thì phải có thời gian thực hiện ngắn và tiết kiệm tài nguyên máy tính. Sự hao phí tài nguyên máy tính liên quan đến phần cứng máy tính. Vì vậy những thuật toán đưa ra thường lấy thời gian để tính độ phức tạp hơn là tài nguyên (vì mỗi máy tính khác nhau về tài nguyên). Do đó độ phức tạp của thuật toán là thời gian thực hiện thuật toán. Kí hiệu độ phức tạp là O lớn. Trong khi thi học sinh giỏi, thường mỗi test có thời gian chấm 1 giây (1s). Trong 1s thông thường máy tính làm được khoảng 4.108 phép tính. Chính vì vậy khi đọc 4
giới hạn của đề bài thì ta sẽ biết làm bài đó với độ phức tạp bao nhiêu để được điểm tối đa. Đánh giá độ phức tạp thuật toán là cực kỳ quan trọng trong thi cử. Nếu đánh giá sai độ phức tạp thuật toán dẫn đến bài mình làm thì mình không tự chấm được chính xác bao nhiêu điểm (nếu như code đúng). Ví dụ: nếu cách làm là O(n) thì bài đó mình có thể làm được với n
ủng hộ. Chính những khó khăn đó luôn tạo áp lực cho giáo viên khi tham gia dạy bồi dưỡng học sinh giỏi. Vì vậy ảnh hưởng không nhỏ đến kết quả, chất lượng học sinh giỏi môn Tin học ở các trường Trung học phổ thông. Giáo viên trực tiếp bồi dưỡng đội tuyển đều phải tự tìm tòi, tự soạn chương trình để dạy vì tài liệu về bộ môn Tin học chưa nhiều. Hệ thống bài tập liên quan đến bồi dưỡng học sinh giỏi còn ít. Tàì liệu ôn thi đội tuyển thật sự khó tìm để phù hợp với học sinh và giáo viên. Quan trọng nhất là sau khi làm bài thi thì nhiều học sinh và giáo viên không hiểu khi làm bài vẫn chạy cho kết quả đúng nhưng điểm thi lại thấp. Do đó, trong quá trình dạy bồi dưỡng học sinh giỏi, giáo viên cần trao đổi kinh nghiệm, trao đổi chia sẻ nội dung, phương pháp, kỹ thuật dạy học với các đồng nghiệp trong toàn ngành giáo dục để nâng cao chất lượng, hiệu quả của công tác bồi dưỡng học sinh giỏi. III. GIẢI PHÁP VỀ VẤN ĐỀ NGHIÊN CỨU Việc nắm vững về phương pháp Quy hoạch động là điều rất quan trọng, đó là cơ sở để các em học sinh vận dụng và giải quyết các bài toán với dữ liệu lớn. Sau đây, tôi xin trình bày một số kiến thức về phương pháp Quy hoạch động và hệ thống các bài tập mà tôi đã tìm hiểu, vận dụng có hiệu quả cao trong quá trình giảng dạy và bồi dưỡng học sinh giỏi. 1. Khái niệm về Quy hoạch động 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). Nói cách khác, Quy hoạch động là lớp các bài toán mà quyết định ở bước thứ i phụ thuộc vào quyết định ở các bước đã xử lý trước đó. 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. 2. Các nguyên tắc Quy hoạch động + Bài toán lớn cần được chia thành các bài toán nhỏ hơn về kích thước. + Với bài toán có tính chất tối ưu cần thiết lập cấu trúc con tối ưu, hay bài toán cần thoả mãn nguyên lý tối ưu địa phương. + Khi giải bài toán bằng quy hoạch động cần thiết lập bảng lưu trữ các giá trị trung gian, đây là nguyên tắc nhớ cục bộ của công thức đệ quy tối ưu. 3. Các bước giải bài toán bằng Quy hoạch động Giải bài toán Quy hoạch động có 4 bước: 6
Bước 1: Xác định hàm mục tiêu: Áp dụng nguyên lý tối ưu của ta xây dựng hàm mục tiêu F(i) là kết quả của bước thứ i. Bước 2: Xây dựng bài toán cơ sở và công thức truy hồi: + 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. + Sau khi xây dựng bài toán cơ sở, ta sẽ tiến hành tìm công thức truy hồi của bài toán thứ i dựa trên kết quả của các bài toán trước đó. Bước 3: 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 4: Kết luận: + Tìm ra nghiệm của bài toán. 4. Nhận dạng các bài toán về Quy hoạch động Một bài toán Quy hoạch động phải thoả mãn có thể sử dụng lời giải ở các trạng thái thấp hơn để tìm lời giải cho các trạng thái cao hơn và cuối cùng là lời giải tối ưu cho cả hai bài toán. Trước khi áp dụng Quy hoạch động ta phải xem phương pháp đó có thoả mãn những yêu cầu sau: - Bài toán lớn phải phân rã được thành nhiều bài toán con và 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. - Khi sử dụng Quy hoạch động thì cần đủ không gian vật lý lưu trữ (dung lượng bộ nhớ…) vì phương pháp này giải tất cả các bài toán con của nó. 5. Sử dụng Quy hoạch động vào lập trình giải một số bài toán học sinh giỏi bằng ngôn ngữ Python. Bài 1. Trong một dây chuyền làm việc của công ty có N công nhân làm N việc. Người ta đánh số cho công nhân từ 1 đến N theo thứ tự đứng trông dây chuyền. Thời gian hoàn thành một công việc của người thứ i là ti phút. Mỗi người cần làm xong công việc của mình nhưng được quyền làm tối đa 2 công việc. Vì thế họ sẽ phối hợp người đứng ngay trước mình cùng làm, nếu người thứ i và người thứ i+1 phối hợp thì thời gian làm xong việc cho hai người là pi . Tìm phương án sao cho N công việc đều hoàn thành với thời gian ít nhất. Dữ liệu vào: từ file bai1.inp * Dòng thứ nhất ghi số N (1 < N
* Dòng thứ 3 ghi N-1 số thời gian cùng làm tương ứng cho số cặp công nhân nếu phối hợp p1, p2, .., pN-1 (1
Bài 2. Cần chuyền hết n gói tin trên một mạng gồm m kênh truyền. Biết chi phí chuyền i gói tin trên kênh j là C(i,j) (1
Kết quả = min(f[n][j]) (1
Bài 3. Cho số nguyên dương N và dãy a gồm N số nguyên a1, a2, …, an có giá trị tuyệt đối không quá 103. Dãy không giảm là dãy số có số hạng trước không lớn hớn số hạng sau: Yêu cầu: Hãy lập trình tìm dãy con liên tiếp không giảm dài nhất trông dãy a. Dữ liệu vào: Đọc từ file bai3.inp: • Dòng đầu tiên chứa số nguyên dương N (2
Bài 4. Có một số gạch để lát nền nhà có hai màu trắng và vàng với kích thước lần lượt là 1x2 và 2x1. Yêu cầu: Hãy cho biết với hai màu gạch như trên thì ta có bao nhiêu cách để lát nền nhà có kích thước là 2 x n (1
- dp[2] = 2 – có 2 cách lát nền kích thước 2 x 2 bằng hai viên gạch kích thước 2x1 hoặc hai viên gạch kích thước 1 x 2 Xét hàng gạch thứ i của nền gạch kích thước 2x i. - Nếu đặt viên kích thước 2 x 1 vào bảng gạch thứ i. Khi đó số cách lát: dp[i] = dp[i-1] - Nếu đặt viên gạch kích thước 1x2 vào hàng gạch thứ i. Khi đó số cách lát: dp[i] = dp[i-2] Suy ra tổng số cách lát nền là: dp[i] = dp[i-1] + dp[i-2] Vì n
Ví dụ: bai5.inp bai5.out adceba 9 Giới hạn: - Có 1/3 test có độ dài xâu S không quá 104 - Có 2/3 test còn lại không có ràng buộc gì thêm. *Thuật toán đề xuất: sử dụng Quy hoạch động Xét từ được kết thúc bởi ký tự s[i]: - Nếu s[i] là nguyên âm: res() cộng thêm số phụ âm có bên trái s[i] - Nếu s[i] là phụ âm: res1 cộng thêm số nguyên âm ở bên trái s[i] Kết quả cuối cùng = res() + res1. Để không mất thời gian tìm số lượng nguyên âm và số lượng phụ âm ở bên trái s[i] cần chuẩn bị trước một mảng cnt[0][i] = số lượng nguyên âm ở bên trái s[i] và cnt[1][i] = số lượng phụ âm ở bên trái s[i]. * Chương trình minh hoạ bằng ngôn ngữ Python: 14
Bài 6. Để tăng cường sức khoẻ, mỗi ngày An chạy chính xác n phút, tại một phút bất kỳ, An có thể lựa chọn là chạy hay nghỉ trong phút đó. Khi bắt đầu chạy, độ mệt của An là 0. Tại phút t bất kì, nếu An chọn phương án là chạy thì An chạy được chính xác di mét và độ mệt sẽ tăng 1 đơn vị, tuy nhiên độ mệt không thể giảm quá 0. An chỉ có thể bắt đầu chạy trở lại khi độ mệt trở về 0 (tức là nếu An chọn nghỉ ngơi thì An phải nghỉ ngơi ở các phút tiếp theo cho đến khi độ mệt trở về 0 thì mới có thể chạy tiếp). Sau khi kết thúc n phút chạy độ mệt của An cũng phải là 0. Yêu cầu: Hãy tìm khoảng cách lớn nhất mà An có thể chạy? Dữ liệu vào: từ file văn bản bai6.inp - Dòng đầu tiên chứa 2 số nguyên dương n, M (1
- Nếu tại phút thứ i đã đi được j phút (tức là đã đi các phút i, i+1, i+2, ..., i+j-1), thì có nghĩa là phải nghỉ ở các phút i+j, i+j+1, ..., i+2*j-1. Khi đó: dp[i]=(d[i]+d[i+1]+ .... + d[i+j-1]) + dp[i+2*j] - Vì cần phải lấy quãng đường lớn nhất nên ta có: dp[i]= max(dp[i+1], (d[i]+d[i+1]+ .... + d[i+j-1]) + dp[i+2*j]) *Chương trình minh hoạ bằng ngôn ngữ Python: Bài 7. Để đón ngày lễ 30/4, lãnh đạo thị xã Cửa Lò đã chỉ đạo trồng cây hoa ở hai bên lề đường (có thể xem là lề đường A và lề đường B). Sau một thời gian, các cây hoa này đã trưởng thành và có thể phục vụ cho du khách tham quan du lịch. Trước dịp tết nguyên đán vừa qua, người ta thấy trong số các cây hoa được trồng thì cũng có khá nhiều cây hoa không được đẹp nên lãnh đạo Thị xã quyết định đưa ra phương án bỏ đi một số cây hoa và sắp xếp lại cho phù hợp hơn. Người ta đánh dấu cây hoa được đánh giá là đẹp có số 1, các cây xấu được đánh dấu là số -1. Việc bỏ đi các cây hoa xấu có thể làm cho con đường không còn nhiều cây hoa nữa nên công việc ở đây cần làm phải đảm bảo bỏ tất cả các điều kiện sau: - Không được di chuyển cây hoa ở lề đường A sang lề đường B và ngược lại. - Các cây hoa trên cùng một lề đường không được thay đổi vị trí với nhau. - Một cây hoa ở lề đường A và một cây hoa ở lề đường B tạo thành một cặp. - Với một cặp được giữ lại phải luôn luôn không được cả 2 cây hoa cùng xấu. - Số lượng cây hoa được giữ lại là nhiều nhất. 16