Bài tập cực hay

Bài 1: Quy hoạch động
Chuyên đề pascal :
Quy hoạch động
Trong lập trình pascal, các bài toán đơn thuần thì các bạn có thể giải được 1 cách dễ dàng, chỉ cố gắng sửa cho đúng câu lệnh là được, nhưng trong các bài toán đòi hỏi tính tư duy thuật toán cao thì các bạn sẽ phải kết hợp nhiều yếu tố như: tính phản xạ, tính tư duy thuật toán, và đặc biệt phải biết cách nhận định bài toán thuộc dạng nào, nếu làm được thế thì các bạn coi như đã thành công được 1/3 quãng đường. Giới thiệu dài dòng, đi vào chi tiết nhá, một trong các thuật toán quan trọng đó chính là Quy hoạch động. Quy hoạch động được coi là 1 trong những thuật toán cơ bản, (theo mutikeo thì nó chỉ đứng sau duyệt rộng thui )và nếu các bạn nắm chắc được cái này thì thật là hoàn hảo. Bài viết hôm nay sẽ giới thiệu sơ lược về Quy hoạch động, do đây là bài viết mutikeo tự chế, nên các bạn cố gắng tư duy thật kĩ, nếu có điều chi thắc mắc, hoặc thấy sai thì cứ cho ý kiến nhá. Trước hết, ta phải hiểu ý tưởng của quy hoạch động, muốn vậy ta xét 1 ví dụ sau: Vd1 :Tính tổ hợp chập k của n. Cái này đối với chúng ta là quá dễ, Chúng ta sẽ sử dụng công thức truy hồi quen thuộc, tính tổ hợp chập k của n thì phải tính tổ hợp chập k-1 của n-1 và chập k của n-1. Vì vậy chỉ cần viết 1 hàm đệ quy là ra mọi vấn đề nhỉ: Function C(n,k) If (k=0) or (k=n) then C:=1; Else C:=C(n-1,k-1)+C(n-1,k). Nhưng cái này rất nhược điểm, đó là chúng ta sẽ phải tính đi tính lại nhiều lần các giá trị C(i,j) (i Ngược lại, nếu sử dụng quy hoạch động, các bạn sẽ có gì, xem nhé: Uses crt; const max=20; var i,j,k,n : byte; c : array[1..max] of longint; p1,p2 : longint; begin clrscr; {lệnh xoá trắng màn hình, cách nhớ rất đơn giản: Có lòng rồi sẽ có rượu} write(`n,k=`);readln(n,k); C[0]:=1; {gán C(0,1=1)} C[1]:=1; {gán C(1,1=1)} for i:=2 to n do begin p1:=1; for j:=1 to i-1 do begin p2:=C[j] C[j]:=p1+p2; p1:=p2; end; C[i]:=1; end; write(f,C[k],` `); close(f); End. Các bạn thử đọc từng dòng lệnh và tìm hiểu xem chúng có ý nghĩa gì, nếu các bạn tư duy được thuật toán trên thì coi như các bạn đã hiểu được quy hoạch động. Từ đó rút ra được ý tưởng của quy hoạch động nhá: đơn giản chỉ là tránh tính toán lại mọi thứ 2 lần, mà lưu giữ kết quả đã tìm được vào 1 bảng làm giả thiết cho việc tìm kiếm những kết quả của trường hợp sau. Chúng ta sẽ làm đầy dần giá trị của bảng này bởi các kết quả của những trường hợp trước đã được giải. Kết quả cuối cùng chính là kết quả của bài toán cần giải 2.Vậy các bước để xây dựng quy hoạch động là gì: Thứ nhất, chúng ta cần lập được 1 biểu thức, và xây dựng một phương trình truy toán bằng cách chia bài toán thành nhiều giai đoạn và lập biểu thức:
Hay là
(*) Thứ hai, các bạn phải tổ chức dữ liệu và bắt đầu viết chương trình. Cái này rất rất cơ bản, đối với quy hoạch động thì việc khó nhất là tìm được công thức truy hồi, đó là công thức (*) ý. Tìm được cái đó thì coi như bài toán được giải quyết, cách duy nhất để học tốt quy họạch động là làm thật nhiều bài. 3.Các ví dụ: vd2: Giải quyết bài toán Fibonacci. vd3: Bài toán tính n!.