Binary String คือ สตริงที่ประกอบด้วย 0 และ 1 หาจำนวน Binary String ความยาว n ที่ไม่มี 1 ติดกัน
ตัวอย่าง n=5: Strings ที่ผ่าน: 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10001, 10010, 10100, 10101 (รวม 13)
วิธี Generate ทั้งหมดแล้ว Filter ไม่มีประสิทธิภาพ วิธีดีกว่า: Recursion ที่แต่ละขั้นตอน Append 0 หรือ 1 แต่ Append 1 ได้ก็ต่อเมื่อตัวสุดท้ายเป็น 0 เท่านั้น
Input: n = 5 Output: Number of 5-digit binary strings without any consecutive 1's are 13
ตัวอย่าง
#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
if (n == 0) return 0;
if (n == 1) {
if (last_digit) return 1;
else return 2;
}
if (last_digit == 0)
return countStrings(n - 1, 0) + countStrings(n - 1, 1);
else
return countStrings(n - 1, 0);
}
int main() {
int n = 5;
cout << "Number of " << n << "-digit binary strings without any consecutive 1's are " << countStrings(n, 0);
return 0;
}