SKKN Một số giải pháp sử dụng thuật toán duyệt để giải một số bài toán trong bồi dưỡng học sinh giỏi

MỤC LỤC 
1. MỞ ĐẦU
1.1. Lí do chọn đề tài. 
Các phương pháp duyệt thường xuất hiện trong bài toán tổ hợp nhằm tìm kiếm tất cả các trạng thái (tổ hợp) có thể có của một tập các trạng thái, hoặc tìm ra một tổ hợp thoả mãn tốt nhất một số yêu cầu xác định trong số các trạng thái của tập hợp.
Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu sự phân bố các phần tử vào các tập hợp. Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo yêu cầu của bài toán cần nghiên cứu. Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp. Liệt kê, đếm các đối tượng có những tính chất nào đó là một phần quan trọng của lý thuyết tổ hợp. Chúng ta cần phải đếm các đối tượng để giải nhiều bài toán khác nhau. Và các bài toán tin có liên quan đến toán tổ hợp chiếm một tỷ lệ rất lớn.
Các phương pháp duyệt thông thường bao gồm: 
Phương pháp duyệt toàn bộ: Duyệt qua tất cả các trạng thái có thể có của tập hợp. Phương pháp này phù hợp với bài toán liệt kê và với các tập hợp có số lượng các trạng thái là đủ nhỏ để không tốn thời gian duyệt. 
Phương pháp duyệt chọn lọc: Thường áp dụng khi số lượng trạng thái của tổ hợp là rất lớn, không thể sử dụng phương pháp duyệt toàn bộ. Phương pháp này chỉ dùng cho các bài toán tìm kiếm một (hoặc một số) trạng thái tốt nhất (theo một số tiêu chí xác định) của tổ hợp bằng cách chỉ duyệt theo một số trạng thái được cho là có khả năng tìm được kết quả cao nhất.
Các bài toán giải bằng phương pháp duyệt (thử sai) ngày càng chiếm một vị trí quan trọng trong các kỳ thi học sinh giỏi quốc gia, tin học trẻ, học sinh giỏi tỉnh. Toán thử sai là một dạng toán khó, đòi hỏi tư duy lôgic, tư duy thuật toán cao, tính hình tượng tốt, phù hợp với mục đích tuyển chọn học sinh có khả năng và năng khiếu toán tin. Hơn nữa, nội dung các bài toán kiểu này ngày càng gần với thực tế, và điều này hoàn toàn phù hợp với xu hướng của tin học hiện đại.
Là một giáo viên đang giảng dạy tại trường THPT Như Thanh, tôi nhận thấy sử dụng phương pháp duyệt để giải một số bài toán là một vấn đề cơ bản đầu tiên người giáo viên nên đưa ra trong quá trình phát hiện và bồi dưỡng những học sinh có năng khiếu về lập trình.
Xuất phát từ lí do trên tôi chọn đề tài: "Một số giải pháp sử dụng thuật toán duyệt để giải một số bài toán trong bồi dưỡng học sinh giỏi" nhằm mục đích phục vụ tốt hơn nữa cho giáo viên và xây dựng nền móng ban đầu cho những học sinh yêu thích môn lập trình.
1.2. Mục đích nghiên cứu.
Mục đích chính của đề tài là đưa ra một số giải pháp trong việc sử dụng thuật toán duyệt để giải một số bài toán bồi dưỡng học sinh giỏi ở mức độ cơ bản. 
1.3. Đối tượng nghiên cứu và phạm vi nghiên cứu
1.3.1. Đối tượng nghiên cứu
Ứng dụng phương pháp duyệt vào một số bài toán cụ thể.
1.3.2. Phạm vi nghiên cứu
Trong khuôn khổ của một sáng kiến kinh nghiệm, tôi chỉ giới hạn một số vấn đề sau:
- Một số kiến thức cơ bản của đại số tổ hợp, thuật toán duyệt
- Hướng dẫn giải một số bài toán bằng phương pháp duyệt.
1.4. Phương pháp nghiên cứu
- Hệ thống hóa một số kiến thức có liên quan đến đại số tổ hợp và thuật toán quay lui.
- Thiết kế các thuật toán cho mỗi bài toán theo thứ tự được tối ưu dần.
2. NỘI DUNG
2.1. CƠ SỞ LÝ THUYẾT
2.1.1. Kiến thức đại số tổ hợp
2.1.1.1. Hoán vị
Cho tập hợp A gồm n phần tử (n ³ 1). Mỗi cách sắp thứ tự n phần tử của tập hợp A được gọi là một hoán vị của n phần tử đó.
	Gọi Pn là số hoán vị của n phần tử, ta có: 
	Pn = n! = n(n-1)2.1
