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

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

เราสามารถแก้ไขได้โดยใช้โปรแกรมไดนามิก สมมติว่าเรามีตาราง 'a' และ 'b' โดยที่ arr[i] เก็บจำนวนสตริงไบนารีที่มีความยาว i โดยที่ไม่มี 1s ต่อเนื่องกัน และลงท้ายด้วย 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

ตัวอย่าง

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