จำนวนเต็มไม่ติดลบไม่มี 1 ติดกัน (Non-negative Integers without Consecutive Ones) ใน C++

ภาพรวมปัญหา

กำหนดจำนวนเต็มบวก n หาจำนวนจำนวนเต็มไม่ติดลบ ≤ n ที่ตัวแทนไบนารีไม่มี 1 ติดกัน ตัวอย่าง: n=7 → คำตอบ 5 (0,1,2,4,5 = 0,1,10,100,101)

แนวทางแก้ปัญหา (Fibonacci + Bit DP)

• แปลง n เป็นสตริงบิต (LSB first)
• ones[i], zeroes[i] = จำนวนสตริงบิตความยาว i+1 ที่ลงท้ายด้วย 1, 0 ตามลำดับ ไม่มี 11
• zeroes[i] = zeroes[i-1] + ones[i-1], ones[i] = zeroes[i-1] (Fibonacci)
• รวม zeroes[n-1] + ones[n-1] แล้วลบกรณีที่เกิน n โดยดูบิตของ n

ตัวอย่างโปรแกรม

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

class Solution {
public:
    string convert(int n) {
        string ret = "";
        while(n) {
            ret += (n % 2) + '0';
            n >>= 1;
        }
        return ret;
    }
    
    int findIntegers(int num) {
        string bits = convert(num);
        int n = bits.size();
        vector<int> ones(n), zeroes(n);
        ones[0] = zeroes[0] = 1;
        
        for(int i = 1; i < n; i++) {
            zeroes[i] = zeroes[i - 1] + ones[i - 1];
            ones[i] = zeroes[i - 1];
        }
        
        int ret = ones[n - 1] + zeroes[n - 1];
        for(int i = n - 2; i >= 0; i--) {
            if(bits[i] == '0' && bits[i + 1] == '0') ret -= ones[i];
            else if(bits[i] == '1' && bits[i + 1] == '1') break;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << (ob.findIntegers(7));
}

Input

7

Output

5