Nombor binari Fibonacci (tiada yang berturutan dalam binari) - kaedah O(1).

Nombor Fibbinary ialah nombor yang tidak mempunyai 1 berturut-turut dalam perwakilan binarinya. Walau bagaimanapun, mereka boleh mempunyai sifar berturut-turut dalam perwakilan binari mereka. Perwakilan binari ialah perwakilan yang memaparkan nombor menggunakan asas 2, dengan hanya dua digit 1 dan 0. Di sini kita akan diberikan nombor dan perlu menentukan sama ada nombor yang diberikan adalah nombor fibbinari.

Input 1: Given number: 10
Output: Yes

Penjelasan - Perwakilan binari bagi nombor 10 yang diberikan ialah 1010, yang menunjukkan bahawa tiada yang berturutan dalam bentuk binari.

Input 2: Given number: 12
Output: No

Penjelasan − Perwakilan binari bagi nombor yang diberi ialah 1100, yang menunjukkan bahawa terdapat dua 1 berturut-turut dalam bentuk binari.

Terjemahan bahasa Cina bagi

Pendekatan Naif

ialah:

pendekatan naif

Dalam kaedah ini kita akan menggunakan kaedah bahagi untuk mencari setiap bit dan menyimpan bit sebelumnya dengan membahagikan dengan 2 untuk mendapatkan maklumat yang diperlukan. Kami akan menggunakan gelung sementara sehingga nombor semasa menjadi sifar.

Kami akan mencipta pembolehubah untuk menyimpan bit yang ditemui sebelum ini dan memulakannya kepada sifar. Jika kedua-dua bit semasa dan bit sebelumnya adalah 1, false dikembalikan, jika tidak, kita ulangi sehingga gelung selesai.

Selepas melengkapkan gelung, kami akan kembali benar kerana tiada 1 berturut-turut ditemui. Mari lihat kod −

Contoh

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

Output

The given number 10 is a Fibbinary Number

Kerumitan Masa dan Ruang

Kerumitan masa kod di atas ialah O(log(N)) kerana kita membahagikan nombor semasa dengan 2 sehingga ia menjadi sifar.

Kerumitan ruang kod di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan di sini.

kaedah yang cekap

Dalam kaedah sebelum ini, kami menyemak setiap bit satu persatu, tetapi ada cara lain untuk menyelesaikan masalah ini, iaitu sedikit beralih. Seperti yang kita tahu bahawa dalam nombor Fibbinary, dua bit berturut-turut tidak akan menjadi 1 pada masa yang sama, yang bermaksud bahawa jika kita mengalihkan semua bit ke kiri dengan satu bit, bit nombor sebelumnya dan nombor semasa akan berada pada setiap kedudukan Ia tidak akan pernah sama.

Sebagai contoh,

Jika kita mengambil nombor yang diberikan sebagai 10, maka bentuk binarinya akan menjadi 01010, dengan mengalihkan bit sebanyak 1 bit, kita akan mendapat nombor 10100, kita dapat melihat bahawa kedua-dua nombor itu tidak mempunyai 1 dalam sama. kedudukan Bit.

Ini adalah sifat nombor perduaan Fibonacci, untuk nombor n dan anjakan kiri n, mereka tidak mempunyai bit yang sama, menjadikan operator bit DAN operator sifar.

n & (n << 1) == 0

Contoh

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

Output

The given number 12 is not a Fibbnary Number

Kerumitan Masa dan Ruang

Kerumitan masa kod di atas ialah O(1) kerana semua operasi dilakukan pada tahap bit dan hanya terdapat dua operasi.

Kerumitan ruang kod di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan di sini.

KESIMPULAN

Dalam tutorial ini, kita telah melihat bahawa nombor Fibbinari ialah nombor yang tidak mempunyai nombor yang berturutan dalam perwakilan binarinya. Walau bagaimanapun, mereka boleh mempunyai sifar berturut-turut dalam perwakilan binari mereka. Kami telah melaksanakan dua kaedah di sini, satu menggunakan kaedah bahagi dengan 2, yang mempunyai kerumitan masa O(log(N)) dan kerumitan ruang O(1), dan satu lagi menggunakan anjakan kiri dan bitwise Sifat daripada operator DAN.

Atas ialah kandungan terperinci Nombor binari Fibonacci (tiada yang berturutan dalam binari) - kaedah O(1).. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!