Dans le programme C, traduisez la séquence Baum Sweet

Ici, nous verrons la séquence Baum Sweet. La séquence est une séquence binaire. Si le nombre n a un nombre impair de 0 consécutifs, alors le nième bit sera 0, sinon le nième bit sera 1.

Nous avons un nombre naturel n. Notre tâche est de trouver le nième terme de la séquence Baum Sweet. Il faut donc vérifier s’il comporte des blocs consécutifs de zéros de longueur impaire.

Si le nombre est 4, ce terme sera 1 car 4 vaut 100. Il y a donc deux zéros (pairs).

Algorithme

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

Exemple

#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);
}

Sortie

1

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!