Fibonacci-Binärzahlen (keine aufeinanderfolgenden Einsen im Binärformat) – O(1)-Methode

Fibbinäre Zahlen sind Zahlen, die in ihrer binären Darstellung keine aufeinanderfolgenden Einsen haben. Allerdings können sie in ihrer binären Darstellung aufeinanderfolgende Nullen haben. Die binäre Darstellung ist eine Darstellung, die Zahlen zur Basis 2 mit nur zwei Ziffern 1 und 0 anzeigt. Hier erhalten wir eine Zahl und müssen feststellen, ob es sich bei der angegebenen Zahl um eine fibbinäre Zahl handelt.

Input 1: Given number: 10
Output: Yes

Erklärung – Die binäre Darstellung der gegebenen Zahl 10 ist 1010, was zeigt, dass es in der binären Form keine aufeinanderfolgenden Einsen gibt.

Input 2: Given number: 12
Output: No

Erläuterung − Die binäre Darstellung der angegebenen Zahl ist 1100, was darauf hinweist, dass es in der binären Form zwei aufeinanderfolgende Einsen gibt.

Die chinesische Übersetzung von „Naiver Ansatz“ lautet: „Naiver Ansatz“.

Bei dieser Methode verwenden wir die Divisionsmethode, um jedes Bit zu finden und das vorherige Bit zu speichern, indem wir durch 2 dividieren, um die erforderlichen Informationen zu erhalten. Wir werden eine While-Schleife verwenden, bis die aktuelle Zahl Null wird.

Wir erstellen eine Variable, um das zuvor gefundene Bit zu speichern und es auf Null zu initialisieren. Wenn sowohl das aktuelle als auch das vorherige Bit 1 sind, wird false zurückgegeben, andernfalls wiederholen wir den Vorgang, bis die Schleife abgeschlossen ist.

Nach Abschluss der Schleife geben wir true zurück, da keine aufeinanderfolgende 1 gefunden wurde. Werfen wir einen Blick auf den Code −

Beispiel

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

Ausgabe

The given number 10 is a Fibbinary Number

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(log(N)), da wir die aktuelle Zahl durch 2 dividieren, bis sie Null wird.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir hier keinen zusätzlichen Speicherplatz verwenden.

Effiziente Methode

Bei der vorherigen Methode haben wir jedes Bit einzeln überprüft, aber es gibt eine andere Möglichkeit, dieses Problem zu lösen, und das ist die Bitverschiebung. Da wir wissen, dass in fibbinären Zahlen zwei aufeinanderfolgende Bits nicht gleichzeitig 1 sind, bedeutet dies, dass, wenn wir alle Bits um ein Bit nach links verschieben, die Bits der vorherigen Zahl und der aktuellen Zahl jeweils gleich sind Position Es wird nie mehr dasselbe sein.

Zum Beispiel

Wenn wir die gegebene Zahl als 10 annehmen, dann ist ihre Binärform 01010. Durch Verschieben des Bits um 1 Bit erhalten wir die Zahl 10100. Wir können sehen, dass beide Zahlen nicht 1 Bit an derselben Position haben.

Dies ist die Eigenschaft von Fibonacci-Binärzahlen. Für die Zahl n und die Linksverschiebung n haben sie nicht die gleichen Bits, sodass ihr bitweiser UND-Operator Null ist.

n & (n << 1) == 0

Beispiel

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

Ausgabe

The given number 12 is not a Fibbnary Number

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(1), da alle Operationen auf Bitebene ausgeführt werden und es nur zwei Operationen gibt.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir hier keinen zusätzlichen Speicherplatz verwenden.

Fazit

In diesem Tutorial haben wir gesehen, dass eine Fibbinärzahl eine Zahl ist, die in ihrer binären Darstellung keine aufeinanderfolgenden Einsen hat. Allerdings können sie in ihrer binären Darstellung aufeinanderfolgende Nullen haben. Wir haben hier zwei Methoden implementiert: Eine verwendet die Methode „Teilen durch 2“, die eine zeitliche Komplexität von O (log (N)) und eine räumliche Komplexität von O (1) aufweist, und die andere verwendet Linksverschiebung und bitweise Eigenschaften des UND-Operators.

Das obige ist der detaillierte Inhalt vonFibonacci-Binärzahlen (keine aufeinanderfolgenden Einsen im Binärformat) – O(1)-Methode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!