In the C program, translate the Baum Sweet sequence

Here we will see the Baum Sweet sequence. The sequence is a binary sequence. If the number n has an odd number of consecutive 0s, then the nth bit will be 0, otherwise the nth bit will be 1.

We have a natural number n. Our task is to find the nth term of the Baum Sweet sequence. So we have to check if it has consecutive blocks of zeros of odd length.

If the number is 4, this entry will be 1 because 4 is 100. So it has two (even) zeros.

Algorithm

BaumSweetSeqTerm (G, s) -

begin
   define bit sequence seq of size n
   baum := 1
   len := number of bits in binary of n
   for i in range 0 to len, do
      j := i + 1
      count := 1
      if seq[i] = 0, then
         for j in range i + 1 to len, do
            if seq[j] = 0, then
               increase count
            else
               break
            end if
         done
         if count is odd, then
            baum := 0
         end if
      end if
   done
   return baum
end

Example

#include <bits/stdc++.h>
using namespace std;
int BaumSweetSeqTerm(int n) {
   bitset<32> sequence(n); //store bit-wise representation
   int len = 32 - __builtin_clz(n);
   //builtin_clz() function gives number of zeroes present before the first 1
   int baum = 1; // nth term of baum sequence
   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) // counts consecutive zeroes
               count++;
            else
               break;
         }
         if (count % 2 == 1) //check odd or even
            baum = 0;
      }
      i = j;
   }
   return baum;
}
int main() {
   int n = 4;
   cout << BaumSweetSeqTerm(n);
}

Output

1

The above is the detailed content of In the C program, translate the Baum Sweet sequence. For more information, please follow other related articles on the PHP Chinese website!