SINH CÁC DÃY NHỊ PHÂN ĐỘ DÀI N

 
Một dãy nhị phân độ dài n là một dãy x[1..n] trong đó x[i] Î {0, 1} ("i : 1 £ i £ n).
Dễ thấy: một dãy nhị phân x độ dài n là biểu diễn nhị phân của một giá trị nguyên p(x) nào đó nằm trong đoạn [0, 2ⁿ - 1]. Số các dãy nhị phân độ dài n = số các số tự nhiên Î [0, 2ⁿ - 1] = 2ⁿ. Ta sẽ lập chương trình liệt kê các dãy nhị phân theo thứ tự từ điển có nghĩa là sẽ liệt kê lần lượt các dãy nhị phân biểu diễn các số nguyên theo thứ tự 0, 1, …, 2ⁿ-1.
Ví dụ: Khi n = 3, các dãy nhị phân độ dài 3 được liệt kê như sau:
 

p(x)	0	1	2	3	4	5	6	7
x	000	001	010	011	100	101	110	111

Như vậy dãy đầu tiên sẽ là 00…0 và dãy cuối cùng sẽ là 11…1. Nhận xét rằng nếu dãy x = x[1..n] là dãy đang có và không phải dãy cuối cùng cần liệt kê thì dãy kế tiếp sẽ nhận được bằng cách cộng thêm 1 ( theo cơ số 2 có nhớ) vào dãy hiện tại.
Ví dụ khi n = 8:
 

Dãy đang có:	10010000	Dãy đang có:	10010111
cộng thêm 1:	+ 1 ⎯⎯⎯⎯	cộng thêm 1:	+ 1 ⎯⎯⎯⎯
Dãy mới:	10010001	Dãy mới:	10011000

 
 
Như vậy kỹ thuật sinh cấu hình kế tiếp từ cấu hình hiện tại có thể mô tả như sau: Xét từ cuối dãy về đầu (xét từ hàng đơn vị lên), tìm số 0 gặp đầu tiên

 
v Nếu thấy thì thay số 0 đó bằng số 1 và đặt tất cả các phần tử phía sau vị trí đó bằng 0.
v Nếu không thấy thì thì toàn dãy là số 1, đây là cấu hình cuối cùng
Dữ liệu vào (Input): nhập từ file văn bản BSTR.INP chứa số nguyên dương n £ 100 Kết quả ra (Output): ghi ra file văn bản BSTR.OUT các dãy nhị phân độ dài n.

BSTR.INP: 
3
BSTR.OUT:
000
001
010
011
100
101
110

111