Bài toán đặt ra ra liệt kê tất cả các xâu nhị phân có n phân tử.
Ví dụ: Liệt kê tất cả các xâu nhị phân có 4 phần tử.
Ta có bảng liệt kê sau:
|
STT |
||||
|
1 |
0 |
0 |
0 | 0 |
|
2 |
0 | 0 | 0 |
1 |
|
3 |
0 |
0 | 1 |
0 |
|
4 |
0 | 0 | 1 | 1 |
| 5 | 0 | 1 | 0 |
0 |
| 6 | 0 | 1 | 0 |
1 |
| 7 | 0 | 1 | 1 |
0 |
|
8 |
0 |
1 | 1 | 1 |
|
9 |
1 | 0 | 0 |
0 |
|
10 |
1 | 0 | 0 | 1 |
|
11 |
1 | 0 | 1 |
0 |
| 12 | 1 | 0 | 1 |
1 |
|
13 |
1 |
1 |
0 |
0 |
| 14 | 1 | 1 | 0 |
1 |
| 15 | 1 | 1 | 1 |
0 |
|
16 |
1 |
1 |
1 |
1 |
Quy luật của dãy đó là: Tìm chỉ số đầu tiên là số 0 theo thứ tự từ phải sang trái và gán cho số đó là 1, các số đứng sau số đó (tức nằm bên phải ) thì gán hết cho bằng 0.
Nói các khác :
- Tìm chỉ số I đầu tiên theo thứ tự i = n, n – 1, n – 2, …, 1 sao cho bi = 0.
- Gán lại cho bi = 1 và bj = 0 với tất cả j > i. Dãy nhị phân thu được là dãy cần tìm.
–>Cài đặt (chương trình viết bằng C++)
Study&Share 