Xin ý tưởng về thuật toán liệt kê dãy nhị phân

#1

a/c cho em xin ý tưởng về thuật toán bài này được không ạ:

Hãy liệt kê tất cả các xâu nhị phân có độ dài 𝑛 sao cho mỗi xâu nhị phân có duy nhất một dãy 𝑘 bít 1 liên tiếp.

#2

Có phải input và output là như vầy không ta.
Input:

n = 4
k = 2

Output

1100, 0110, 0011

2 Likes
#3

đúng rồi bạn ơi…

#4

Ý tưởng là vầy
Đầu tiên tìm k chữ số 1 (vd: k = 2 thì được 11, k = 3 thì được 111)
Dịch trái (n -k) lần để được tất cả các trường hợp còn lại.

Result 
#include <stdio.h>

//assumes little endian
void printBits(size_t const size, void const * const ptr) {
    unsigned char *b = (unsigned char *) ptr;
    unsigned char byte;
    int i, j;

    for (i = size - 1; i >= 0; i--) {
        for (j = 7; j >= 0; j--) {
            byte = (b[i] >> j) & 1;
            printf("%u", byte);
        }
    }
    puts("");
}

int main() {
    int n, k, data, i, remain_bits;

    printf("Nhap n: ");
    scanf("%d", &n);
    printf("Nhap k (k <= %d): ", n);
    scanf("%d: ", &k);
    printf("n: %d, k: %d\n", n, k);

    /*
     k = 1 -> data = 1
     k = 2 -> data = 11
     k = 3 -> data = 111
     */
    i = 0;
    data = 0;
    while (i < k) {
        data = data | (1 << i);
        i++;
    }
    //printf("data: ");
    //printBits(sizeof(data), &data);

    /*
     n = 4
     k = 2
     => remain_bits = 4 - 2 = 2 (+ 1)
     */
    remain_bits = n - k + 1;
    for (i = 0; i < remain_bits; i++) {
        int result = (data << i) | 0x0;
        printBits(sizeof(result), &result);
    }

    return 0;
}
3 Likes
#5

Thế kết quả là như này thì có đúng yêu cầu/điều kiện đề không nhỉ?
IP:

n = 4
k = 2

OP:

1100
1101 <---
0110
0011
1011 <---
1 Like
#6

Theo như đề thì là được á Situ ca. :slight_smile:

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?