โปรแกรมนับจำนวนสตริงฐานสองที่ไม่มี 1 ติดกันใน C/C++

นี่คือปัญหาเชิงสนุกสนาน สมมติได้ค่า n ต้องหาสตริงความยาว n ทั้งหมดที่ไม่มี 1 ติดกัน ถ้า n = 2 ตัวเลขคือ {00, 01, 10} ผลลัพธ์คือ 3

แก้ได้ด้วย Dynamic Programming สมมติมีตาราง 'a' และ 'b' โดย a[i] เก็บจำนวนสตริงฐานสองความยาว i ไม่มี 1 ติดกัน และลงท้ายด้วย 0 b เก็บเหมือนกันแต่ลงท้ายด้วย 1 สามารถต่อ 0 หรือ 1 ได้ถ้าตัวสุดท้ายคือ 0 แต่ต่อแค่ 0 ถ้าตัวสุดท้ายคือ 1

อัลกอริทึม

noConsecutiveOnes(n) -

Begin
  define array a and b of size n
  a[0] := 1
  b[0] := 1
  for i in range 1 to n, do
    a[i] := a[i-1] + b[i - 1]
    b[i] := a[i - 1]
  done
  return a[n-1] + b[n-1]
End

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

#include 
using namespace std;
int noConsecutiveOnes(int n) {
    int a[n], b[n];
    a[0] = 1;
    b[0] = 1;
    for (int i = 1; i < n; i++) {
        a[i] = a[i-1] + b[i-1];
        b[i] = a[i-1];
    }
    return a[n-1] + b[n-1];
}
int main() {
    cout << noConsecutiveOnes(4) << endl;
}