Ví dụ: 
	Cho A = {1, 2, 3}, các hoán vị của A là: 
	1 2 3 
	1 3 2 	 	
2 1 3 
2 3 1
3 1 2
	3 2 1	
	có 3! = 6 hoán vị của A.
2.1.1.2 Chỉnh hợp có lặp.
Một cách sắp xếp có thứ tự k phần tử có thể lặp lại của một tập n phần tử được gọi là một chỉnh hợp lặp chập k từ tập n phần tử. Nếu A là tập gồm n phần tử đó thì mỗi chỉnh hợp như thế là một phần tử của tập Ak. Ngoài ra, mỗi chỉnh hợp lặp chập k từ tập n phần tử là một hàm từ tập k phần tử vào tập n phần tử. Vì vậy số chỉnh hợp lặp chập k từ tập n phần tử là nk.
2.1.1.3 Chỉnh hợp không lặp
Cho A là tập hợp gồm n phần tử ( n ³ 1). Mỗi bộ gồm k phần tử ( 0 £ k £ n) sắp thứ tự của tập hợp A được gọi là chỉnh hợp chập k của n phần tử của A. 
	Gọi là số các hoán vị chập k của n. Ta có công thức sau: 
Ví dụ: 
	Cho A = {1, 2, 3}. Thì các chỉnh hợp chập 2 của A là
	(1, 2)	 (2, 1) 	(1, 3) 	
	(3, 1) 	 	 (2, 3) 	(3, 2)
	 Có tất cả chỉnh hợp chập 2 của A.
2.1.1.4 Tổ hợp
Cho tập hợp A gồm n phần tử ( n ³ 1). Mỗi tập con gồm k phần tử của tập hợp A được gọi là một tổ hợp chập k của n phần tử đã cho.
Gọi là số tổ hợp chập k của n phần tử, ta có:
Một số công thức về tổ hợp:
2.1.2. Sinh các hoán vị và tổ hợp
Phương pháp sinh được áp dụng để giải quyết bài toán liệt kê của lý thuyết tổ hợp. Để áp dụng được phương pháp này thì bài toán phải thoả mãn hai điều kiện sau:
	- Có thể xác định được thứ tự trên tập các cấu hình tổ hợp cần liệt kê. Từ đó có thể xác định được cấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đó.
	- Xây dựng được một thuật toán cho phép từ một cấu hình chưa phải cấu hình cuối, sinh ra được cấu hình kế tiếp của nó. Phương pháp sinh có thể được mô tả tổng quát như sau:
repeat
Until 
2.1.2.1. Sinh các hoán vị
	Có nhiều thuật toán đã được phát triển để sinh ra n! hoán vị của tập {1,2,...,n}. Ta sẽ mô tả một trong các phương pháp đó, phương pháp liệt kê các hoán vị của tập {1,2,...,n} theo thứ tự từ điển. Khi đó, hoán vị a1a2...an được gọi là đi trước hoán vị b1b2...bn nếu tồn tại k (1 £ k £ n), a1 = b1, a2= =b2,..., ak-1 = bk-1 và ak < bk.
	Thuật toán sinh các hoán vị của tập {1,2,...,n} dựa trên thủ tục xây dựng hoán vị kế tiếp, theo thứ tự từ điển, từ hoán vị cho trước a1 a2 ...an. Đầu tiên nếu an-1 aj+2 > ... > an, tức là tìm cặp số nguyên liền kề đầu tiên tính từ bên phải sang bên trái của hoán vị mà số đầu nhỏ hơn số sau. Sau đó, để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất trong các số lớn hơn aj của tập aj+1, aj+2, ..., an, rồi liệt kê theo thứ tự tăng dần của các số còn lại của aj, aj+1, aj+2, ..., an vào các vị trí j+1, ..., n. Dễ thấy không có hoán vị nào khác đi sau hoán vị xuất phát và đi trước hoán vị vừa tạo ra. 
