C++ 2023年计算机学院”新生杯“ACM天梯赛周赛（一） 二进制转化的感悟

对于长度为 5 位的一个 01 串，每一位都可能是 0 或 1，一共有 32 种可能。它们的前几个是：

00000

00001

00010

00011

00100

请按从小到大的顺序输出这 32 种 01 串。

本试题没有输入。

输出 32 行，按从小到大的顺序每行一个长度为 5 的 01 串。

直接输出不得分。

 

 

 

 

 

#include <iostream>
using namespace std;
int main()
{
    for(int i=0;i<32;i++){
        cout<<i%32/16<<i%16/8<<i%8/4<<i%4/2<<i%2<<endl;
    }
    return 0;
}

 

这段代码使用了整数除法和取模运算，将一个整数表示为二进制数的形式输出。

 

 

#include <iostream>
#include <bitset>  // 引入 bitset 库

using namespace std;

int main()
{
    for (int i = 0; i < 32; i++)
    {
        bitset<5> b(i);  // 将整数转换成二进制数
        cout << b << endl;  // 输出二进制数
    }
    return 0;
}

 

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<int>& bits, int n, int idx) {
    if (idx == n) { // 递归边界，已经填满所有位
        for (int i = 0; i < n; ++i) {
            cout << bits[i];
        }
        cout << endl;
        return;
    }
    bits[idx] = 0; // 填 0
    dfs(bits, n, idx + 1);
    bits[idx] = 1; // 填 1
    dfs(bits, n, idx + 1);
}
int main() {
    const int n = 5; // 5 位二进制数
    vector<int> bits(n); // 存储二进制数
    dfs(bits, n, 0);
    return 0;
}

 

这里使用了深度优先搜索（DFS）来枚举所有 01 串。递归函数 dfs 的参数 bits 存储当前正在生成的二进制数，n 表示二进制数的位数，idx 表示正在填写的二进制数位的下标。

当递归到填满所有位时，即 idx == n，就输出当前二进制数。

否则，分别填入 0 和 1，然后继续递归填写下一位。

 

#include <iostream>
#include <string>
using namespace std;

string to_binary_string(int x) { // 将整数转换为 5 位二进制字符串
    string s(5, '0');
    for (int i = 4; i >= 0; --i) {
        if (x & 1) s[i] = '1';
        x >>= 1;
    }
    return s;
}

int main() {
    for (int i = 0; i < 32; ++i) {
        cout << to_binary_string(i) << endl;
    }
    return 0;
}

 

这里定义了一个 to_binary_string 函数，用来将整数转换为 5 位二进制字符串。函数中从右往左依次处理每一位二进制数，通过与 1 进行按位与运算，可以得到最低位的值，然后将整个数向右移位，再处理下一位。
在主函数中，通过循环调用 to_binary_string 函数输出所有的二进制数。