前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日算法系列【EOJ 3031】二进制倒置

每日算法系列【EOJ 3031】二进制倒置

作者头像
godweiyang
发布2020-03-24 10:59:02
4680
发布2020-03-24 10:59:02
举报
文章被收录于专栏:算法码上来

题目描述

给定一个整数 、将 的 334 位二进制表示形式(不包括开头可能的值为 0 的位, 表示为 1 位 0)前后倒置,输出倒置后的二进制数对应的整数。

例如: ,其二进制表示为(330 个 0)1010 ,倒置后为 0101 ,对应输出就是 5 。

题目链接 https://acm.ecnu.edu.cn/problem/3031/

题解

这题考查的主要是大数的进制转换,其他没有什么算法技巧,但是对代码实现要求还是挺高的,适合用来锻炼你的耐心代码风格

整体思路非常简单,不就是先把输入的 10 进制数 转化成 2 进制数 ,再把 所有位颠倒过来,最后再把 转化成 10 进制输出就行了。

所以整体代码拆分成了三步,先从 10 进制转 2 进制,再颠倒 2 进制,最后从 2 进制转 10 进制。

为了代码的普适性,我这里直接实现了从任意 进制 转化为任意 进制的算法,这样更加方便调用。

这就涉及到了大数的任意进制转换问题,假设 是 进制数,我们要把它转化为 进制的 (初始时为空)。那么转化步骤如下:

  • 求 ,并把余数接在 的最高位。
  • 令 。
  • 重复步骤 1 ,直到 。

部分代码如下:

代码语言:javascript
复制
while (n > 0) {
    y.push_back(mod(x, a, b));
    div(x, a, b);
    n = x.size();
    if (n == 1 && !x[0]) break;
}

看起来非常简单,但是步骤 1 和 2 都涉及到了大数的求余大数的除法算法,所以我们还得实现这两个算法。

大数求余只要从 最高位开始计算 的大小,并同时对 求余,然后由于求余的加法和乘法定理,我们可以始终保持 ,这样就能用一个 int 类型保存余数了。

部分代码如下:

代码语言:javascript
复制
int mod(vector<int>& x, int a, int b) {
    int n = x.size(), q = 0;
    for (int i = n-1; i >= 0; --i) {
        q = (q * a + x[i]) % b;
    }
    return q;
}

大数除法类似,从 最高位开始除 ,并注意要把余数带到下一位,最后还得去掉前导 0 。

部分代码如下:

代码语言:javascript
复制
void div(vector<int>& x, int a, int b) {
    int n = x.size(), q = 0;
    for (int i = n-1; i >= 0; --i) {
        x[i] += q * a;
        q = x[i] % b;
        x[i] /= b;
    }
    for (int i = n-1; i > 0; --i) {
        if (x[i]) break;
        x.pop_back();
    }
}

代码

c++

代码语言:javascript
复制
#include <bits/stdc++.h>
using namespace std;

// string转化为vector<int>,倒序存储
vector<int> s2i(string& s) {
    vector<int> x;
    int idx = 0, n = s.size();
    for (; idx < n; ++idx) {
        if (s[idx] != '0') break;
    }
    if (idx == n) idx = n - 1;
    for (int i = n-1; i >= idx; --i) {
        x.push_back(s[i]-'0');
    }
    return x;
}

// a进制下x%b,x倒序存储
int mod(vector<int>& x, int a, int b) {
    int n = x.size(), q = 0;
    for (int i = n-1; i >= 0; --i) {
        q = (q * a + x[i]) % b;
    }
    return q;
}

// a进制下x/b,x倒序存储
void div(vector<int>& x, int a, int b) {
    int n = x.size(), q = 0;
    for (int i = n-1; i >= 0; --i) {
        x[i] += q * a;
        q = x[i] % b;
        x[i] /= b;
    }
    for (int i = n-1; i > 0; --i) {
        if (x[i]) break;
        x.pop_back();
    }
}

// a进制下s转化为b进制string
string convert(string s, int a, int b) {
    vector<int> x = s2i(s);
    int n = x.size();
    vector<int> y;
    while (n > 0) {
        y.push_back(mod(x, a, b));
        div(x, a, b);
        n = x.size();
        if (n == 1 && !x[0]) break;
    }
    int m = y.size();
    string res = "";
    for (int i = m-1; i >= 0; --i) {
        res += '0' + y[i];
    }
    return res; 
}

int main() {
    int T;
    cin >> T;
    string x;
    for (int t = 0; t < T; ++t) {
        cin >> x;
        string x2 = convert(x, 10, 2);
        reverse(x2.begin(), x2.end());
        string res = convert(x2, 2, 10);
        cout << "case #" << t << ":" << endl;
        cout << res << endl;
    }
    return 0;
}

python

代码语言:javascript
复制
x = int(input())
for i in range(x):
    print("case #%d:" %i)
    print(int(str(bin(int(input())))[2::][::-1], 2))

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-02-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法码上来 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题解
  • 代码
    • c++
      • python
      相关产品与服务
      NLP 服务
      NLP 服务(Natural Language Process,NLP)深度整合了腾讯内部的 NLP 技术,提供多项智能文本处理和文本生成能力,包括词法分析、相似词召回、词相似度、句子相似度、文本润色、句子纠错、文本补全、句子生成等。满足各行业的文本智能需求。
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档