Ví dụ: Tìm hoán vị liền sau theo thứ tự từ điển của hoán vị 4736521.
	Cặp số nguyên đầu tiên tính từ phải qua trái có số trước nhỏ hơn số sau là a3 = 3 và a4 = 6. Số nhỏ nhất trong các số bên phải của số 3 mà lại lớn hơn 3 là số 5. Đặt số 5 vào vị trí thứ 3. Sau đó đặt các số 3, 6, 1, 2 theo thứ tự tăng dần vào bốn vị trí còn lại. Hoán vị liền sau hoán vị đã cho là 4751236.
procedure Hoan_vi _lien_sau (a1, a2, ..., an);
Begin
	j := n - 1;
	while aj > aj+1 do
	j := j - 1 {j là chỉ số lớn nhất mà aj < aj+1}
	k := n;
	while aj > ak do 
	k := k – 1;
 {ak là số nguyên nhỏ nhất trong các số lớn hơn aj và bên phải aj}
	đổi chỗ (aj, ak);
	r := n;
	s := j + 1;
	while r > s do
	Begin
	đổi chỗ (ar, as);
	r := r - 1 ; s := s + 1;
	end;
{Điều này sẽ xếp phần đuôi của hoán vị ở sau vị trí thứ j theo thứ tự tăng dần.}
end;
2.1.2.2. Sinh các tổ hợp
	Làm thế nào để tạo ra tất cả các tổ hợp các phần tử của một tập hữu hạn? Vì tổ hợp chính là một tập con, nên ta có thể dùng phép tương ứng 1-1 giữa các tập con của {a1,a2,...,an} và xâu nhị phân độ dài n.
	Ta thấy một xâu nhị phân độ dài n cũng là khai triển nhị phân của một số nguyên nằm giữa 0 và 2n - 1. Khi đó 2n xâu nhị phân có thể liệt kê theo thứ tự tăng dần của số nguyên trong biểu diễn nhị phân của chúng. Chúng ta sẽ bắt đầu từ xâu nhị phân nhỏ nhất 00...00 (n số 0). Mỗi bước để tìm xâu liền sau ta tìm vị trí đầu tiên tính từ phải qua trái mà ở đó là số 0, sau đó thay tất cả số 1 ở bên phải số này bằng 0 và đặt số 1 vào chính vị trí này.
procedure Xau_nhi_phan_lien_sau(bn-1bn-2...b1b0);
Begin
	i := 0;
	while bi = 1 do
	begin 
	bi := 0;
	i := i + 1;
	end;
	bi := 1;
End;
Tiếp theo chúng ta sẽ trình bày thuật toán tạo các tổ hợp chập k từ n phần tử {1,2,...,n}. Mỗi tổ hợp chập k có thể biểu diễn bằng một xâu tăng. Khi đó có thể liệt kê các tổ hợp theo thứ tự từ điển. Có thể xây dựng tổ hợp liền sau tổ hợp a1a2...ak bằng cách sau. Trước hết, tìm phần tử đầu tiên ai trong dãy đã cho kể từ phải qua trái sao cho ai ¹ n - k + i. Sau đó thay ai bằng ai + 1 và aj bằng ai + j - i + 1 với j = i + 1, i + 2, ..., k.
 Ví dụ: Tìm tổ hợp chập 4 từ tập {1, 2, 3, 4, 5, 6} đi liền sau tổ hợp {1, 2, 5, 6}.
