ตัวเลข 1 ถึง n บิตโดยไม่มี 1s ติดต่อกันในการแสดงไบนารี?

ในปัญหานี้ เราต้องหาเลขฐานสองบางตัวที่ไม่มี 1s ติดต่อกัน ในสตริงไบนารี 3 บิต มีเลขฐานสองสามตัวคือ 011, 110, 111 ที่มีเลข 1 ติดต่อกัน และมีตัวเลขห้าตัวที่ไม่มีเลข 1 ที่ต่อเนื่องกัน ดังนั้นหลังจากใช้อัลกอริทึมนี้สำหรับตัวเลข 3 บิตแล้ว คำตอบจะเป็น 5

ถ้า a[i] เป็นเซตของเลขฐานสองซึ่งมีจำนวนบิตเป็น i และไม่มี 1s ติดต่อกัน และ b[i] คือเซตของเลขฐานสอง โดยที่จำนวนบิตคือ i และมี 1s ที่ต่อเนื่องกัน แล้วมีความสัมพันธ์ที่เกิดซ้ำเช่น −

a[i] := a[i - 1] + b[i - 1]

b[i] := a[i - 1]

อินพุต

อัลกอริทึมนี้ใช้จำนวนบิตสำหรับเลขฐานสอง ให้อินพุตเป็น 4

ผลลัพธ์

ส่งกลับจำนวนของสตริงไบนารีที่ไม่มี 1 ติดต่อกัน

ผลลัพธ์ที่ได้คือ − 8 (มี 8 สตริงไบนารีที่ไม่มี 1 ตัวต่อเนื่องกัน)

อัลกอริทึม

countBinNums(n)

Input: n is the number of bits.
Output: Count how many numbers are present which have no consecutive 1.
Begin
   define lists with strings ending with 0 and ending with 1
   endWithZero[0] := 1
   endWithOne[0] := 1
   for i := 1 to n-1, do
      endWithZero[i] := endWithZero[i-1] + endWithOne[i-1]
      endWithOne[i] := endWithZero[i-1]
   done
   return endWithZero[n-1] + endWithOne[n-1]
End

ตัวอย่าง

#include <iostream>
using namespace std;
int countBinNums(int n) {
   int endWithZero[n], endWithOne[n];
   endWithZero[0] = endWithOne[0] = 1;
   for (int i = 1; i < n; i++) {
      endWithZero[i] = endWithZero[i-1] + endWithOne[i-1];
      endWithOne[i] = endWithZero[i-1];
   }
   return endWithZero[n-1] + endWithOne[n-1];
}
int main(){
   int n;
   cout << "Enter number of bits: "; cin >> n;
   cout << "Number of binary numbers without consecutive 1's: "<<countBinNums(n) << endl;
   return 0;
}

ผลลัพธ์

Enter number of bits: 4
Number of binary numbers without consecutive 1's: 8