SKKN Giải bài toán bằng phương pháp quy hoạch động dùng mảng 1 chiều

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ 
 TRƯỜNG THPT HÀM RỒNG
SÁNG KIẾN KINH NGHIỆM
GIẢI BÀI TOÁN BẰNG PHƯƠNG PHÁP 
QUY HOẠCH ĐỘNG DÙNG MẢNG 1 CHIỀU
Người thực hiện: Nguyễn Thượng Thiên
Chức vụ: Giáo viên
SKKN thuộc lĩnh mực: Tin học
THANH HOÁ NĂM 2018
Mục lục
Trang
1. Mở đầu
2
1.1. Lí do chọn đề tài
2
1.2. Mục đích nghiên cứu
1.3. Đối tượng nghiên cứu 
2
1.4. Phương pháp nghiên cứu
2
1.5. Những điểm mới của SKKN
2
2. Nội dung sáng kiến kinh nghiệm
2
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm:
2
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm:
4
2.3. Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng để giải quyết 
4
2.4. Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động giáo dục, với bản thân, đồng nghiệp và nhà trường
14
3. Kết luận, kiến nghị
14
1. MỞ ĐẦU
1.1. Lí do chọn đề tài: 
	Nhằm nâng cao chuyên môn và là giao lưu học hỏi, mong mọi người đánh giá chỉ ra điểm ưu, nhược điểm đồng thời xem xét về mặt giá trị thiết thực phục vụ trong công tác dạy và học.
1.2. Mục đích nghiên cứu:
 Để dạy nâng cao việc dạy và học phục vụ cho luyện thi học sinh giỏi.
1.3. Đối tượng nghiên cứu: 
Chương trình lập trình nâng cao cho lớp 11.
1.4. Phương pháp nghiên cứu: 
	Kết hợp tài liệu cùng với thực hành thực tiễn một số bài toán áp dụng thực tế.
2. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm:
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 một số bài toán đệ quy, 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ó thành 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 án quy hoạch động, nguyên lý chia để trị càng được thể hiện rõ: Khi không biết phải giải quyết những bài toán con nào, ta sẽ đi giải quyết toàn bộ 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 ra 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 ra tiếp thành nhiều bài toán nhỏ hơn và lại đi giải các 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).
Bài toán giải theo phương pháp quy hoạch động gọi tắt là bài toán quy hoạch động. 
Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn gọi là công thức truy hồi của quy hoạch động.
Tập các bài toán có ngay lời giải để từ đó giải quyết các bài toán lớn hơn gọi là cơ sở quy hoạch động.
Không gian lưu trữ lời giải các bài toán con để tìm cách phối hợp chúng gọi là bảng phương án của quy hoạch động. 
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ó thỏa mãn những yêu cầu dưới đây 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 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ác bước cài đặt một chương trình sử dụng quy hoạch động:
+ 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.
+ Dùng công thức truy hồi phối hợp những lời giải của các bài toán nhỏ đã lưu trong bảng phương án để tìm lời giải của các bài toán lớn hơn rồi 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.
+ Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu.
Cho tới nay, vẫn chưa có một định lý nào cho biết một cách chính xác những bài toán nào có thể giải quyết hiệu quả bằng quy hoạch động. Tuy nhiên để biết được bài toán có thể giải bằng quy hoạch động hay không, ta có thể đặt câu hỏi:
1. “Một nghiệm tối ưu của bài toán lớn có phải là sự phối hợp các nghiệm tối ưu của các bài toán con hay không?” 
2. “Liệu có thể nào lưu trữ được nghiệm các bài toán con dưới một hình thức nào đó để phối hợp tìm được ngiệm bài toán lớn?”.
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm:
Trước khi chưa áp dụng có những bài toán khọc sinh giải bằng kiến thức trong SGK không ăn hết được số test trong khoảng thời gian 1 giây.
2.3. Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng để giải quyết 
Ví dụ về các bài toán có thể giải bằng phương pháp quy hoạch động
2.1. Bài toán 1:
 Tính N!	GT.PAS
	Ta có định nghĩa như sau: n! = nếu 
