首页 > 编程语言 >C++ 2023年计算机学院”新生杯“ACM天梯赛周赛(一) 二进制转化的感悟

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

时间:2023-03-25 17:23:25浏览次数:51  
标签:return idx 二进制 C++ int 赛周赛 ACM include bits

题目描述

对于长度为 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

相关文章

  • c++ linux 编译 静态库 ,动态库
                        一起编译:  静态路径要用全路径    静态编译       规范写法  ......
  • linux c++编译
                gcc-v查看版本                     指定名字    多文件编译 ......
  • c++的内存补齐
    数据类型占用的字节数:char1short2int4longlong8当我们需要进行内存补齐的时候,是看最大类型然后进行补齐。structtest{shorta;shortb;c......
  • 【C++】类与对象理解和学习(中)
    六大默认成员函数前言每个类中都含有六大默认成员函数,也就是说,即使这个类是个空类,里面什么都没有写,但是编译器依然会自动生成六个默认成员函数,可以说它们六个是祖师爷钦点的......
  • DP 新疆大学ACM-ICPC程序设计竞赛五月月赛(同步赛)勤奋的杨老师
    链接:https://www.nowcoder.com/acm/contest/116/C来源:牛客网时间限制:C/C++1秒,其他语言2秒空间限制:C/C++32768K,其他语言65536K64bitIO......
  • C++餐厅点餐结算系统[2023-03-25]
    C++餐厅点餐结算系统[2023-03-25]题目某餐馆根据实际需要欲开发一套《餐厅点餐结算系统》,具体要求如下:1、系统用户包括消费者、收银员、厨师、服务员、餐厅老板、系统......
  • c++union用法
    参考文章:c++中union的使用  union使用方法union即为联合,它是一种特殊的类。通过关键字union进行定义,一个union可以有多个数据成员。在任意时刻,联合中只能有一个数据成......
  • DolphinDB C++ API 数据写入使用指南
    本文为DolphinDBC++API(连接器)写入接口的使用指南,用户在有数据写入需求时,可以根据本篇教程快速明确地选择写入方式。本文将从使用场景介绍、原理简述、函数使用、场景实......
  • C/C++文档编辑器的设计与实现[2023-03-24]
    C/C++文档编辑器的设计与实现[2023-03-24]程序设计题三:文档编辑器的设计与实现1.系统的基本功能该系统要求对一个文本文件中的内容进行各种常规操作,如:插入、删除、查找......
  • const在c语言和c++中的区别
    1.c语言中的const变量 c语言中const变量是只读变量,有自己的存储空间2.c++中的const常量可能分配存储空也可能不分配存储空间当const常量为全局,并且需要......