Đếm cặp số 0 liên tiếp trong dãy sinh tự động trong C++

Có trình sinh dãy bắt đầu từ 1. Mỗi bước: 0→10, 1→01. Các bước đầu:

• Bước 1: 01
• Bước 2: 1001
• Bước 3: 01101001
• Bước 4: 1001011001101001
• Bước 5: 01101001100101101001011001101001

Quan sát: dãy lặp lại theo chu kỳ 12 ký tự, mỗi chu kỳ có 2 cặp "00". Số cặp 0 liên tiếp ở bước S: tmp = 2^S / 12, pairs = 1 + 2*tmp (trừ trường hợp S≤3).

Ví dụ

Đầu vào − steps = 5

Đầu ra − 5

Giải thích − tmp = 32/12 = 2, pairs = 1 + 2*2 = 5.

Đầu vào − steps = 10

Đầu ra − 171

Giải thích − tmp = 1024/12 = 85, pairs = 1 + 2*85 = 171.

Phương pháp giải

• Nếu steps <= 1 → 0.
• Nếu steps == 2 hoặc 3 → 1.
• Ngược lại: tmp = pow(2, steps) / 12, count = 2*tmp + 1.

Ví dụ code

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

int Zero_pairs(int decimal) {
    int count = 0;
    if (decimal <= 1) count = 0;
    else if (decimal == 2 || decimal == 3) count = 1;
    else {
        int temp = (pow(2, decimal) / 12);
        count = 2 * temp + 1;
    }
    return count;
}

int main() {
    int decimal = 7;
    cout << "Count of Pairs Of Consecutive Zeros are: " << Zero_pairs(decimal);
    return 0;
}

Đầu ra

Count of Pairs Of Consecutive Zeros are: 21