Cho một số nguyên dương n (0 £ n £ 20). 
Yêu cầu: Hãy tính n! bằng phương pháp quy hoạch động (lập bảng phương án).
Dữ liệu: Vào từ file văn bản GT.INP gồm 1 số nguyên dương n.
Kết quả: Ghi ra file văn bản GT.OUT gồm 1 dòng là giá trị của n!
Ví dụ:
GT.INP
GT.OUT
3
6
Thuật toán:
Gọi f[i] là giá trị của i!
Vì ta biết n! = n*(n-1)!. Từ đây ta có công thức quy hoạch động sau:
	f[i] := f[i-1]*i;	
	Kết quả của bài toán là f[n].
Code tham khảo: 
// Độ phức tạp O(n)
const fi='GT.INP';
 fo='GT.OUT';
var n: integer;
 f: array[0..30] of qword;
procedure giaithua;
var i: integer;
begin
 f[0]:=1;
 for i:=1 to n do f[i]:= f[i-1]*i;
end;
BEGIN
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(n);
 giaithua;
 writeln(f[n]);
 close(input); close(output);
END.
2.2. Bài toán 2
 Tính dãy Fibonaci	FIBO.PAS
	Ta có định nghĩa như sau: F(n) = 	 nếu 
Cho một số nguyên dương n (0 £ n £ 50). 
Yêu cầu: Hãy tính F(n) bằng phương pháp quy hoạch động (lập bảng phương án).
Dữ liệu: Vào từ file văn bản FIBO.INP gồm 1 số nguyên dương n.
Kết quả: Ghi ra file văn bản FIBO.OUT là giá trị tính được của F(n).
Ví dụ:
FIBO.INP
FIBO.OUT
5
8
Thuật toán:
	Gọi F[i] là giá trị Fibonaci thứ i.
	Bài toán cơ sở: F[0] = 1; F[1] = 1;
	Ta có công thức quy hoạch động như sau:
	F[i] := F[i-1] + F[i-2];
	Kết quả của bài toán chính là F[n].
Code tham khảo: 
// Độ phức tạp O(n)
const fi='fibo.inp';
 fo='fibo.out';
var n: longint;
 i: longint;
 f: array[0..51] of int64;
BEGIN
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(n);
 f[0]:= 1; f[1]:= 1;
 for i:= 2 to n do f[i]:= f[i-1] + f[i-2];
 writeln(f[n]);
 close(input); close(output);
END.	
2.3. Bài toán 3
 Tính tổng của dãy số	
	Cho dãy số nguyên gồm n phần tử a1, a2, , an và hai số nguyên dương p và q (1 £ p £ q £ n).
Yêu cầu: Hãy tính tổng của các phần tử liên tiếp từ ap  aq.
Dữ liệu: Vào từ file văn bản SUM.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương n và k, hai số được ghi cách nhau một dấu cách. (1 £ k, n £ 105)
- Dòng 2: Ghi n số nguyên a1, a2, , an, các số được ghi cách nhau ít nhất một dấu cách (-32000 £ ai £ 32000). 
- Dòng thứ i trong k dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương pi và qi, hai số được ghi cách nhau một dấu cách (1 £ pi £ qi £ n). 
Kết quả: Ghi ra file văn bản SUM.OUT theo cấu trúc như sau:
- Dữ liệu được ghi trên k dòng: Dòng thứ i ghi một số nguyên là tổng giá trị của các phần tử trong đoạn 
Ví dụ:
SUM.INP
SUM.OUT
5 3
2 9 -3 5 8
1 5
2 3
4 4
21
6
5
Thuật toán:
	Gọi S[i] là tổng giá trị các phần tử a1, a2, , ai (1 £ i £ n).
	Ta có công thức quy hoạch động để tính S[i] như sau:
	S[i] := S[i - 1] + A[i];
	Như vậy, việc tính T[n] được thực hiện bằng vòng lặp:
	S[0] := 0;
