鲍姆斯威特序列-yiteyi-C++库

鲍姆斯威特序列是0和1的无限二进制序列。如果数字n在二进制表示中没有奇数个连续零，则序列的第n项为1，否则第n项为0。

null

The first few terms of the sequence are:
b₁ = 1 (binary of 1 is 1)
b₂ = 0 (binary of 2 is 10)
b₃ = 1 (binary of 3 is 11)
b₄ = 1 (binary of 4 is 100)
b₅ = 0 (binary of 5 is 101)
b₆ = 0 (binary of 6 is 110)

给定一个自然数 N .任务是找到Baum-Sweet序列的第n项，即检查它是否包含奇数长度的连续零块。

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

Input: n = 5
Output: 0

Input: n = 7
Output: 1

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

其思想是在n的二进制表示中运行一个循环，并计算所有连续零块的长度。如果至少有一个奇数长度的零块，那么给定输入n的第n项为0，否则为1。

                     // CPP code to find the nth term of the                   
                     // Baum Sweet Sequence                   
                     #include <bits/stdc++.h>                   
                     using                               namespace                               std;                   
                             
                     int                               nthBaumSweetSeq(                               int                               n)                   
                     {                   
                                         // bitset stores bitwise representation                   
                                         bitset<32> bs(n);                   
                             
                                         // len stores the number of bits in the                   
                                         // binary of n. builtin_clz() function gives                   
                                         // number of zeroes present before the                   
                                         // leading 1 in binary of n                   
                                         int                               len = 32 - __builtin_clz(n);                   
                             
                                         int                               baum = 1;                               // nth term of baum sequence                   
                                         for                               (                               int                               i = 0; i < len;) {                   
                                         int                               j = i + 1;                   
                             
                                         // enter into a zero block                   
                                         if                               (bs[i] == 0) {                   
                                         int                               cnt = 1;                   
                             
                                         // loop to run through each zero block                   
                                         // in binary representation of n                   
                                         for                               (j = i + 1; j < len; j++) {                   
                             
                                         // counts consecutive zeroes                   
                                         if                               (bs[j] == 0)                   
                                         cnt++;                   
                                         else                   
                                         break                               ;                   
                                         }                   
                             
                                         // check if the number of consecutive                   
                                         // zeroes is odd                   
                                         if                               (cnt % 2 == 1)                   
                                         baum = 0;                   
                                         }                   
                                         i = j;                   
                                         }                   
                             
                                         return                               baum;                   
                     }                   
                             
                     // Driver Code                   
                     int                               main()                   
                     {                   
                                         int                               n = 8;                   
                                         cout << nthBaumSweetSeq(n);                   
                                         return                               0;                   
                     }                   

输出：

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章