Ta thấy từ phải qua trái a2 = 2 là số hạng đầu tiên của tổ hợp đã cho thỏa mãn điều kiện ai ¹ 6 - 4 + i. Để nhận được tổ hợp tiếp sau ta tăng ai lên một đơn vị, tức a2 = 3, sau đó đặt a3 = 3 + 1 = 4 và a4 = 3 + 2 = 5. Vậy tổ hợp liền sau tổ hợp đã cho là {1,3,4,5}. Thủ tục này được cho dưới dạng thuật toán như sau:
Procedure To_hop_lien_sau (a1, a2, ..., ak);
Begin
	i := k;
	while ai = n - k + i do
	i := i - 1;
	ai := ai + 1;
	for j := i + 1 to k do
	aj := ai + j - i;
End;
2.1.3. Thuật toán quay lui
	Nét đặc trưng của phương pháp này là ở chỗ các bước đi đến lời giải hoàn toàn bằng cách làm thử. Nếu có một lựa chọn được chấp nhân thì ghi nhớ các thông tin cần thiết các bước thử tiếp theo. Trái lại, nếu không có một lựa chọn nào thích hợp thì làm lại bước trước, xoá bớt các ghi nhớ và quay về chu trình thử với các lựa chọn còn lại. Hành động này được gọi là quay lui (Back tracking) và các giải thuật thể hiện phương pháp này gọi là các giải thuật quay lui.
Nội dung chính của phương pháp này là việc xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng. Giả thiết cấu hình cần được tìm được mô tả bằng một bộ giá trị (x 1 ,x 2 ,..,x N ). Giả sử đã xác định được i - 1 thành phần (x 1 ,x 2 ,...,x i-1 ), bây giờ ta xác định thành phần x i bằng cách duyệt tất cả các khả năng có thể đề cử cho nó (đánh số từ 1 đến n i ).Với mỗi khả năng j, kiểm tra xem j có được chấp nhận hay không. Có thể có hai trường hợp có thể xảy ra:
- Nếu j được chấp nhận thì xác định x i theo j, sau đó nếu j = N thì ta được một cấu hình, trái lại ta tiếp tục tiến hành việc xác định x i+1 .
- Nếu thử tất cả các khả năng mà không có khả năng nào được chấp nhận thì ta sẽ lùi lại bước trước để xác định x i-1 . 
Cần phải lưu ý là ta phải ghi nhớ tại mỗi bước đã đi qua, những khả năng nào đã thử để tránh trùng lặp. Những thông tin này được lưu trữ theo kiểu dữ liệu ngăn xếp - Stack ( vào sau ra trước) - vì thế nên thuật toán này phù hợp thể hiện bởi thủ tục đệ quy. Ta có thể mô tả bước xác định xi bởi thủ tục đệ quy sau: 
Procedure Try (i); 
Begin 
For Do
Begin 
;
if Then 
 	else 
begin
	;
	Try(i+1);
	;
end;
end;
End; 
	Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1);
