นับสตริงไบนารีที่มีบิต 1 ติดกัน K ครั้งใน C++

เราได้รับจำนวนเต็ม N และ K มีสตริงไบนารีความยาว N ประกอบด้วย 0 และ 1 เท่านั้น เป้าหมายคือหาจำนวนสตริงที่มีความยาว N ที่มีบิต 1 ติดกัน K ครั้ง (เช่น N=3, K=2 นับสตริง 3 ตัวที่มี 1 ติดกัน 2 ครั้ง)

ตัวอย่าง − 111 มี 1 ติดกัน 2 ครั้ง (K=2) ใน 011 และ 110 มี 1 ติดกัน 1 ครั้งเท่านั้น

เราแก้ปัญหานี้ด้วยการเก็บผลลัพธ์ค่าก่อนหน้า (Dynamic Programming) ใช้陣列 3 มิติ count[x][y][z] โดย x = N, y = K, z = ตัวเลขสุดท้ายของสตริง (0 หรือ 1)

• N=1 สตริงคือ "0" และ "1" จำนวน 1 ติดกัน = 0 ดังนั้น count[1][K][0] = count[1][K][1] = 0
• เมื่อตัวสุดท้ายเป็น 0: count[N][K][0] = count[N-1][K][0] + count[N-1][K][1]
• เมื่อตัวสุดท้ายเป็น 1: count[N][K][1] = count[N-1][K][0] + count[N-1][K-1][1]
• ผลรวม = count[N][K][0] + count[N][K][1]

อินพุต

N=4, K=2

เอาต์พุต

Count of strings: 2

คำอธิบาย − 1110, 0111 คือสตริงความยาว 4 ที่มี 1 ติดกัน 2 ครั้งเท่านั้น

อินพุต

N=3, K=1

เอาต์พุต

Count of strings: 2

คำอธิบาย − 110, 011 มี 1 ติดกัน 1 ครั้ง ส่วน 111 มี 2 ครั้ง

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• จำนวนเต็ม N และ K เก็บความยาวสตริงและจำนวนครั้งที่ 1 ติดกัน
• ฟังก์ชัน stringcount(int n, int k) คืนค่าจำนวนสตริง
• ใช้陣列 count[i][j][0/1] เก็บจำนวนสตริงความยาว i มี 1 ติดกัน j ครั้ง จบด้วย 0 หรือ 1
• เงื่อนไขเริ่มต้น count[1][0][0] = 1, count[1][0][1] = 1
• ลูปจากความยาว 2 ถึง n สำหรับแต่ละ j จาก 0 ถึง k อัปเดตค่า count[i][j][0] และ count[i][j][1]
• หาก j-1 >= 0 อัปเดต count[i][j][1] เพิ่ม count[i-1][j-1][1]
• ผลลัพธ์ = count[n][k][0] + count[n][k][1]

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

#include <bits/stdc++.h>
using namespace std;

int stringcount(int n, int k) {
    int count[n + 1][k + 1][2] = {0};
    count[1][0][0] = 1;
    count[1][0][1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
            count[i][j][1] = count[i - 1][j][0];
            if (j - 1 >= 0)
                count[i][j][1] += count[i - 1][j - 1][1];
        }
    }
    int result = count[n][k][0] + count[n][k][1];
    return result;
}

int main() {
    int N = 6, K = 3;
    cout << "Strings of length 6 and 3 adjacent 1's in each: " << stringcount(N, K);
    return 0;
}

ผลลัพธ์

Strings of length 6 and 3 adjacent 1's in each: 7