Nombres binaires de Fibonacci (pas de nombres consécutifs en binaire) - méthode O(1)

Les nombres fibbinaires sont des nombres qui n'ont pas de 1 consécutifs dans leur représentation binaire. Cependant, ils peuvent avoir des zéros consécutifs dans leur représentation binaire. La représentation binaire est une représentation qui affiche des nombres en base 2, avec seulement deux chiffres 1 et 0. Ici, nous recevrons un nombre et nous devrons déterminer si le nombre donné est un nombre fibbinaire.

Input 1: Given number: 10
Output: Yes

Explication - La représentation binaire du nombre 10 donné est 1010, ce qui montre qu'il n'y en a pas de consécutifs sous forme binaire.

Input 2: Given number: 12
Output: No

Explication - La représentation binaire du nombre donné est 1100, ce qui indique qu'il y a deux 1 consécutifs sous forme binaire.

Approche Naive

Approche Naive

Dans cette méthode, nous utiliserons la méthode de division pour trouver chaque bit et stocker le bit précédent en divisant par 2 pour obtenir les informations requises. Nous utiliserons une boucle while jusqu'à ce que le nombre actuel devienne zéro.

Nous allons créer une variable pour stocker le bit précédemment trouvé et l'initialiser à zéro. Si le bit actuel et le bit précédent sont tous deux égaux à 1, false est renvoyé, sinon nous répétons jusqu'à ce que la boucle soit terminée.

Après avoir terminé la boucle, nous retournerons vrai car aucun 1 consécutif n'a été trouvé. Jetons un coup d'œil au code −

Exemple

#include <iostream>
using namespace std;
bool isFibbinary(int n){
   int temp = n; // defining the temporary number 
   int prev = 0; // defining the previous number 
   while(temp != 0){
      // checking if the previous bit was zero or not
      if(prev == 0){
         // previous bit zero means no need to worry about current 
         prev = temp%2;
         temp /= 2;
      } else {
         // if the previous bit was one and the current is also the same return false
         if(temp%2 == 1){
            return false;
         } else {
            prev = 0;
            temp /=2;
         }
      }
   }
   // return true, as there is no consecutive ones present 
   return true;
}
// main function 
int main(){
   int n = 10; // given number 
   // calling to the function 
   if(isFibbinary(n)){
      cout<<"The given number "<< n<< " is a Fibbinary Number"<<endl;
   } else {
      cout<<"The given number "<< n << " is not a Fibbnary Number"<<endl;
   }
   return 0;
}

Sortie

The given number 10 is a Fibbinary Number

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(log(N)) car nous divisons le nombre actuel par 2 jusqu'à ce qu'il devienne zéro.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire ici.

Méthode efficace

Dans la méthode précédente, nous avons vérifié chaque bit un par un, mais il existe une autre façon de résoudre ce problème : le décalage de bits. Comme on sait que dans les nombres fibbinaires, deux bits consécutifs ne seront pas 1 en même temps, ce qui veut dire que si on décale tous les bits vers la gauche d'un bit, les bits du nombre précédent et du nombre courant seront à chaque fois position Ce ne sera plus jamais pareil.

Par exemple,

Si nous prenons le nombre donné comme 10, alors sa forme binaire sera 01010, en décalant le bit de 1 bit, nous obtiendrons le nombre 10100, nous pouvons voir que les deux nombres n'ont pas 1 bit à la même position.

C'est la propriété des nombres binaires de Fibonacci, pour le nombre n et le décalage gauche n, ils n'ont pas les mêmes bits, ce qui rend leur opérateur ET au niveau du bit nul.

n & (n << 1) == 0

Exemple

#include <iostream>
using namespace std;
bool isFibbinary(int n){
   if((n & (n << 1)) == 0){
      return true;
   } else{
      return false;
   }
}
// main function 
int main(){
   int n = 12; // given number 
   // calling to the function 
   if(isFibbinary(n)){
      cout<<"The given number "<< n<< " is a Fibbinary Number"<<endl;
   } else {
      cout<<"The given number "<< n << " is not a Fibbnary Number"<<endl;
   }
   return 0;
}

Sortie

The given number 12 is not a Fibbnary Number

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(1) car toutes les opérations sont effectuées au niveau du bit et il n'y a que deux opérations.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire ici.

Conclusion

Dans ce tutoriel, nous avons vu qu'un nombre fibbinaire est un nombre qui n'a pas de nombres consécutifs dans sa représentation binaire. Cependant, ils peuvent avoir des zéros consécutifs dans leur représentation binaire. Nous avons implémenté deux méthodes ici, l'une utilise la méthode de division par 2, qui a une complexité temporelle de O(log(N)) et une complexité spatiale de O(1), et l'autre utilise le décalage à gauche et au niveau du bit. de l’opérateur ET.

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!