Thuyết minh Giải pháp Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư duy một số thuật toán

 n: Xét tất cả các giá trị x[n] có thể nhận, thử cho x[n] nhận lần lượt các giá trị đó, thông báo phương án tìm được .
Trên phương diện quy nạp, có thể nói rằng thuật toán quay lui liệt kê các phương án n phần tử dạng x[1..n] bằng cách thử cho x[1] nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x[1] bài toán trở thành liệt kê tiếp phương án n - 1 phần tử x[2..n].
Mô hình của thuật toán quay lui:
procedure Try(i: Integer); begin
for do begin
;
if then
else
begin
; Try(i + 1); {Gọi đệ quy để chọn tiếp x[i+1]}
;
end;
end;
end;
Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1)
Ví dụ:
Ví dụ 1: Liệt kê các dãy nhị phân độ dài N
Biểu diễn dãy nhị phân độ dài N dưới dạng x[1..n]. Ta sẽ liệt kê các dãy này bằng cách thử
dùng các giá trị {0, 1} gán cho x[i]. Với mỗi giá trị thử gán cho x[i] lại thử các giá trị có thể gán cho x[i+1].Chương trình liệt kê bằng thuật toán quay lui có thể viết:
program BinaryStrings;
const InputFile = 'BSTR.INP'; OutputFile = 'BSTR.OUT'; max = 30;
var	x: array[1..max] of Integer; n: Integer; f: Text;
procedure PrintResult; {In phương án tìm được} var i: Integer;
begin
for i := 1 to n do Write(f, x[i]); WriteLn(f);
end;
procedure Try(i: Integer); {Thử các cách chọn x[i]} var j: Integer;
begin
for j := 0 to 1 do {Xét các giá trị có thể gán cho x[i], với mỗi giá trị đó} begin
26
x[i] := j; {Thử đặt x[i]}
if i = n then PrintResult {Nếu i = n thì in kết quả}
else Try(i + 1); {Nếu i chưa phải là phần tử cuối thì tìm tiếp x[i+1]}
end; end; BEGIN
Assign(f, InputFile); Reset(f); ReadLn(f, n); {Nhập dữ liệu} Close(f);
Assign(f, OutputFile); Rewrite(f); Try(1); {Thử các cách chọn giá trị x[1]} Close(f);
END.
Vẽ cây ví dụ
Bài tập vận dụng:
Bài 1:Bài toán cái túi (Câu 3 đề thi cấp tỉnh V1 năm 2011-2012)
Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b. Có n đồ vật cần đem theo. Đồ vật thứ j có trọng lượng là aj và giá trị sử dụng là cj (j = 1, 2, 3, ..,n). Hỏi rằng nhà thám hiểm cần đem theo các đồ vật nào để cho tổng giá trị sử dụng của các đồ vật đem theo là lớn nhất?
Input: Vào từ file văn bản CAITUI.INP:
Dòng đầu ghi 2 số nguyên dương n và b (n < 100).
Dòng thứ hai ghi các số nguyên không âm a1, a2, .. ,an.
Dòng thứ ba ghi các số nguyên không âm c1, c2, .. ,cn.
Output: Ghi ra file CAITUI.OUT:
Dòng đầu ghi tổng giá trị các đồ vật đem theo ứng với phương án tìm được.
Ghi chỉ số của các đồ vật đem theo
CAITUI.INP
CAITUI.OUT
4	8
5	3	2	4
10	5	3	6
15
1	2
Quy hoạch động. (DYNAMIC PROGRAMMING)
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.
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 những bài toán nhỏ đã lưu trong bảng phương án để tìm lời giải của những bài toán lớn hơn và 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.
Ví dụ
Ví dụ 1: Bài toán Tính N!	GT.PAS
Ta có định nghĩa như sau: n! =
ì1
î
ín *(n -1)!
nếu
n = 0
n > 0
Cho một số nguyên dương n (0 £ n £ 13).
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: Ghi trong file văn bản GT.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương n.
Dữ liệu ra: Ghi ra file văn bản GT.OUT theo cấu trúc như sau:
- Dòng 1: Ghi giá trị tính được của n!
Ví dụ:
GT.INP
GT.OUT
3
6
Thuật toán:
Gọi GT[i] là giá trị của i! (0 £ i £ 13)
Ta có công thức quy hoạch động như sau: GT[i] := GT[i-1]*i;
Như vậy, việc tính n! sẽ được thực hiện bằng vòng lặp: GT[0] :=1;
For i:=1 to n do
GT[i] := GT[i-1]*i;
Kết quả: giá trị của n! nằm trong phần tử GT[n].
Ví dụ 2: Dãy con đơn điệu:
Bài toán: Cho dãy số nguyên A = a1, a2, , an. (n ≤ 1000, -10000 ≤ ai ≤ 10000). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự.
Yêu cầu: Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất.
Đặc trưng:
Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử A[i] trong dãy, các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị.
Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu.
Công thức quy hoạch động:
Hàm mục tiêu: f : độ dài dãy con.
Vì độ dài dãy con chỉ phụ thuộc vào một yếu tố là dãy ban đầu nên bảng phương án là mảng một chiều. Gọi Li là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ A1 đến Ai và phần tử cuối cùng là Ai.
Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con.
Ta có công thức QHĐ để tính Li như sau:
L[n+1] = 1. (Hiển nhiên)
Li = L[jmax] + 1 với mọi phần tử j thỏa mãn: 0 < j < i và Aj ≤ Ai
Tính Li: phần tử đang được xét là Ai. Ta tìm đến phần tử Aj < Ai có Lj lớn nhất. Khi đó nếu bổ sung Ai vào đầu dãy con ...Aj ta sẽ được dãy con tăng dần dài nhất xét từ A1...Ai.
Truy vết:
Tại bước xây dựng dãy L, mỗi khi tính L[i] := L[jmax] + 1, ta đặt T[i] = jmax. Để lưu lại rằng: Dãy con dài nhất bắt đầu tại Ai sẽ có phần tử thứ hai kế tiếp là
Ajmax. Sau khi tính xong hay dãy L và T, ta bắt đầu từ 0.
T[0] là phần tử đầu tiên được chọn, T[T[0]] là phần tử thứ hai được chọn, T[T[T[0]]] là phần tử thứ ba được chọn ... Quá trình truy vết có thể diễn tả như sau:
i := T[0];
while i n + 1 do
{Chừng nào chưa duyệt đến số an+1=+∞ ở cuối} begin
 i := T[i];
