Gợi ý Thuật Toán Liệt Kê Các Dãy Nhị Phân độ Dài N Mà Trong đó Dãy ... Trang chủ » độ Dài Xâu Bit » Gợi ý Thuật Toán Liệt Kê Các Dãy Nhị Phân độ Dài N Mà Trong đó Dãy ... Có thể bạn quan tâm độ Dài Xâu C++ độ Dài Xâu Không Vượt Quá độ Dài Xâu Rỗng độ Dài Xâu Trong Pascal đổ đà Kiềng Nhà Cấp 4 Gợi ý thuật toán 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 programming algorithm Trung_Thao (Trung Thảo) June 4, 2021, 4:34pm #1 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 2 Likes ltd (Lê Trần Đạt) August 28, 2015, 1:43am #2 Vậy nếu n = 1 NA n = 2 01 N = 3 001 010 101 011 Phải không nhỉ? Trung_Thao (Trung Thảo) August 28, 2015, 1:47am #3 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 1 Like nguyenhuuca (Nguyen Ca) August 28, 2015, 1:50am #4 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 2 Likes ltd (Lê Trần Đạt) August 28, 2015, 2:09am #5 À, Đạ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 Trung_Thao: ví dụ: n = 5 thì ra có 00101 01001 01010 01011 10101 Nếu vậy dãy này bị thiếu rồi? Ví dụ thiếu 01101 1 Like Trung_Thao (Trung Thảo) August 28, 2015, 2:08am #6 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 1 Like ltd (Lê Trần Đạt) August 28, 2015, 2:10am #7 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 lvhero (Tôi là tôi) August 28, 2015, 2:16am #8 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. nguyenhuuca (Nguyen Ca) August 28, 2015, 2:22am #9 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 Trung_Thao (Trung Thảo) August 28, 2015, 2:26am #10 Đúng là nó hơi khó hiểu @lvhero, bạn có thể giải thích chi tiết hơn ko? Rok_Hoang (Minh Hoàng) September 6, 2015, 1:00am #11 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; } } 1 Like Trung_Thao (Trung Thảo) August 28, 2015, 2:27am #12 Cách này cũng hay bạn @nguyenhuuca. Thanks TTH (Kẻ Máu Lạnh) January 12, 2019, 6:07pm #13 ý 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<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"); } 3 Likes nghiakaka (Đào Trọng Nghĩa) September 4, 2015, 11:48am #14 ý 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ả. ltd (Lê Trần Đạt) September 4, 2015, 4:03pm #15 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 1 Like Rok_Hoang (Minh Hoàng) September 4, 2015, 5:58pm #16 anh ơi còn trường hợp này thì sao 0000101111 1 Like ltd (Lê Trần Đạt) September 5, 2015, 3:09am #17 Ẹ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. 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. 3 Likes Van_Huu (Văn Hữu) January 12, 2019, 3:59pm #18 mình có ý tưởng cho bài này như sau : đầu tiên cần 1 cấu hình là vị trí đặt 2 dãy “01” trong n bit : -> cấu hình đầu tiên sẽ là : [“0” , “1” ,“0” ,“1” , “x” , “x”] . ( x có thể thay = 0 hoặc = 1 . với 6 Bit) sau đó với mỗi cấu hình tạo ra được . ta lần lượt thử thay = 0 hoặc = 1 vào các vị trí 'x" ( mình dùng đệ quy quay lui) . với điều kiên : + thay = “0” chỉ khi bit sau nó khác 1. + thay = “1” chỉ khi bit trước nó khác 0. cứ như vậy đến khi hết cấu hình thì dừng . ** đâ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) 1 Like duccongnd9 (Duc Cong Tran) June 11, 2022, 5:48am #20 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 1 Like DayNhauHoc's Discord Học C++ Free? Click Blog Dạy Nhau Học Tự Học Lập Trình 83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao? Từ khóa » độ Dài Xâu Bit [Lời Giải]Tổng Hợp Các Bài Toán đếm Xâu [PDF] Trường đại Học Cần Thơ Khoa CNTT Và TT - Cit..vn Có Bao Nhiêu Xâu Nhị Phân độ Dài 5 Không Chứa 2 Bit 1 đứng Cạnh ... Có Bao Nhiêu Chuỗi Bit Có độ Dài 10 Chứa đúng Bốn Giây 1 Thuật Toán Đưa Ra Chuỗi Nhị Phân Độ Dài N - CodeLearn [PDF] Toán Rời Rạc – N.T.T.H - FITA-VNUA Giúp Em Với - VNOI Có đúng Hai Bít 0. Có Nghĩa Là Chuỗi Ln Có 2 Bit 0 Và Các Bit ... - 123doc [PDF] GIẢI BÀI TẬP TOÁN RỜI RẠC Số Xâu Nhị Phân độ Dài 4 Có Bít Cuối Cùng Bằng 1 Là: Có Bao Nhiêu Xâu Nhị Phân Có độ Dài Nhỏ Hơn Hoặc Bằng 6 Kết Thúc ... [PDF] TOÁN RỜI RẠC Có Bao Nhiêu Xâu Nhị Phân Có độ Dài N Trong đó Không Có Hai Bit 1 ... Có Bao Nhiêu Xâu Nhị Phân Có độ Dài Bằng 10 Và Có 5 Số 0 Liên Nhau ...
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?