หาจำนวนสตริงไบนารีความยาว N ที่มี 1 ติดต่อกันอย่างน้อย 3 ตัวใน C++

สมมติว่าเรามีจำนวนเต็ม N เราต้องหาจำนวนสตริงไบนารีที่เป็นไปได้ทั้งหมดที่มีความยาว N ซึ่งมี 1 ติดต่อกันอย่างน้อย 3 ตัว ดังนั้นถ้า n = 4 ตัวเลขจะเป็น 0111, 1110, 1111 ดังนั้นผลลัพธ์คือ 3

เพื่อแก้ปัญหานี้ เราสามารถใช้แนวทาง Dynamic Programming (การเขียนโปรแกรมแบบไดนามิก) ได้ DP(i, x) บ่งบอกจำนวนสตริงความยาว i ที่มี 1 ติดต่อกัน x ตัวในตำแหน่ง i+1 ถึง i+x ความสัมพันธ์แบบเรียกซ้ำจะเป็นดังนี้:

DP(i, x) = DP(i – 1, 0) + DP(i – 1, x + 1)

ความสัมพันธ์นี้อิงจากข้อเท็จจริงที่ว่าสตริงอาจมี 0 หรือ 1 อยู่ที่ตำแหน่ง i

• ถ้ามี 0 ที่ดัชนี i แล้วสำหรับตำแหน่ง (i – 1) ค่าของ x = 0
• ถ้ามี 1 ที่ดัชนี i แล้วสำหรับตำแหน่ง (i – 1) ค่าของ x = 1 + ค่าของ x ที่ตำแหน่ง i

ตัวอย่าง

#include <iostream> 
using namespace std; 

int n;
int numberCount(int i, int x, int table[][4]) {
    if (i < 0)
        return x == 3;
    if (table[i][x] != -1)
        return table[i][x];
    table[i][x] = numberCount(i - 1, 0, table);
    table[i][x] += numberCount(i - 1, x + 1, table);
    return table[i][x];
}

int main() {
    n = 4;
    int table[n][4];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            table[i][j] = -1;
    for (int i = 0; i < n; i++) {
        table[i][3] = (1 << (i + 1));
    }
    cout << "The number of binary strings with at least 3 consecutive 1s: " << numberCount(n - 1, 0, table);
}

ผลลัพธ์

The number of binary strings with at least 3 consecutive 1s: 3