For i:=1 to n do
	S[i] := S[i - 1] + A[i];
	Kết quả: Tổng các phần tử liên tiếp từ ap đến aq được tính theo công thức:
	Sum := S[q] - S[p-1];
2.6. Bài toán 4
Thỏ nhặt cà rốt	
Các con thú nuôi trong chuồng ở vườn bách thú thường ít có điều kiện vận động. Điều này vừa có hại cho sức khỏe của thú nuôi, vừa làm làm giảm hứng thú của khách tham quan. Để khắc phục điều đó, Ban giám đốc cho đặt một cái thang có n bậc trong chuồng thỏ. Đến giờ cho ăn người ta đặt cà rốt - thứ khoái khẩu nhất của thỏ, lên bậc trên cùng của thang. Thỏ phải nhảy theo các bậc thang để lấy cà rốt. Mỗi bước nhảy thỏ có thể không được vượt quá k bậc (1 ≤ k ≤ n ≤ 300). Có thể có nhiều cách nhảy để lấy cà rốt. Hai cách nhảy gọi là khác nhau nếu tồn tại một bậc thỏ tới được ở một cách nhảy và bị bỏ qua ở cách kia. Ví dụ, với n = 4 và k = 3 có tất cả 7 cách lấy cà rốt khác nhau: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1.
Yêu cầu: Cho k và n. Hãy xác định số cách khác nhau thỏ có thể thực hiện để lấy cà rốt.
Dữ liệu: Vào từ file văn bản CARROT.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương t là số lượng cặp k và n (1 ≤ t ≤ 50).
- Dòng thứ i trong t dòng tiếp theo: Mỗi dòng ghi 2 số nguyên k và n.
Kết quả: Ghi ra file văn bản CARROT.OUT, kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên.
Ví dụ:	
CARROT.INP
CARROT.OUT
3
1 3
2 7
3 10
1
21
274
Thuật toán:
+ Gọi f[i] là số cách mà thỏ có thể nhảy tới bậc thứ i của thang.
+ Ta có bài toán cơ sở f[0] = 1; 
+ Công thức f[i] = f[i-k] + f[i-k+1] + + f[i-1]
+ Kết quả bài toán là f[n]
Code tham khảo:
// Độ phức tạp O(n)
const fi='carrot.inp';
 fo='carrot.out';
var t,k, n: longint;
 f: array[0..301] of int64;
 i: longint;
procedure xuli;
var i,j: longint;
begin
 f[0]:= 1;
 for i:= 1 to k do
 begin
 f[i]:=0;
 for j:= 0 to i-1 do f[i]:= f[i] + f[j];
 end;
 for i:= k+1 to n do
 begin
 f[i]:=0;
 for j:= i-k to i-1 do f[i]:= f[i] + f[j];
 end;
 writeln(f[n]);
end;
BEGIN
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(t);
 for i:= 1 to t do
 begin
 readln(k, n);
 xuli;
 end;
 close(input); close(output);
