题目描述
对于长度为 5 位的一个 01 串,每一位都可能是 0 或 1,一共有 32 种可能。它们的前几个是:
00000
00001
00010
00011
00100
请按从小到大的顺序输出这 32 种 01 串。
输入格式
本试题没有输入。输出格式
输出 32 行,按从小到大的顺序每行一个长度为 5 的 01 串。样例输出
00000
00001
00010
00011
<以下部分省略>
提示/说明
直接输出不得分。 1.初学者的代码#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;
} 这段代码使用了整数除法和取模运算,将一个整数表示为二进制数的形式输出。 2.调用标准库中bitset类实现二进制和十进制转化。 #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;
} 3.使用深度优先搜索来枚举 #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,然后继续递归填写下一位。 4.只调用iostream的手动转化法 #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 函数输出所有的二进制数。 我们比较两种只调用iostream的方法,第一段代码使用了整数除法和取模运算,将一个整数表示为二进制数的形式输出。在运行效率方面,这段代码比使用逐位移位运算的代码效率要低,因为整数除法和取模运算的运算速度比逐位移位运算要慢。
但是在这个问题的输入规模比较小的情况下,即长度为 5 的 01 串,共 32 种可能的情况下,这段代码的运行时间较短,可以接受。
如果输入规模较大,例如长度为 20 的 01 串,共有 $2^{20}$ 种可能的情况,那么这段代码的运行时间会很长,不建议使用。 标签:return,idx,二进制,C++,int,赛周赛,ACM,include,bits From: https://www.cnblogs.com/Edward-Jie/p/17255131.html