Рубрики

Baum Sweet Sequence

Последовательность Baum Sweet Sequence — это бесконечная двоичная последовательность из 0 и 1. N-й член последовательности равен 1, если число n не имеет нечетного числа смежных нулей в своем двоичном представлении, в противном случае n-й член равен 0.

The first few terms of the sequence are:
b1 = 1 (binary of 1 is 1)
b2 = 0 (binary of 2 is 10)
b3 = 1 (binary of 3 is 11)
b4 = 1 (binary of 4 is 100)
b5 = 0 (binary of 5 is 101)
b6 = 0 (binary of 6 is 110)

Дано натуральное число n . Задача состоит в том, чтобы найти n-й член последовательности Баума Свита, т.е. проверить, содержит ли он какой-либо последовательный блок нулей нечетной длины.

Input: n = 8
Output: 0
Explanations:
Binary representation of 8 is 1000. It 
contains odd length block of consecutive 0s. 
Therefore B8 is 0.

Input: n = 5
Output: 1

Input: n = 7
Output: 0

Идея состоит в том, чтобы запустить цикл через двоичное представление n и посчитать длину всех имеющихся последовательных нулевых блоков. Если имеется хотя бы один нулевой блок нечетной длины, то n-й член для данного входа n равен 0, иначе он равен 1.

// код CPP для поиска n-го члена
// Baum Sweet Sequence
#include <bits/stdc++.h>

using namespace std;

  

int nthBaumSweetSeq(int n)

{

    // bitset хранит побитовое представление

    bitset<32> bs(n);

  

    // len хранит количество бит в

    // двоичный код n. Встроенная функция () дает

    // количество нулей, присутствующих перед

    // ведущий 1 в двоичном из n

    int len = 32 - __builtin_clz(n);

  

    int baum = 1; // n-й член последовательности Баума

    for (int i = 0; i < len;) {

        int j = i + 1;

  

        // войти в нулевой блок

        if (bs[i] == 0) {

            int cnt = 1;

  

            // цикл для прохождения каждого нулевого блока

            // в двоичном представлении n

            for (j = i + 1; j < len; j++) {

  

                // считает нули подряд

                if (bs[j] == 0)                   

                    cnt++;

                else

                    break;

            }

  

            // проверяем номер последовательного

            // нули нечетные

            if (cnt % 2 == 1)

                baum = 0;

        }

        i = j;

    }

  

    return baum;

}

  
// Код драйвера

int main()

{

    int n = 8;

    cout << nthBaumSweetSeq(n);

    return 0;

}

Выход:

0

Рекомендуемые посты:

Baum Sweet Sequence

0.00 (0%) 0 votes