Biểu diễn số dưới dạng tổng các số giả nhị phân tối thiểu bằng C++

Số giả nhị phân (pseudo-binary) chỉ chứa chữ số 0 và 1 (vd: 1, 10, 11, 101...). Biểu diễn số N thành tổng số lượng ít nhất các số giả nhị phân. Ví dụ:

Input: 23 → 11 + 11 + 1 Input: 50 → 10 + 10 + 10 + 10 + 10

Thuật toán

Lặp cho đến khi N = 0:

• Tạo số X: mỗi chữ số của N ≠ 0 → đặt chữ số đó của X = 1, ngược lại = 0.
• X là một số giả nhị phân. In X.
• N = N - X.

Ví dụ

#include <iostream>
using namespace std;

int main() {
    int N = 51;
    cout << "pseudo-binary representation of " << N << " is: ";
    while (N > 0) {
        int temp = N, X = 0, bit = 1;
        while (temp != 0) {
            int last_dig = temp % 10;
            temp /= 10;
            if (last_dig != 0) X += bit;
            bit *= 10;
        }
        cout << X << " ";
        N -= X;
    }
    return 0;
}

Kết quả

pseudo-binary representation of 51 is: 11 10 10 10 10

Kết luận

Biểu diễn số thành tổng số lượng ít nhất các số giả nhị phân bằng thuật toán tham lam: mỗi lần trừ đi số giả nhị phân lớn nhất có thể. Code C++ O(N×số chữ số).