Lập trình động

Chia sẻ: Nguyen Vu | Ngày: | Loại File: PDF | Số trang:96

Thêm vào BST

Báo xấu

121
lượt xem 34
download

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

Lập trình động (còn gọi là phương pháp quy hoạch động) là một kĩ thuật rất hiệu quả giải quyết nhiều bài toán tin học, đặc biệt là những bài toán tối ưu. Số lượng bài toán được giải bằng lập trình động cũng rất lớn, ví dụ riêng kì thi Olympic quốc tế về Tin học IOI 2004 có tới 3 bài trong 6 bài thi có thể giải bằng lập trình động. Nhiều năm gần đây, trong hầu hết các đề thi chọn HSG QG đều có ít nhất 1 trong 3 bài có thể giải bằng phương...

Chủ đề:

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

Lưu

Nội dung Text: Lập trình động

Lời nói đầu Lập trình động (còn gọi là phương pháp quy hoạch động) là một kĩ thuật rất hiệu quả giải quyết nhiều bài toán tin học, đặc biệt là những bài toán tối ưu. Số lượng bài toán được giải bằng lập trình động cũng rất lớn, ví dụ riêng kì thi Olympic quốc tế về Tin học IOI 2004 có tới 3 bài trong 6 bài thi có thể giải bằng lập trình động. Nhiều năm gần đây, trong hầu hết các đề thi chọn HSG QG đều có ít nhất 1 trong 3 bài có thể giải bằng phương pháp quy hoạch động. Nhóm tác giả chúng tôi biên tập tài liệu “Bài tập quy hoạch động” này mong muốn giới thiệu lí thuyết và các bài tập từ đơn giản đến phức tạp của lập trình động. Cuốn sách sẽ là tài liệu quí báu đối với học sinh năng khiếu Tin học, sinh viên các ngành công nghệ thông tin và giáo viên môn Tin học của các trường THPT. Tài liệu gồm 4 chương: Chương I: Cơ sở lý thuyết Chương II: Một số bài tập cơ bản Chương III: Bài tập chọn lọc Chương IV: Một số đề tự giải Chương I nêu rõ tư tưởng, vị trí, ứng dụng của lập trình động và cách nhận diện các bài tập có thể giải bằng phương pháp quy hoạch động. Chương II phân tích và dẫn ra chương trình giải các bài toán kinh điển như: Tìm dãy con không giảm dài nhất, Dãy con chung dài nhất, Tìm dãy con có tổng bằng S, ….Chương III, chương IV giới thiệu đề bài, cách giải, chương trình của rất nhiều bài tập chọn lọc. Chúng tôi chân thành cảm ơn các bạn đồng nghiệp đã nhận xét và góp ý cho bản thảo, trân trọng cảm ơn BGH trường THPT Chuyên Bắc Giang đã khích lệ, tạo điều kiện cho nhóm tác giả được nghiên cứu để tài liệu sớm được ra mắt bạn đọc.
Trong quá trình biên soạn, mặc dù chúng tôi đã cố gắng, song nội dung chuyên đề ngày càng có nhiều khía cạnh mới và sâu sắc nên chắc chắn tài liệu còn nhiều hạn chế. Chúng tôi rất mong được bạn đọc xa gần góp ý, để lần tái bản sau tài liệu sẽ hoàn thiện hơn. Mọi góp ý, xin gửi đến địa chỉ: Nhóm Tin học Trường THPT Chuyên Bắc Giang
Chương I: Cơ sở lý thuyết I.1. Tư tưởng của phương pháp quy hoạch động I.1.1. Thuật toán chia để trị ậ độ ng như chia để ị là các phương pháp giả ộ ằ ổ ợ ờ ả ủ ậ chia để ị đượ ậ ụ ấ ọ ả ộ ớ thướ ban đầ đó ế ặ ở ạ thướ ớ , ngườ ta thườ đế ệ ả ươ ự ư ớ thướ ỏ ơ ọ ủ ư tưở “chia để ị” thườ đượ ắ ớ ư ả ẻ ầ ừ ế đ để ẻ ả đ Chia để ị ự ệ ộ ban đầ con độ ậ đó ả ổ ợ ầ ờ ả ừ ỏ ấ đế ban đầ ư ả ừ ư ế ể ự ệ ộ đơ ả ạ ỏ ơ ữ ứ ế ư ậ cho đế ặ ỏ đế ứ ễ ả đượ đượ ỗ ầ đượ ọ ứ ữ ơ ở ứ dướ ấ ơ ủ ụ đệ thườ ệ ả để ự ệ ậ chia để ị đệ ầ lượ ế ầ ă ế ộ ớ ẽ ự ệ ả ứ ự ngượ ạ ừ đơ ả ấ đỉ ă ế cho đế ả đượ ban đầ ở đáy ă ế ụ ả ồ ốđ ắ ă ầ ử ủ ả ị ằ ố x cho trướ
ươ ự ệ ậ ế ị ộ ể chia để ị ấ ổ ế ) để ả ươ ờ ọ ủ ụ đâ ủ ụ ả ỉ ế ộ ầ đượ n độ ứ ạ ậ ố ơ ế ầ ự I.1.2. Hệ thức truy hồi ả thườ ế ề bướ ế ả ủ ộ bướ thườ ự ế ả ủ bướ ự ệ trướ đó ậ ầ ự ệ ứ ể ệ ệ ề ế ả ữ bướ ọ ệ ứ ồ ụ ố đó ớ ố ạ ứ
ệ ứ ố ạ ứ ủ ệ ứ đ ẵ trong đề ụ ộ ố đi mộ ố ấ ố ạng để ại là đơn điệ ọ ộ ố ề ấ ố ạ ồ ố ạng đó theo tr ự ấ ệ đơn điệ ạ ụ để ả ấ ộ ầ ử ầ ử ở ộ ớ ầ ử ầ ử, … để độ ổ ọ ố ầ ử ủ ầ ử ừ 1 đế ễ dàng tính đượ ế ồ ại j:= 1..i-1 để ả ư ậ , để ả ở ụ ả ế qua n bướ ờ ả ở bướ ụ ộ ờ ả ủ i-1 bướ trướ đó ệ ứ ệ ứ ồ ủ I.1.3. Lập trình động là gì? ậ độ ố ươ chia để ị ở ỗ ờ ả ủ đượ ổ ợ ừ ờ ả “Chia để ị ẽ ban đầ độ ậ ự ấ ạ ả thườ ằ đệ đó ổ ợ ờ ả ủ để đượ ờ ả ủ ban đầ
ậ độ ư ụ ộ ừ ố đượ ỗ ể ế ớ ộ ố ứ dướ ự ấ ạ Đồ ị Đây không phả ộ ấ ộ đồ ị có hướ ả ệ ữ ố ằ ộ ỗ đó đượ ử ụng để ả ề ớn hơn khác nhau. Ví dụ ỗ ố đề ả ần đế ả ộ ột cách ngây thơ có thể ẽ ả ầ ặ ều hơn. Điề ụ ỗ ặ ố ộ ế ận ngây thơ có thể ố ờ ạ ờ ả ối ưu cho các bài toán con mà nó đ ả Để ệc đó, ta lưu trữ ờ ả ủa các bài toán con đ ả ậ ế ầ ả ại chính bài toán đó, ta có thể ấ ử ụ ế ả đ được tính toán. Hướ ế ận này đượ ọ lưu trữ ế đượ ọ ả ừ ợ ế ắ ắ ằ ộ ờ ải nào đó không c ầ ế ữ ể xóa nó đi để ế ệ ộ ớ ộ ố trườ ợ ể ờ ả ết trướ ằ ẽ ần đế
ả ỡ ới i tăng từ 2 đến n), ta đề ử ụ ế ả ủ ỡ ậ độ ọ ngườ ỹ phát minh vào năm 1953. ậ độ thườ để ả ố ư ầ ộ ả ố ấ ả ể đượ ơ ở ủ ậ độ ố ư ố ư ố ư ế đị ộ ế đị ề đ ạ ộ ạ ế đị ban đầ ấ ể ế ữ ế đị ạ ả ạ ộ ả ế ố ư ụ ộ ạ đượ ừ ữ ế đị ban đầ I.1.4. Phương pháp quy hoạch động ọ ươ ạch độ ột phương pháp giả ờ ạ ủ ậ ể ệ ấ ủ ố ấ ối ưu. ư tưở ủ đạ ủ ươ ạ độ ể lượ ư ớ bài toán con tương tự có kích thướ ỏ hơn cho đế ận đượ ờ ả ể ự ễ ả ố ệ ữ ệ ủ ớ ệ ủ ố ệ ể ệ ứ ồ ộ ọ ứ ạch độ ạch độ ấ ừ ệm các bài toán con ban đầu, sau đó kế ợ ệ ủ ứ ạch động ta đượ ệ ỡ ớn hơn. Quá ứ ế ục như vậy cho đến khi ta đượ ệ ủa bài toán đ
ậ ưởng cơ bả ủ ạch độ ật đơn giả ạ ọ ứ ần, mà lưu giữ ế ảđ ếm đượ ộ ả ả ế ệ ế ữ ế ả ủa trườ ợ ẽ làm đầ ầ ị ủ ả ở ế ả ủ ững trườ ợp trước đ đượ ả ế ả ố ế ả ủ ầ ả ụ ố ạ ứ ủ ằ ươ ạ độ ư ệ ủ ỗ ỉ ầ ầ đượ ư ả ề ế ả ủ ỡ ớ ơ ế ả ủ ỉ ệ ấ ra để ử ụ I.2. Các bước thực hiện giải bài toán bằng phương pháp quy hoạch động I.2.1. Các bước cơ bản: Bướ ứ ạch độ ứ ệ ủ ớ ệ ả - Xác đị ệ ủ án con đơn giản (trong trườ ợp cơ sở Bướ ự ệ ổ ứ ữ ệ - Đầ ệ ủa bài toán con đơn giản (cơ sở ở ạ ị ban đầu cho hàm QHĐ) ựa vào hàm QHĐ đ ự ệ ủa bài toán theo kích thướ ớ ần cho đế ận đượ ệ ủa bài toán đ Bướ ổ ứ ữ ệu và cài đặ
- Thườ ả ộ ề ặ ều để lưu trữ ạ ị ủ ị ủa hàm QHĐ) ả ộ ố ế ng thườ ảng để lưu trữ ạ ạ ủa bài toán để ể ấ ờ ả ủ I.2.2. Tổ chức cài đặt: ể ặ ặ đệ ệ ủa các bài toán con đượ ần và lưu trữ ả ầ ấ ở ảng đó ra và sử ụ I.2.3 Khi nào dùng phương pháp quy hoạch động? ặ ấ ồ ờ ả ở bước sau đượ ự ờ ả ở bước trướ - Kích thướ ớ *Ưu điể ờ ả ắ ọ ủa, có tính logic cao, chương tr ạ *Nhược điể ả ả ằng QHĐ ệ ức QHĐ củ ều bài toán là khó khăn ứ ị ạ ế ề ộ ớ ải lưu trữ ệ ủ
Chương ộ ố ập cơ bả Bài 1: Tìm dãy con không gi ảm nhiều phần tử nhất; ố ầ ử ộ ả ủ đ ầ ử ạ ủ đ ỏ ộ ặ ộ ố ầ ử ấ ủ ầ ử ủ ạ ả ụ ộ ả ủ ầ ả ủ ồ ề ầ ử ấ ữ ệ ừ file văn bả ồ đầ ố ế ỗ ố ủ ố ố ể ít hơn 10 số ố ộ ộ ấ ế ả hi ra file văn bả ồ ố max là độ ả ấ đượ ỉ ố ấ ệ ủ ố ạ ủ đ ụ Hướng dẫn: ọi L(i) là độ ăng dài nhấ ầ ử ấ ề ừ đế ầ ử ố ức QHĐ để tính L(i) như sau: ớ ọ ầ ử
ảng phươ ộ ả ộ ều L để lưu trữ ị ủa hàm QHĐ L(i). Đoạn chương tr ị ủ ảng L như sau: Như vậ ủ ờ * Chương trình cài đặt:
Bài 2: Dãy con chung dài nhất; ố ớ
ộ ủ ồ ề ố ạ ấ ận đượ ằng cách xóa đi mộ ố ố ạ ủ ận đượ ằng cách xóa đi mộ ố ố ạ ủ ở ữ ứ ự ầ ử ạ ữ ệ ừ file văn bả ấu trúc như sau: đầ ố nguyên dương M, N. ứ ố ứ ố ế ả Ghi ra file văn bả ấ đầ ố ố lượ ố ạ ủ ế ố ế ứ ố ớ ố ạ ứ ủ ố ạ ứ ủ ố ạ ứ ủ Ví dụ: *Hướng dẫn: ọi L(i,j) là độ ấ ủ ồ ầ ử ầ đầ ủ ồ ầ ử ần đầ ủ
ứ ạch động như sau: ế ế *Chương trình cài đặt:
Bài 3: Dãy con có tổng bằng S ộ ủ đó có tổ ằ ữ ệ ừ ă ả ạ đầ ố ứ ố ế ả ă ả ạ ầ ử ộ đượ ụ * Hướ ẫ
Đặ ế ể ạ ổ ừ ộ ủ ồ ầ ử . Ngượ ạ ế đáp án củ ể ứ ế ặ * Chương tr đặ
Bài 4: Xếp đồ vật vào ba lô (mỗi đồ vật chỉ có 1) ộ ế ể ứ đượ ộ ố lượ N đồ ậ đượ đánh ố ừ 1 đế N, đồ ậ ố lượ ị ử ụ ọ đồ ậ để ế ổ ị đồ ậ ớ ấ ế ể ế đượ ữ ệ ừ ă ả ấ ư đầ ố ươ ứ ớ ố ươ ươ ứ ố lượ ị ử ụ ủ đồ ậ ứ ế ả ă ả ấ đầ ổ ị ử ụ ớ ấ đượ