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++

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
Nội dung trích xuất từ tài liệu:
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ỤCPhầ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 ..................................................................................... 2Phầ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 ............................................................................ 30Phần III. KẾT LUẬN VÀ KIẾN NGHỊ .................................................................. 36 3.1. Kết luận ........................................................................................................... 36 3.2. Kiến nghị ......................................................................................................... 36TÀ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ộcsố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óiriê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 caodâ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ọncá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 đượcquan tâm đúng với tầm quan trọng của nó. Tin Học đang bị xem là môn phụ trongtrườ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ăncho giáo viên trong nhà trường và đặc biệt chọn đội ngũ học sinh giỏi. Mặt khácmô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ênphầ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àiviệ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 để đảmbả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á t ...