Trong thủ tục mô tả trên, điều quan trọng nhất là đưa ra được một danh sách các khả năng đề cử và xác định được giá trị của biểu thức logic [chấp nhận v]. Ngoài việc phụ thuộc v, giá trị này còn phụ thuộc vào việc đã chọn các khả năng tại i – 1 bước trước đó. Trong những trường hợp như vậy, cần ghi nhớ trạng thái mới của quá trình sau khi [xác định xi theo v] và trả lại trạng thái cũ sau lời gọi Try(i+1). Các trạng thái này được ghi nhận nhờ một số biến tổng thể (global), gọi là các biến trạng thái.
Dễ thấy rằng bài toán vô nghiệm khi ta đã duyệt hết mọi khả năng mà không có khả năng nào thoả mãn yêu cầu. Ta nói rằng là đã vét cạn mọi trường hợp. Chú ý rằng là đến một lúc nào đó ta phải lùi liên tiếp nhiều lần.Từ đó suy ra rằng, thông thường bài toán vô nghiệm khi không thể lùi được nữa.
2.1.4. Những vấn đề cần chú ý khi giải bài toán bằng phương pháp thử sai
2.1.4.1. Đoán nhận vector nghiệm
Để giải bài toán bằng phương pháp thử sai, việc đầu tiên phải làm là xác định được vector nghiệm, cụ thể cần xác định: vector nghiệm gồm bao nhiêu thành phần (ý nghĩa mỗi thành phần), miền giá trị của mỗi thành phần và các ràng buộc giữa các thành phần. Đây là công việc quan trọng mang ý nghĩa quyết định đến việc giải quyết bài toán.
2.1.4.2. Giảm thiểu số trường hợp phải thử, giảm thiểu chi phí kiểm tra
Qua cách tính độ phức tạp của phương pháp thử sai như sau:
Độ phức tạp bằng số khả năng thử nhân với chi phí trung bình kiểm tra một khả năng.
Ta nhận thấy, để giảm độ phức tạp thuật toán ta có thể giảm thiểu số khả năng phải thử hoặc giảm chi phí kiểm tra.
2.1.4.3. Một số độ phức tạp thường gặp
Độ phức tạp
Giá trị của n có thể giải được
(Dùng với máy chạy con CPU core i3)
O(n)
n~100.000.000
O(n.Logn)
n~1.000.000
O(n2)
n~10000 
O(n3)
n~460 
2.2. THỰC TRẠNG
Trong quá trình giảng dạy, tôi nhận thấy đa số các em học sinh khi thực hiện giải một bài toán tin, các em chỉ cần giải quyết xong, giải quyết được bài toán mà các em chưa tìm cách để giải quyết bài toán một cách "sâu sắc". Từ giải quyết được, các em phải phân tích, nâng cấp, cải tiến để trở thành giải quyết hay một bài toán. Với cách làm đó, sau khi các em giải quyết xong một bài toán, ngoài sự rèn luyện về tư duy lập trình, các em sẽ tích lũy được rất nhiều kiến thức, cũng như kỹ thuật cài đặt cho một thao tác cụ thể nào đó.
Đặc biệt, trong các kỳ thi học sinh giỏi, phương pháp duyệt là phương pháp thường được học sinh lựa chọn khi không tìm được phương pháp giải hiệu quả hơn. Như nhà bác học Thomas Edison đã phát biểu cách tìm một cây kim trong một đống rơm: "Trong khi chưa nghĩ ra được cách thật hay thì cứ việc rút từng cọng rơm cho đến khi rút được cây kim". Vì vậy, thông qua việc đưa ra các giải pháp sử dụng thuật toán duyệt để giải một số bài toán, tôi mong rằng các bạn học sinh sẽ tự khắc phục được những hạn chế của mình và yêu thích môn lập trình hơn.
2.3. MỘT SỐ GIẢI PHÁP SỬ DỤNG THUẬT TOÁN DUYỆT CHO MỘT SỐ BÀI TOÁN CƠ BẢN
2.3.1. Bài toán BỘ TAM HỢP 
2.3.1.1. Đề bài
Cho dãy số nguyên a1, a2, ..., an, các số khác nhau từng đôi một (3 £ n £ 5000; với mọi i ta có |ai| £ 106). Bộ ba số ai, aj, ak (i ¹ j ¹ k) được gọi là Bộ tam hợp nếu có một số bất kỳ trong ba số đó bằng trung bình cộng của hai số còn lại.
Yêu cầu: Hãy đếm số lượng bộ tam hợp và tìm bộ tam hợp có tổng giá trị của ba số là lớn nhất.
Dữ liệu vào: Đọc từ file văn bản có tên TAMHOP.INP có cấu trúc như sau:
- Dòng 1 chứa số n;
- Dòng 2 chứa n số a1, a2, ..., an cách nhau ít nhất một dấu cách
Dữ liệu ra: Ghi ra file văn bản có tên TAMHOP.OUT có cấu trúc như sau:
- Dòng 1 ghi một số nguyên dương là số lượng bộ tam hợp tìm được;
- Dòng 2 ghi tổng giá trị ba số của bộ tam hợp là lớn nhất.
Ví dụ:
TAMHOP.INP
TAMHOP.OUT
7
6 1 9 2 3 4 8 
5
18
2.3.1.2. Hướng dẫn giải
a. Lời giải O(n3)
- Xác định vector nghiệm: (x1,x2,x3) trong đó 1≤ x1,x2,x3≤n tương ứng là bộ chỉ số (i,j,k).
- Xác định ràng buộc: có một số bất kỳ trong ba số đó bằng trung bình cộng của hai số còn lại.
Để liệt kê tất cả các khả năng ta có thể sử dụng ba vòng lặp lồng nhau như sau.
Procedure Bai2_p1;
Begin
	count:=0;
	For x1:=1 To N-2 Do
	For x2:=x1+1 To N-1 Do
	For x3:=x2+1 To N Do
