Như tiêu đề, mình đang có 1 bài tập khá hay nhưng mà hơi hóc mình chưa nghĩ ra thuật toán cho nó.
Mọi người đọc và cùng suy nghĩ, thảo luận và góp ý cho mình xem phải giải nó như thế nào nhé!
Đề bài: Hãy liệt kê các dãy nhị phân độ dài n mà trong đó dãy 01 chỉ xuất hiện đúng 2 lần
ví dụ: n = 5 thì ra có
00101 01001 01010 01011 01101 10101
Vậy nếu
n = 1
NA
n = 2
01
N = 3
001 010 101 011
Phải không nhỉ?
Trong đề chỉ có như vậy thôi, nhưng em nghĩ chăc không phải, có lẽ đề nên yêu cầu n>=4 anh @ltd
Hình như không phải anh, ý bạn ấy là trong dãy số đó “01” xuất hiện 2 lần chắc n>=4 mơi có: 0101, 01101
À, Đạt hiểu nhầm, tưởng là xuất hiện một lần. Hóa ra là xuất hiện hai lần
Nếu vậy dãy này bị thiếu rồi? Ví dụ thiếu
01101
vâng anh, cái ví dụ là em tự viết ra cho dễ hiểu nên bị thiếu, để em bổ xung
Thực ra em thiếu có 1 trường hợp thôi ^^ Anh nhìn không kỹ, vậy là được rồi
theo mình bạn nên dùng phương pháp quay lui dãy nhị phân cần tìm là mảng x[1. .n]. giả sử k là số lần xuất hiện 01. nếu k = 2 && x[i] = 0 thì x[i+1] = 0 còn x[i] = 1 thì x[i+1] = 1 hoặc 0 đều được.
còn nếu k<2 và x[i] = 0 , x[i+1] = 1 thì k++ hoặc x[i+1] = 0 thì giữ nguyên k. Có lẽ mình giải thích quá khó hiểu.
Mình nghỉ làm như sau:
-Liệt kê các hoán vị :có (n)(n-i) trường hợp
-Đối với mỗi hoán vị check xem “01” có xuất hiện 2 lần không-> xuât
Mình nghĩ là từ thuật toán sinh sâu nhị phân có độ dài n, thêm một biến đếm số chuỗi “01”.
//vi du n=10
int a[11];
a[0]=1;//chuỗi bắt đầu từ a[1]
void binary(int n, int pos, int count)
{
dem = count;
for (i=0;i<=1;i++)
{
a[pos]=i;
if (a[pos-1]==0 && a[pos]==1)
dem++;
if (pos == 10)
{
if (dem == 2)
printstr();
}
else
if (dem<3)
binary(n, pos+1, count);
dem = count;
}
}ý tưởng của mình thế này
dưới là code của mình, mình mới học CTDL & GT nên chỉ biết tới đó, bạn thông cảm 
#include<iostream>
using namespace std;
int a[100], n;
bool check = false;
void display(){
int dem = 0;
for (int i = 1; i <= n; i++){
if (a[i] == 0 && a[i + 1] == 1) dem++;
}
if (dem == 2){
for (int i = 1; i <= n; i++){
cout << a[i]<< "\t";
}
cout << endl;
}
}
void sinh(){
int i = n;
while (a[i] == 1 & i>0){
i--;
}
if (i == 0) check = true;
else
{
a[i] = 1;
for (int j = i + 1; j <= n; j++){
a[j] = 0;
}
}
}
void main(){
cout << " nhap chieu dai : ";
cin >>n;
for (int i = 1; i <= n; i++){
a[i] = 0;
}
while (!check){
display();
sinh();
}
system("pause");
}
ý tưởng của mình dùng quay lui 
các pác xem được không.
phát triển từ thuật toán quay lui liệt kê xâu nhị phân độ dài n .
Mỗi nghiệm thỏa mãn ghi vào mảng. sau đó thì kiểm tra nếu mak mảng thỏa mãn thì ghi ra kết quả.
Bài này có thể giải bằng cách sau:
Tạo một chỉnh hợp (hic, quên thuật ngữ toán là chỉnh hợp chặp gì gì đó rồi), của 0101, lặp cho 2 trường hợp tất cả các giá trị còn lại là 1 và trường hợp các giá trị còn lại là 0.
#include <iostream>
#include <cmath>
#include <vector>
void _to_bin(int num, std::vector<int> * out) {
if (num / 2)
_to_bin(num/2, out);
out->push_back(num % 2);
}
void to_bin(int num, int numDigit) {
std::vector<int> out;
_to_bin(num, &out);
for(int i = 0; i < numDigit - out.size(); ++i)
std::cout << 0;
for(int i = 0; i < out.size(); ++i)
std::cout << out.at(i);
std::cout << std::endl;
}
void to0101(int numDigit) {
// all 0
for(int fist_01_pos = 0; fist_01_pos < numDigit - 1; ++fist_01_pos) {
int mask = 0;
mask |= (1 << fist_01_pos);
for(int second_01_pos = 2 + fist_01_pos; second_01_pos < numDigit - 1; ++second_01_pos) {
int result = mask;
result |= (1 << second_01_pos);
to_bin(result, numDigit);
}
}
// all 1
for(int fist_01_pos = 0; fist_01_pos < numDigit - 1; ++fist_01_pos) {
// slow but short code to get all bits set to 1
int mask = (int)pow(2,numDigit) - 1;
mask ^= (2 << fist_01_pos);
for(int second_01_pos = 2 + fist_01_pos; second_01_pos < numDigit - 1; ++second_01_pos) {
int result = mask;
result ^= (2 << second_01_pos);
to_bin(result, numDigit);
}
}
}
int main() {
std::cout << std::endl << "5 digits" << std::endl << std::endl;
to0101(5);
std::cout << std::endl << "10 digits" << std::endl << std::endl;
to0101(10);
std::cout << std::endl << "15 digits" << std::endl << std::endl;
to0101(15);
return 0;
}
Kết quả chạy thử với n = 5, 10, 15
5 digits
00101
01001
01010
10101
01101
01011
10 digits
0000000101
0000001001
0000010001
0000100001
0001000001
0010000001
0100000001
0000001010
0000010010
0000100010
0001000010
0010000010
0100000010
0000010100
0000100100
0001000100
0010000100
0100000100
0000101000
0001001000
0010001000
0100001000
0001010000
0010010000
0100010000
0010100000
0100100000
0101000000
1111110101
1111101101
1111011101
1110111101
1101111101
1011111101
0111111101
1111101011
1111011011
1110111011
1101111011
1011111011
0111111011
1111010111
1110110111
1101110111
1011110111
0111110111
1110101111
1101101111
1011101111
0111101111
1101011111
1011011111
0111011111
1010111111
0110111111
0101111111
15 digits
000000000000101
000000000001001
000000000010001
000000000100001
000000001000001
000000010000001
000000100000001
000001000000001
000010000000001
000100000000001
001000000000001
010000000000001
000000000001010
000000000010010
000000000100010
000000001000010
000000010000010
000000100000010
000001000000010
000010000000010
000100000000010
001000000000010
010000000000010
000000000010100
000000000100100
000000001000100
000000010000100
000000100000100
000001000000100
000010000000100
000100000000100
001000000000100
010000000000100
000000000101000
000000001001000
000000010001000
000000100001000
000001000001000
000010000001000
000100000001000
001000000001000
010000000001000
000000001010000
000000010010000
000000100010000
000001000010000
000010000010000
000100000010000
001000000010000
010000000010000
000000010100000
000000100100000
000001000100000
000010000100000
000100000100000
001000000100000
010000000100000
000000101000000
000001001000000
000010001000000
000100001000000
001000001000000
010000001000000
000001010000000
000010010000000
000100010000000
001000010000000
010000010000000
000010100000000
000100100000000
001000100000000
010000100000000
000101000000000
001001000000000
010001000000000
001010000000000
010010000000000
010100000000000
111111111110101
111111111101101
111111111011101
111111110111101
111111101111101
111111011111101
111110111111101
111101111111101
111011111111101
110111111111101
101111111111101
011111111111101
111111111101011
111111111011011
111111110111011
111111101111011
111111011111011
111110111111011
111101111111011
111011111111011
110111111111011
101111111111011
011111111111011
111111111010111
111111110110111
111111101110111
111111011110111
111110111110111
111101111110111
111011111110111
110111111110111
101111111110111
011111111110111
111111110101111
111111101101111
111111011101111
111110111101111
111101111101111
111011111101111
110111111101111
101111111101111
011111111101111
111111101011111
111111011011111
111110111011111
111101111011111
111011111011111
110111111011111
101111111011111
011111111011111
111111010111111
111110110111111
111101110111111
111011110111111
110111110111111
101111110111111
011111110111111
111110101111111
111101101111111
111011101111111
110111101111111
101111101111111
011111101111111
111101011111111
111011011111111
110111011111111
101111011111111
011111011111111
111010111111111
110110111111111
101110111111111
011110111111111
110101111111111
101101111111111
011101111111111
101011111111111
011011111111111
010111111111111
Link chạy thử: http://ideone.com/kKpX0C
anh ơi còn trường hợp này thì sao
0000101111Ẹc, haha, tối qua về mắt nhắm mắt mở tính thử với trường hợp 5 số nên không tính tới cái này.
Nếu vậy thì phần all bit 0 và có 2 dãy 01 đã OK, còn lại phần nhét các số 1 vào nữa. ai làm thử đi 
#include <iostream>
#include <cmath>
#include <vector>
void _to_bin(int num, std::vector<int> * out) {
if (num / 2)
_to_bin(num / 2, out);
out->push_back(num % 2);
}
void to_bin(int num, int numDigit) {
std::vector<int> out;
_to_bin(num, &out);
for (int i = 0; i < numDigit - out.size(); ++i)
std::cout << 0;
for (int i = 0; i < out.size(); ++i)
std::cout << out.at(i);
std::cout << std::endl;
}
void set_bits(int* num, int numDigit) {
*num = 1;
for (int i = 1; i < numDigit; ++i)
*num = *num << 1 | 1;
}
void to0101(int numDigit) {
// all 0
for (int fist_01_pos = 0; fist_01_pos < numDigit - 1; ++fist_01_pos) {
int mask = 0;
mask |= (1 << fist_01_pos);
for (int second_01_pos = 2 + fist_01_pos; second_01_pos < numDigit - 1; ++second_01_pos) {
int result = mask;
result |= (1 << second_01_pos);
to_bin(result, numDigit);
}
}
// all 1 after right most 01
for (int fist_01_pos = 0; fist_01_pos < numDigit - 1; ++fist_01_pos) {
int mask = 0;
set_bits(&mask, fist_01_pos);
mask |= (1 << fist_01_pos);
for (int second_01_pos = 2 + fist_01_pos; second_01_pos < numDigit - 1; ++second_01_pos) {
int result = mask;
result |= (1 << second_01_pos);
to_bin(result, numDigit);
}
}
// all 1
for (int fist_01_pos = 0; fist_01_pos < numDigit - 1; ++fist_01_pos) {
int mask = 0;
set_bits(&mask, numDigit);
mask ^= (2 << fist_01_pos);
for (int second_01_pos = 2 + fist_01_pos; second_01_pos < numDigit - 1; ++second_01_pos) {
int result = mask;
result ^= (2 << second_01_pos);
to_bin(result, numDigit);
}
}
}
int main() {
std::cout << std::endl << "5 digits" << std::endl << std::endl;
to0101(5);
std::cout << std::endl << "10 digits" << std::endl << std::endl;
to0101(10);
std::cout << std::endl << "15 digits" << std::endl << std::endl;
to0101(15);
return 0;
}
Test thử
5 digits
00101
01001
01010
00101
01001
01011
10101
01101
01011
10 digits
0000000101
0000001001
0000010001
0000100001
0001000001
0010000001
0100000001
0000001010
0000010010
0000100010
0001000010
0010000010
0100000010
0000010100
0000100100
0001000100
0010000100
0100000100
0000101000
0001001000
0010001000
0100001000
0001010000
0010010000
0100010000
0010100000
0100100000
0101000000
0000000101
0000001001
0000010001
0000100001
0001000001
0010000001
0100000001
0000001011
0000010011
0000100011
0001000011
0010000011
0100000011
0000010111
0000100111
0001000111
0010000111
0100000111
0000101111
0001001111
0010001111
0100001111
0001011111
0010011111
0100011111
0010111111
0100111111
0101111111
1111110101
1111101101
1111011101
1110111101
1101111101
1011111101
0111111101
1111101011
1111011011
1110111011
1101111011
1011111011
0111111011
1111010111
1110110111
1101110111
1011110111
0111110111
1110101111
1101101111
1011101111
0111101111
1101011111
1011011111
0111011111
1010111111
0110111111
0101111111
15 digits
000000000000101
000000000001001
000000000010001
000000000100001
000000001000001
000000010000001
000000100000001
000001000000001
000010000000001
000100000000001
001000000000001
010000000000001
000000000001010
000000000010010
000000000100010
000000001000010
000000010000010
000000100000010
000001000000010
000010000000010
000100000000010
001000000000010
010000000000010
000000000010100
000000000100100
000000001000100
000000010000100
000000100000100
000001000000100
000010000000100
000100000000100
001000000000100
010000000000100
000000000101000
000000001001000
000000010001000
000000100001000
000001000001000
000010000001000
000100000001000
001000000001000
010000000001000
000000001010000
000000010010000
000000100010000
000001000010000
000010000010000
000100000010000
001000000010000
010000000010000
000000010100000
000000100100000
000001000100000
000010000100000
000100000100000
001000000100000
010000000100000
000000101000000
000001001000000
000010001000000
000100001000000
001000001000000
010000001000000
000001010000000
000010010000000
000100010000000
001000010000000
010000010000000
000010100000000
000100100000000
001000100000000
010000100000000
000101000000000
001001000000000
010001000000000
001010000000000
010010000000000
010100000000000
000000000000101
000000000001001
000000000010001
000000000100001
000000001000001
000000010000001
000000100000001
000001000000001
000010000000001
000100000000001
001000000000001
010000000000001
000000000001011
000000000010011
000000000100011
000000001000011
000000010000011
000000100000011
000001000000011
000010000000011
000100000000011
001000000000011
010000000000011
000000000010111
000000000100111
000000001000111
000000010000111
000000100000111
000001000000111
000010000000111
000100000000111
001000000000111
010000000000111
000000000101111
000000001001111
000000010001111
000000100001111
000001000001111
000010000001111
000100000001111
001000000001111
010000000001111
000000001011111
000000010011111
000000100011111
000001000011111
000010000011111
000100000011111
001000000011111
010000000011111
000000010111111
000000100111111
000001000111111
000010000111111
000100000111111
001000000111111
010000000111111
000000101111111
000001001111111
000010001111111
000100001111111
001000001111111
010000001111111
000001011111111
000010011111111
000100011111111
001000011111111
010000011111111
000010111111111
000100111111111
001000111111111
010000111111111
000101111111111
001001111111111
010001111111111
001011111111111
010011111111111
010111111111111
111111111110101
111111111101101
111111111011101
111111110111101
111111101111101
111111011111101
111110111111101
111101111111101
111011111111101
110111111111101
101111111111101
011111111111101
111111111101011
111111111011011
111111110111011
111111101111011
111111011111011
111110111111011
111101111111011
111011111111011
110111111111011
101111111111011
011111111111011
111111111010111
111111110110111
111111101110111
111111011110111
111110111110111
111101111110111
111011111110111
110111111110111
101111111110111
011111111110111
111111110101111
111111101101111
111111011101111
111110111101111
111101111101111
111011111101111
110111111101111
101111111101111
011111111101111
111111101011111
111111011011111
111110111011111
111101111011111
111011111011111
110111111011111
101111111011111
011111111011111
111111010111111
111110110111111
111101110111111
111011110111111
110111110111111
101111110111111
011111110111111
111110101111111
111101101111111
111011101111111
110111101111111
101111101111111
011111101111111
111101011111111
111011011111111
110111011111111
101111011111111
011111011111111
111010111111111
110110111111111
101110111111111
011110111111111
110101111111111
101101111111111
011101111111111
101011111111111
011011111111111
010111111111111
Link chạy thử: http://ideone.com/UAqSeq
Bài này tách hàm to0101 thành 3 hàm con để quản lý code tốt hơn, mà lười quá.
Ẹc, có bug, với n = 5 nó bị duplicate 
, đi công việc tối về xem.
Fixed, chỉnh lại vòng lặp thứ hai, loại bỏ trùng.
mình có ý tưởng cho bài này như sau :
** đây là code của mình viết bằng python :
def _list(conf , i) : # conf : ["x" , "0" , "1" , "x" , "0" , "1" , "x"]
# stop condition
if i == len(conf) :
print(" , ".join(conf))
return
if conf[i] != "x" :
_list(conf , i + 1)
return
# recursion body
config = list(conf).copy()
zero = one = True
if i > 0 :
if config[i - 1] == "0" :
one = False
if i < len(config) - 1:
if config[i + 1] == "1" :
zero = False
if zero :
config[i] = "0"
_list(config , i + 1)
if one :
config[i] = "1"
_list(config , i + 1)
def permute(conf , n) : # conf : [0 , 1] : vi tri cua 2 lan 01 xuat hien
if conf[1] < n - 2 : # ham nay la de tao ra cau hinh moi .
conf[1] += 1
elif conf[0] < n - 4 :
conf[0] += 1
conf[1] = conf[0] + 2
else :
return []
result = ["x"] * n
result[conf[0]] = result[conf[1]] = "0"
result[conf[0] + 1] = result[conf[1] + 1] = "1"
return result
def func(n) : # Liet ke day nhi phan n Bit (chi xuat hien 01 dung 2 lan)
if n < 4 :
return
conf = [0 , 1]
while True :
config = permute(conf , n)
if config :
_list(config , 0)
else :
break
func(5)Hi anh, phần này của anh vẫn chưa chính xác ạ.
Hi vọng anh có thể check lại.
Ví dụ: n = 7 thì có output như bên dưới.
Sẽ còn 1 só chuỗi thiếu như: 0101100, 0101110, 0111001, 0111010…
0000101
0001001
0010001
0100001
0001010
0010010
0100010
0010100
0100100
0101000
0001011
0010011
0100011
0010111
0100111
1110101
1101101
1011101
0111101
1101011
1011011
0111011
1010111
0110111
0101111
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?