END.	
2.7. Bài toán 5
Cho một hình chữ nhật kích thước 2xN (1<=N<=100). Hãy đếm số cách lát các viên gạch nhỏ kích thước 1x2 và 2x1 vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát. 
Dữ liệu: Vào từ file văn bản LATGACH.INP gồm nhiều test:
+ Dòng đầu ghi số lượng test T ( T<=100 ).
+ T dòng sau mỗi dòng ghi một số N. 
Kết quả: Ghi ra file LATGACH.OUT gồm T dòng là số cách lát tương ứng. 
Ví dụ:
LATGACH.INP
LATGACH.OUT
3
1
2
3
1
2
3
Thuật toán: 
Nhận thấy N = 1 thì có 1 cách xếp. N = 2 thì có 2 cách xếp. N = 3 thì có 3 các xếp. N = 4 thì có 5 cách xếp. Từ đó ta suy ra được quy luật của đáp án chính là dãy số fibonaci: f[i] = f[i-1] + f[i-2]. Nhưng do N <= 100 nên kết quả của bài toán có thể lên tới số có khoảng 21 chữ số. Vì vậy chúng ta phải xử lí số lớn.
2.9. Bài toán 6
Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang gồm n bậc.
Các bậc thang được đánh số từ 1 đến n từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số 1 (bậc thang số 1 không bao giờ bị thủng).
Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ n). Bờm muốn nhờ bạn trả lời câu hỏi này.
Dữ liệu: Vào từ file văn bản VSTEPS.INP: 
Dòng đầu tiên: gồm 2 số nguyên n và k, là số bậc của cầu thang và số bậc thang bị hỏng (0 ≤ k < n ≤ 100000). 
Dòng thứ hai: gồm k số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng dần.
Kết qủa: Ghi ra file VSTEPS.OUT gồm phần dư của số cách Lucky leo hết cầu thang khi chia cho 14062008.
Ví dụ:
VSTEPS.INP
VSTEPS.OUT
4 2
2 3
0
90000 1
49000
4108266
Thuật toán:
	+ Gọi f[i] là số cách nhảy từ bậc 1 đến bậc thứ i
	+ Ta có bài toán cơ sở: f[1] = 1
	+ Công thức quy hoạch động 
	 f[i] = f[i-1] + f[i-2] mod base; nếu bậc thang thứ i không bị hỏng
	 f[i] = 0; nếu bậc thang thứ i bị hỏng	
	+ Kết quả của bài toán là f[n].
Code tham khảo:
const fi='';//'vsteps.inpt';
 fo='';//'vsteps.out';
 base=14062008;
var a:array[1..100000] of longint;
 f:array[0..100000] of longint;
 n,b,i,k:longint;
BEGIN
 assign(input,fi);reset(input);
 readln(n,k); fillchar(a,sizeof(a),0);
 for i:=1 to k do
 begin
 read(b);
 a[b]:=b;
 end;
 close(input);
 fillchar(f,sizeof(f),0);
 f[1]:=1;
 for i:=2 to n do
 if a[i]=0 then
 f[i]:=((f[i-2])+(f[i-1])) mod base;
 assign(output,fo);rewrite(output);
 writeln(f[n]);
 close(output);
