นับสตริงไบนารีที่ไม่มี 1 ติดกัน (Count Binary Strings without Consecutive 1's)

หาจำนวนสตริงไบนารีความยาว n ที่ไม่มีเลข 1 ติดกัน ตัวอย่าง n=3: มี 011, 110, 111 ที่มี 1 ติดกัน → เหลือ 5 สตริงที่ไม่มี 1 ติดกัน

กำหนด a[i] = จำนวนสตริง i บิตที่จบด้วย 0 และไม่มี 1 ติดกัน
b[i] = จำนวนสตริง i บิตที่จบด้วย 1 และไม่มี 1 ติดกัน

ความสัมพันธ์แบบเรียกซ้ำ:
a[i] = a[i-1] + b[i-1]
b[i] = a[i-1]

การรับค่าและแสดงผล

Input: จำนวนบิต = 4
Output: Number of binary numbers without consecutive 1's: 8

อัลกอริทึม

countBinNums(n)

Begin
  กำหนดอาร์เรย์ endWithZero และ endWithOne
  endWithZero[0] := 1, endWithOne[0] := 1
  
  for i := 1 ถึง 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

ตัวอย่างโค้ด (C++)

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

ผลลัพธ์

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