30/09/2018, 17:58
Xin gợi ý thuật toán: 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
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
Bài liên quan
Vậy nếu
n = 1
n = 2
N = 3
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
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
Đúng là nó hơi khó hiểu @lvhero, bạn có thể giải thích chi tiết hơn ko?
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”.
Cách này cũng hay bạn @nguyenhuuca. Thanks
ý tưởng của mình thế này
tìm tất cả các xâu nhị phân có độ dài là n.
khi in ra cấu hình thì sẽ dùng 1 biến dem để check xem có thỏa mãn điều kiện cụm"01" có xuất hiện 2 lần hay không.
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
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.
Kết quả chạy thử với n = 5, 10, 15
Link chạy thử: http://ideone.com/kKpX0C
anh ơi còn trường hợp này thì sao
Ẹ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
Test thử
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.
Ideone.com
Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.