Dãy Baum-Sweet trong C

Dãy Baum-Sweet: số tự nhiên n, nếu biểu diễn nhị phân có khối 0 liên tiếp lẻ thì bit thứ n = 0, ngược lại = 1.

Ví dụ: 4 = 100 (2 số 0 liên tiếp - chẵn) -> bit = 1.

Thuật toán

BaumSweetSeqTerm(n)
    bitset<32> sequence(n)
    len = 32 - __builtin_clz(n)
    baum = 1
    VỚI i = 0 ĐẾN len
        NẾU sequence[i] == 0
            ĐẾM count SỐ 0 LIÊN TIẾP TỪ i
            NẾU count LẺ -> baum = 0
        i = j (vị trí sau khối 0)
    TRẢ VỀ baum

Chương trình C++ ví dụ

#include <bits/stdc++.h>
using namespace std;

int BaumSweetSeqTerm(int n) {
    bitset<32> sequence(n);
    int len = 32 - __builtin_clz(n);
    int baum = 1;
    for (int i = 0; i < len; ) {
        int j = i + 1;
        if (sequence[i] == 0) {
            int count = 1;
            for (j = i+1; j < len; j++) {
                if (sequence[j] == 0) count++;
                else break;
            }
            if (count % 2 == 1) baum = 0;
        }
        i = j;
    }
    return baum;
}

int main() { cout << BaumSweetSeqTerm(4); }

Kết quả

1