Liệt kê dãy nhị phân có độ dài n (PP Sinh)

Link bài: http://www.spoj.com/PTIT/problems/BCSINH/

9806. Sinh các dãy nhị phân độ dài n (Cơ bản)

Mã bài: BCSINH

Sinh các dãy nhị phân có độ dài n.

Input

Số nguyên duy nhất n (1<=n<=9)

Output

Mỗi dòng một dãy nhị phân. Các dãy nhị phân phải được liệt kê theo thứ tự từ điển.

Example

Input:
2

Output:
00
01
10
11

 

HD:

Xây dựng một thứ tự các dãy nhị phân cần liệt kê

Gọi a,b là hai dãy nhị phân và p(a) và p(b) là số nguyên tương ứng a,b. Ta xây dựng một thứ tự như sau:

a<b <=> p(a)<p(b)

Suy ra dãy np đầu tiên là 0….0 (n số 0) và dãy np cuối cùng là 1…1(n số 1)

-Xây dựng thuật toán sinh dãy np kế tiếp:

Do dãy kế sẽ có giá trị thập phân lớn hơn dãy nhị phân hiện tại 1 đơn vị nên ta có cách xây dựng dãy np kế như sau: Gọi b1…bn là dãy np hiện tại.

Nếu bi =1, với mọi i=1…n thì đây là dãy cuối cùng, gán stop =1;

Ngược lại:

  • Tìm b i đầu tiên từ phải qua trái sao cho b i =0;
  • Gán b=1 và gán các bi+1 = …= bn= 0;

 

Code tham khảo:

 

Share
Share