If isOK(x1,x2,x3) Then Inc(Count);
End;
Trong đó hàm isOK(x1,x2,x3) nhận ba tham số đầu vào là ba chỉ số của dãy số có nhiệm vụ kiểm tra ràng buộc, trả về TRUE nếu thỏa mãn ràng buộc, FALSE trong trường ngược lại.
Độ phức tạp của thuật toán: Số trường hợp thử O(n3) nhân với chi phí kiểm tra O(1), do đó độ phức tạp của thuật toán trên là O(n3).
b. Lời giải O(n2.Logn)
Để giảm độ phức tạp thuật toán ta giảm số trường hợp thử xuống O(n2) và tăng chi phí kiểm tra lên O(Logn) như sau:
- Sắp xếp dãy số theo thứ tự tăng dần (dùng Quick Sort có độ phức tạp O(n.Logn))
- Dùng hai vòng để liệt kê các trường hợp thử cho x1 và x2, khi biết phần tử A[x1], A[x2] thì sẽ biết được phần tử A[x3].
- Dùng tìm kiếm nhị phân để xem A[x3] có trong dãy đã sắp xếp trước đó chưa.
Procedure bai2_p2;
Begin
Quicksort; {Sắp xếp dãy số}	
count:=0;
	For x1:=1 To N-2 Do
	For x2:=x1+1 To N-1 Do
	Begin
	x:=A[x2]*2-A[x1];
If Binary(x) Then Inc(Count);
	end;
