解题思路

题目在说什么？

计算机只认二进制（只用 0 和 1），而人类习惯用十进制。这道题就是要把一个十进制整数转换成二进制数。

十进制转二进制的办法：除 2 取余法

比如把 13 转成二进制：

把余数从下往上倒着读，得到 1101，这就是 13 的二进制。

用程序怎么写？

1. 用一个数组 b 依次记录每次除 2 的余数；
2. 只要 n 还大于 0，就执行：b[k++] = n % 2（记余数），然后 n /= 2（去掉最低位）；
3. 当 n 变成 0 时停止，把数组里的余数倒过来输出。

别忘了特判 0！

如果输入的是 0，循环一次都不会执行，数组是空的。所以要在开头特判：n == 0 时直接输出 0。

参考代码

// P4506 改造计算机：十进制整数转二进制
#include <iostream>
using namespace std;
int main() {
    int n, b[35], k = 0;
    cin >> n;
    if (n == 0) { cout << 0 << endl; return 0; } // 特判：0的二进制就是0
    while (n > 0) {
        b[k++] = n % 2; // 不断取余数记录二进制位
        n /= 2;         // 去掉已经取出的最低位
    }
    for (int i = k - 1; i >= 0; i--) cout << b[i]; // 倒过来输出
    cout << endl;
    return 0;
}

复杂度分析

设要转换的十进制数是 n。

• 时间：n 每除以一次 2 就变小一半，循环的次数约等于 n 的二进制位数，也就是 log₂(n) 次，时间复杂度是 O(log₂n)；
• 空间：需要一个数组存二进制的每一位，空间复杂度是 O(log₂n)。