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
Nach dem Login kopieren
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
Nach dem Login kopieren
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;
}
Nach dem Login kopieren
Ausgabe
The given number 10 is a Fibbinary Number
Nach dem Login kopieren
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
Nach dem Login kopieren
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;
}
Nach dem Login kopieren
Ausgabe
The given number 12 is not a Fibbnary Number
Nach dem Login kopieren
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!