END.
2.11. Bài toán 7
Văn bản là một dãy gồm N từ đánh số từ 1 đến N. Từ thứ i có độ dài là wi (i=1, 2,... N). Phân trang là một cách xếp lần lượt các từ của văn bản vào dãy các dòng, mỗi dòng có độ dài L, sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá L.Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số (L-S), trong đó S là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng. Tìm cách phân trang với hệ số phạt nhỏ nhất.
Dữ liệu: Vào từ file văn bản PTRANG.INP
Dòng 1 chứa 2 số nguyên dương N, L (N<=6000,L<=1000) 
Dòng thứ i trong số N dòng tiếp theo chứa số nguyên dương wi (wi<=L), i=1, 2,.., N 
Kết quả: Ghi ra file PTRANG.OUT là hệ số phạt nhỏ nhất 
Ví dụ:
PTRANG.INP
PTRANG.OUT
4 5
3
2
2
4
2
Thuật toán:
	+ Gọi w[i] là tổng độ dài của từ thứ 1 đến từ thứ i
	+ gọi g[i] là hệ số phạt nhỏ nhất khi xét đến từ thứ i
	+ Công thứ quy hoạch động
	G[i] = min(max(g[j], L – (w[i] – w[j])) nếu w[i] – w[j] <=L. Với mọi j = i-1 .. 0 
 	+ Kết quả của bài toán chính là g[n].
Code tham khảo:
uses math;
const	fi='ptrang.inp';
	fo='ptrang.out';
var n,l,i,j:longint;
 w,g:array[0..6000] of longint;
procedure Solve;
 begin
 w[0]:=0;
 for i:=1 to n do w[i]:=w[i]+w[i-1];
 for i:=1 to n do
 begin
 g[i]:=maxlongint;
 for j:=i-1 downto 0 do
 begin
 if w[i]-w[j]>l then break;
 g[i]:=min(g[i],
 	 max(g[j],l-(w[i]-w[j])));
 end;
 end;
	write(g[n]);
 end;
BEGIN
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(n,l);
 for i:=1 to n do readln(w[i]);
 solve;
 close(input); close(output);
END.
2.21 Bài toán 8
Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N]. 
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],... A[ik] thỏa mãn 
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử? 
Dữ liệu: Vào từ file văn bản LIQ.INP gồm
Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000). 
Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000). 
Kết quả: Ghi ra file LIQ.OUT - độ dài của dãy con tăng đơn điệu dài nhất.
Ví dụ:	
LIQ.INP
LIQ.OUT
6
1 2 5 4 6 2
4
Thuật toán:
	+ Gọi f[i] là độ dài dãy con đơn điệu tăng mà có phần tử a[i] là phần tử cuối cùng
	+ Nhận thấy f[1] = 1;
	+ Công thức quy hoạch động 
	f[i] = max(f[j]) + 1 nếu a[j]<a[i] Với mọi j =1..i-1
	Ngược lại f[i] = 1;
	+ Kết quả bài toán là max(f[i])
	+ Trong lúc cài đặt nếu cần đưa ra dãy con đó thì chúng ta sử dụng phần truy vết như code. 
Code tham khảo:
const fi='LIQ.INP';
 fo='LIQ.OUT';
var a,f,tr:array[1..100] of integer;
 jmax,max,i,j,n,ii:byte;
procedure enter;
 begin
 assign(input,fi);reset(input);
 readln(n);
 for i:=1 to n do read(a[i]);
 close(input);
 end;
procedure solve;
 begin
 ii:=1;
 for i:=1 to n do
 begin
 f[i]:=1; jmax:=i;
 for j:=1 to i-1 do
 if (a[j]<a[i]) and 
	(f[j]+1>f[i])then
 begin
 f[i]:=f[j]+1;
 jmax:=j;
 if max<f[i] then
 begin
 max:=f[i];
 ii:=i;
 end;
 end;
 tr[i]:=jmax;
 end;
 end;
procedure solution;
 begin
 assign(output,fo);rewrite(output);
 writeln(max);
	 { Truy vet ra day con neu can
 i:=ii; f[i]:=0;
 while itr[i]do
 begin
 i:=tr[i];
 f[i]:=0;
 end;
 for i:=1 to n do
 if f[i]=0 then write(a[i],' ');}
 close(output);
 end;
BEGIN
 enter;
 solve;
 solution;
END.
2.4. Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động giáo dục, với bản thân, đồng nghiệp và nhà trường
Giúp cho bản thân tôi phải đọc nhiều tài liệu, tập hợp các bài toán những dạng cơ bản để rồi có thể quy lạ thành quen trong một số bài toán ứng dụng tương tự, đồng thời giúp học sinh nâng cao cách giải quyết các bài toán thực tế. 
3. Kết luận, kiến nghị
- Kết luận: Với thời gian không cho phép, trong khuôn khổ một sáng kiến kinh nghiệm, mong các Thầy, cô đồng nghiệp góp ý để đề tài hoàn thiện hơn, mang tính thiết thực hơn.
- Kiến nghị: Không
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ
Thanh Hóa, ngày 03 tháng 5 năm 2018
CAM KẾT KHÔNG COPY.
(Tác giả ký và ghi rõ họ tên)
Nguyễn Thượng Thiên