Đếm số N chữ số có số lượng chữ số 0 lẻ trong C++

Cho số N. Đếm các số có N chữ số (cho phép số 0 dẫn đầu) mà có số lượng chữ số 0 là số lẻ. Ví dụ N=3: từ 000 đến 999.

Ví dụ

Đầu vào: N = 3
Đầu ra: 244.

Đầu vào: N = 5
Đầu ra: 33616.

Giải thuật (Toán học)

Tổng số N chữ số: T = 10^N (từ 0 đến 10^N-1).
Số N chữ số có số 0 chẵn: E = (10^N + 8^N) / 2.
Số N chữ số có số 0 lẻ: O = (10^N - 8^N) / 2.
(Công thức suy ra từ hàm sinh hoặc quy hồi).

Ví dụ triển khai

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

int count_odd(int N) {
    int total = pow(10, N);
    int even = pow(8, N);
    int odd = (total - even) / 2;
    return odd;
}

int main() {
    int N = 4;
    cout << "Count of Numbers with N digits which consists of odd number of 0's are: " << count_odd(N);
    return 0;
}

Kết quả

Count of Numbers with N digits which consists of odd number of 0's are: 2952