End;
Như vậy, độ phức tạp thuật toán là O(n.Logn + n2.Logn), rút gọp lại ta có độ phức tạp thuật toán chỉ còn O(n2.Logn).
c. Lời giải O(n2)
Để giảm độ phức tạp thuật toán ta giữ nguyên số trường hợp thử O(n2) và giảm chi phí kiểm tra lên xuống O(1) như sau:
- Dùng mảng KT[A[i]] =1 để đánh dấu số A[i] có xuất hiện trong dãy số.
- Dùng hai vòng để liệt kê các trường hợp thử cho x1 và x2, khi biết phần tử A[x1], A[x2] thì sẽ biết được phần tử A[x3].
- Kiểm tra xem A[x3] có tồn tại trong mảng KT hay không bằng cách: Nếu KT[A[x3]] =1 thì tồn tại số A[x3].
Procedure Bai2_p3;
Begin
For i:=1 To N Do Inc(KT(A[i]); 	
count:=0;
	For x1:=1 To N-2 Do
	For x2:=x1+1 To N-1 Do
	Begin
	x:=A[x2]*2-A[x1];
If KT(x)=1 Then Inc(Count);
	End;
End;
Như vậy, độ phức tạp thuật toán là O(n + n2), rút gọp lại ta có độ phức tạp thuật toán chỉ còn O(n2).
2.3.2. Bài toán SINH DÃY NHỊ PHÂN CÓ ĐỘ DÀI N                     
2.3.2.1. Đề bài
Dãy nhị phân có độ dài N là một dãy X[1..N] trong đó X[i]  {0,1} ("i: 1 ≤ i ≤ N). Ví dụ: với N  = 3 ta có các dãy nhị phân sau: 000, 001, 010, 011, 100, 101, 110, 111. 
Yêu cầu: Hãy viết chương trình liệt kê tất cả các dãy nhị phân có độ dài N. 
Dữ liệu vào: Cho trong file văn bản có cấu trúc như sau:           
          	- Dòng 1: Ghi số nguyên dương N. (1 ≤ N ≤ 255). 
Dữ liệu ra: Ghi ra file văn bản BSTR.OUT theo cấu trúc sau:
          	-  Trên mỗi dòng: Ghi một dãy nhị phân có độ dài N tìm được.
Ví dụ: 
BSTR.INP
BSTR.OUT
3
000
001
010
011
100
101
110
111
2.3.2.2. Hướng dẫn
* Lời giải O(2n)
Tư tưởng của thuật toán tạo dãy nhị phân độ dài n bit là vét cạn. Tôi nói “vét cạn” bởi lẽ với mỗi cấu hình vừa tạo ra được, bạn đều có thể xét 1 trường hợp riêng lẻ, và cho đến cấu hình cuối cùng (cấu hình đích), thì bạn đã xét cụ thể tất cả các trường hợp nhất định.Thuật toán tạo dãy nhị phân gồm có tất cả 2 phương pháp, đó là phương pháp liệt kê và phương pháp sinh. Tôi sẽ lần lượt giới thiệu cho các bạn cả 2 phương pháp đó.
	* Phương pháp liệt kê. Đây là một phương pháp dùng kĩ thuật đệ quy quay lui, có lẽ vì vậy mà tốc độ tạo dãy sẽ bị hạn chế tối đa vì bản chất chính kĩ thuật này. Song, việc tạo dãy với phương pháp này được xem là dễ hiểu và “trong sáng”. Cấu hình khởi điểm của dãy là tất cả các phần tử đều có giá trị 0 (fillchar(a, sizeof(a), 0);) . Sau đó dùng 2 giá trị {0,1} để thử gán cho phần tử a[i], và tiếp tục với các phần tử a[i+1]. Khi kiểm tra thấy một cấu hình a[1..n] đươc gán xong (tức i = n) thì sẽ in cấu hình đó ra. Chương trình kết thúc khi đạt được cấu hình đích (tất cả giá trị của mỗi phần tử đều là 1).
Procedure Try (i : integer); 
Var j : byte;
Begin
For j := 0 to 1 do 
Begin
a[i] := j;                   {Thử gán j = {0,1} cho a[i]}
if (i = n) then Print(a)  
{Nếu cấu hình đã hoàn thành thì tiến hành in ra}
else Try(i+1); 
{Nếu chưa hoàn thành cấu hình thì thử gán cho phần tử thứ i+1}
End;
 	End;
* Dùng phương pháp sinh: Phương pháp này sẽ duyệt từ cuối mảng trở ngược lên đầu mảng, tìm số 0 đầu tiên trong cấu hình:
------ - Nếu tồn tại số 0 đó thì thay a[i] = 1, sau đó tiếp tục thay tất cả cấu hình sau i (i+1, i+2, ) thành 0.
------ - Nếu không tồn tại số 0 đó thì có nghĩa dãy đã toàn là số 1, vì vậy đã đạt được cấu hình đích. Kết thúc chương trình.
Procedure BSTR;
Begin
	Fillchar (x, sizeof (x), 0); {Cấu hình ban đầu}
	Repeat
	;
	i:=n;
	While (i>0) and (Xi=1) do Dec(i);
	If i>0 then {chưa gặp cấu hình cuối cùng}
	Begin
	Xi:=1;
	;
	End;
	Until i= 0;
End;
2.3.3 Bài toán BIỂU THỨC ZERO
2.3.3.1. Đề bài
Cho một số tự nhiên N ≤ 9. Giữa các số từ 1 đến N hãy thêm vào các dấu + (cộng) và – (trừ) sao cho kết quả thu được bằng 0.
Yêu cầu: Hãy viết chương trình tìm tất cả các khả năng có thể. 
Dữ liệu vào: Lấy từ file văn bản ZERO.INP với một dòng ghi số N. 
Dữ liệu ra: Ghi vào file văn bản có tên ZERO.OUT có cấu trúc như sau: 
- Dòng đầu ghi số lượng kết quả tìm được. 
- Các dòng sau mỗi dòng ghi một kết quả tìm được. 
Ví dụ 
	2.3.3.2. Hướng dẫn
Áp dụng thuật toán đệ quy quay lui để giải quyết bài toán nay, ta sẽ dùng thủ tục đệ quy Try(i). Giả sử ta đã điền các dấu’+’ và ’-’ vào các số từ 1 đến i, bây giờ cần điền các dấu giữa i và i + 1. Ta có thể chọn một trong ba khả năng