end;
Cài đặt : Ví dụ: với A = (5, 2, 3, 4, 9, 10, 5, 6, 7, 8).
Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ Li và mảng giá trị T sử dụng để lưu trữ vị trí của các phần tử trong dãy con.
i
0
1
2
3
4
5
6
7
8
9
10
11
ai
-∞
5
2
3
4
9
10
5
6
7
8
+∞
L[i]
9
5
8
7
6
3
2
5
4
3
2
1
T[i]
2
8
3
4
7
6
11
8
9
10
11

Truy vết
Cài đặt:
Const max:=1000;
Var a, L, T: array [1..max+1] of longint; N: longint;
Procedure nhapdl; { Nhap du lieu cho mang A} Procedure QHD_daycondondieu;
Var I, j, jmax: longint; Begin
A[0] := -32768; A[n+1] := 32767;
L[n+1] := 1;
For i:= n downto 0 do Begin
Jmax:= n+1;
For j:= i+1 to n+1 do
If (A[j]>A[i]) and (L[j]> L[jmax]) then jmax:= j;
L[i] := L[jmax] + 1; T[i] := jmax;
Writeln(‘Chieu dai cua day con la: ’, L[0] - 2);
{Truy vet tim va hien thi day con} i:= T[0];
while i n+1 do begin
write (A[i]); i:= T[i];
end; End; BEGIN
Nhapdl; QHD_daycondondieu;
END.
Như vậy độ phức tạp bộ nhớ của bài toán là O(n), độ phức tạp thời gian là O(n2).
Có một số phương pháp cài đặt tốt hơn so với phương pháp trên, cho chi phí thời gian là O(nlogn), một trong những cách đó là dùng cây nhị phân.
Bài tập vận dụng:
Bài 1: Cho hai số nguyên dương M, N (0 ≤ M, N ≤ 100) và hai dãy số nguyên: A1, A2,..., AM và B1, B2,..., B N. Tìm một dãy dài nhất C là dãy con chung dài nhất của hai dãy A và B, nhận được từ A bằng cách xoá đi một số số hạng và cũng nhận được từ B bằng cách xoá đi một số số hạng.
Dữ liệu vào trong file LCS.INP có dạng:
+ Dòng thứ nhất chứa M số A1, A2,..., AM
+ Dòng thứ hai chứa N số B1, B2,..., B N.
Dữ liệu ra trong file LCS.OUT có dạng:
+ Dòng thứ nhất ghi số k là số số hạng của dãy C.
+ Dòng thứ hai chứa k số là các số hạng của dãy C.
Hướng dẫn: Công thức QHĐ
Cần xây dựng mảng L[0..M, 0..N] với ý nghĩa: L[i, j] là độ dài của dãy chung dài nhất của hai dãy A[0.. i] và B[0..j].
Đương nhiên nếu một dãy là rỗng (số phần tử là 0) thì dãy con chung cũng là rỗng vì vậy L[0, j] = 0 với j = 1.. N, L[i, 0] = 0 với i = 1.. M. Với M ≥ i > 0 và N ≥ j > 0 thì L[i, j] được tính theo công thức truy hồi sau:
L[i,j] = Max{L[i, j-1], L[i-1, j], L[i-1, j-1] + x}
(với x = 0 nếu A[i] ≠ B[j] , x=1 nếu A[i]=B[j])
Bài 2: Biến đổi xâu:
Cho xâu ký tự X, xét 3 phép biến đổi:
Insert(i, C): i là số, C là ký tự: Phép Insert chèn ký tự C vào sau vị trí i của xâu X.
Replace(i, C): i là số, C là ký tự: Phép Replace thay ký tự tại vị trí i của xâu X bởi ký tự C.
Delete(i): i là số, Phép Delete xoá ký tự tại vị trí i của xâu X.
Yêu cầu: Cho trước xâu Y, hãy tìm một số ít nhất các phép biến đổi trên để biến xâu X thành xâu Y.
Input: file văn bản STR.INP
Dòng 1: Chứa xâu X (độ dài ≤ 100)
Dòng 2: Chứa xâu Y (độ dài ≤ 100)
Output: file văn bản STR.OUT ghi các phép biến đổi cần thực hiện và xâu X tại mỗi phép biến đổi.
STR.INP
STR.OUT
PBBCEFATZ QABCDABEFA
7
PBBCEFATZ -> Delete(9) -> PBBCEFAT PBBCEFAT -> Delete(8) -> PBBCEFA PBBCEFA -> Insert(4, B) -> PBBCBEFA PBBCBEFA -> Insert(4, A) -> PBBCABEFA PBBCABEFA -> Insert(4, D) -> PBBCDABEFA
PBBCDABEFA -> Replace(2, A) -> PABCDABEFA
PABCDABEFA -> Replace(1, Q) -> QABCDABEFA
Hướng dẫn: Công thức QHĐ:
Hàm mục tiêu: f: số phép biến đổi.
Dễ thấy số phép biến đổi phụ thuộc vào vị trí i đang xét của xâu X và vị trí j đang xét của xâu F. Do vậy để cài đặt cho bảng phương án ta sẽ dùng mảng 2 chiều.
Gọi L[i,j] là số phép biến đổi ít nhất để biến xâu Xi gồm i kí tự phần đầu của X (Xi=X[1..i]) thành xâu Fj gồm j kí tự phần đầu của F (Fj=F[1..j]).
Công thức QHĐ:
L[0,j]=j
L[i,0]=i
L[i,j] =L[i−1,j−1] nếu Xi=Yj.
L[i,j] = min(L[i−1,j], L[i,j−1], L[i-1,j-1]) +1 nếu Xi≠Fj.
Bài 3: Xâu con chung dài nhất:
Cho 2 xâu X, Y. Hãy tìm xâu con của X và của Y có độ dài lớn nhất. Biết xâu con của một xâu thu được khi xóa một số kí tự thuộc xâu đó (hoặc không xóa kí tự nào).
Hướng dẫn: Công thức QHĐ:
Gọi L[i,j] là độ dài xâu con chung dài nhất của xâu Xi gồm i kí tự phần đầu của X(Xi=X[1..i]) và xâu Yj gồm j kí tự phần đầu của Y (Yj=Y[1..j]). Ta có công thức quy hoạch động như sau:
L[0,j] = L[i,0] = 0
L[i,j] = L[i−1,j−1] + 1 nếu Xi=Yj
L[i,j] = max(L[i−1,j], L[i,j−1]) nếu Xi≠Yj.
Bài 4: Xâu đối xứng (Palindome):
Bài toán: Một xâu gọi là xâu đối xứng (palindrome) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.
Hướng dẫn: Công thức QHĐ:
Gọi L[i,j] là số kí tự ít nhất cần thêm vào xâu con S[i..j] của S để xâu đó trở thành đối xứng.
Đáp số của bài toán sẽ là L[1,n] với n là số kí tự của S. Ta có công thức sau để tính L[i,j]:
L[i,i]=0.
L[i,j]=L[i+1,j−1] nếu Si=Sj L[i,j]=max(L[i+1,j],L[i,j−1]) nếu Si≠Sj
PHỤ LỤC II
THIẾT KẾ BÀI GIẢNG ÔN LUYỆN ĐỘI TUYỂN
CHỦ ĐỀ / BÀI HỌC: THUẬT TOÁN TÌM GIÁ TRỊ LỚN NHẤT CỦA
DÃY SỐ.
Chủ đề gồm nội dung:
Nội dung 1: Thuật toán tìm Max.
Nội dung 2: Bài tập vận dụng.
MỤC TIÊU BÀI HỌC
Sau khi học chủ đề, học sinh cần:
Biết cách viết thuật toán tìm giá trị lớn nhất của một dãy số.
Biết đánh giá độ phức tạp thuật toán từ đó lựa chọn ra thuật toán tối ưu tương ứng với từng bài toán.
Biết vận dụng thuật toán vào giải quyết các bài toán trong thực tế và ở một số các môn học: Toán, Lý, 
Phát triển tư duy logic và bước đầu hình thành kĩ năng giải quyết vấn đề cho học sinh.
Bước đầu có cảm hứng và đam mê lập trình.
ĐỒ DÙNG DẠY HỌC
Máy tính.
Tài liệu: Sách giáo khoa tin học 10, cấu trúc dữ liệu và giải thuật.
Phiếu học tập.
CÁC HOẠT ĐỘNG DẠY HỌC
Khởi động
Mục đích: Tạo hứng thú cho học sinh trong việc tìm hiểu kiến thức.
Phương pháp tiến hành: Giáo viên giao nhiệm vụ cho học sinh về nhà đọc và tìm hiểu thuật toán tìm giá trị lớn nhất của dãy số với các nội dung:
+ Xác định bài toán.
+ Ý tưởng giải quyết bài toán.
+ Viết thuật toán.
+ Đánh giá độ phức tạp thuật toán.
Định hướng kết quả: Học sinh hệ thống và nắm được thuật toán cơ bản tìm giá trị lớn nhất trong chương trình lớp 10.
b. Hoạt động ôn tập
Mục đích: Kiểm tra việc thực hiện nhiệm vụ của học sinh trong phần khởi động.
Phương thức tiến hành: Yêu cầu học sinh hoàn thành phiếu học tập.
Định hướng sản phẩm:
Nội dung
Tìm giá trị lớn nhất của dãy số
Xác định bài toán
Input: Số nguyên dương N và dãy N số nguyên a1,..., aN.
Output: Giá trị lớn nhất Max của dãy số.
Ý tưởng giải quyết bài toán
Khởi tạo Max = a1
Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với Max, nếu ai > Max thì Max nhận giá trị mới là ai.
Thuật toán
Liệt kê :
Bước 1. Nhập N và dãy a1,, aN; Bước 2. Max := a1, i := 2;
Bước 3. Nếu i > N thì đưa ra giá trị Max rồi kết thúc; Bước 4.
Bước 4.1. Nếu ai > Max thì Max := ai;

Bước 4.2. i := i + 1 rồi quay lại bước 3;
Sơ đồ khối
Độ phức tạp thuật toán.
- Độ phức tạp thuật toán là O(N)

c. Luyện tập vận dụng và cũng cố
Mục đích:
+ Giúp học sinh củng cố kiến thức về thuật toán tìm giá trị lớn nhất và vận dung thuật toán đó giải quyết các bài toán khác.
+ Giúp học sinh đưa ra được ý tưởng tối ưu ( Sử dụng thuật toán sắp xếp).
Phương thúc tiến hành: Giáo viên tổ chức cho học sinh làm bài tập vận dung:
Bài 1: Tìm giá trị nhỏ nhất của một dãy số nguyên.
Dãy A gồm N số nguyên a1, a2, , aN (N<= 100). Viết thuật toán đưa ra giá trị nhỏ nhất của dãy.
Ví dụ: Dãy A: 1, 5, 8,10, 7, 4, 2 thì giá trị nhỏ nhất của dãy là 1
Bài 2: Tìm giá trị lớn thứ nhì của một dãy số nguyên.
Dãy A gồm N số nguyên a1, a2, , aN (N<= 100). Viết thuật toán đưa ra giá trị lớn thứ nhì của dãy.
Ví dụ: Dãy A: 1, 5, 8,10, 7, 4, 2 thì giá trị lớn thứ nhì của dãy là 8
Bài 3: Tìm giá trị lớn thứ k của một dãy số nguyên.
Dãy A gồm N số nguyên a1, a2, , aN (N<= 100). Viết thuật toán đưa ra giá trị lớn thứ k của dãy (k nguyên dương có giá trị được nhập vào từ bàn phím)
Ví dụ: Dãy A: 1, 5, 8,10, 7, 4, 2 với k = 2 thì giá trị lớn thứ 2 của dãy là 8
MỘT SỐ HÌNH ẢNH SẢN PHẨM CỦA HỌC SINH
Thuật toán tìm Max và đếm số lượng số có giá trị bằng Max
Bài 1: Tìm giá trị nhỏ nhất của một dãy số nguyên.
Bài 3: Tìm giá trị lớn thứ k của một dãy số nguyên.
Bài 2: Tìm giá trị lớn thứ nhì của một dãy số nguyên.
MỘT SỐ PHIẾU HỌC TẬP ÁP DỤNG TRONG QUÁ TRÌNH GIẢNG DẠY
TÀI LIỆU THAM KHẢO
Giải thuật và lập trình - Lê Minh Hoàng - ĐHSP Hà Nội.
Tài liệu chuyên Tin Học quyển 1 - Hồ Sĩ Đàm (Chủ biên ) - NXB Giáo Dục.
Sách giáo khoa Tin Học 10 - Hồ Sĩ Đàm (Chủ biên ) - NXB Giáo Dục.
Trang 
Chuyên đề “Quy hoạch động” - Nguyễn Thanh Tùng - ĐHSP Hà Nội.
Quy hoạch động - Nhóm tác giả Trường THPT chuyên Bắc Giang.
Đề thi học sinh giỏi văn hóa cấp tỉnh Tin Học 11 từ năm 2018 đến 2021.
MỤC LỤC	Trang
Tên sáng kiến	2
Ngày sáng kiến được áp dụng	2
Các thông tin bảo mật	2
Mô tả giải pháp cũ thường làm	2
Sự cần thiết phải áp dụng giải pháp sáng kiến	3
Mục đích của giải pháp	4
Nội dung	4
Thuyết minh giải pháp mới hoặc cải tiến	4
Tên giải pháp	4
Nội dung	4
Thuật toán	4
Áp dụng thuật toán vào giải quyết các bài toán	8
Các bước tiến hành thực hiện giải pháp	8
Kết quả khi thực hiện giải pháp	8
+ Sản phẩm được tạo ra từ giải pháp	8
+ Các bảng số liệu, biểu đồ so sánh	8
Thuyết minh về phạm vi áp dụng sáng kiến	10
Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến	10
Phụ lục I	11
Phụ lục II	36