开发者社区> 游客z3jcatjk57fiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介: 二进制倒置
+关注继续查看

题目描述



image.png

题目链接

https://acm.ecnu.edu.cn/problem/3031/

题解



image.png

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 类型保存余数了。

部分代码如下:

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 。

部分代码如下:

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++

#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进制stringstring 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

x = int(input())for i in range(x):   
    print("case #%d:" %i)  
    print(int(str(bin(int(input())))[2::][::-1], 2))

image.png

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


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
各种Java实现的常用排序算法
各种Java实现的常用排序算法
24 0
除了闹过腥风血雨的fastjson,你还知道哪些Java解析JSON的利器?(1)
除了闹过腥风血雨的fastjson,你还知道哪些Java解析JSON的利器?
29 0
JAVA常见算法题(二十二)
package com.xiaowu.demo; //利用递归方法求5!。 public class Demo22 { public static void main(String[] args) { int n = 5; long s = sum(n); System.
641 0
JAVA常见算法题(一)
package com.xiaowu.demo; // 有一只兔子,从出生后第3个月起每个月都生一只兔子,小兔子长到第四个月后每个月又生一只兔子,假如兔子都不死,问每个月的兔子总数为多少? /** * * @author WQ * */ public class Demo...
481 0
jvm系列(三):java GC算法 垃圾收集器
GC算法 垃圾收集器 概述 垃圾收集 Garbage Collection 通常被称为“GC”,它诞生于1960年 MIT 的 Lisp 语言,经过半个多世纪,目前已经十分成熟了。 jvm 中,程序计数器、虚拟机栈、本地方法栈都是随线程而生随线程而灭,栈帧随着方法的进入和退出做入...
1281 0
JAVA算法系列 快速排序
java算法系列之排序 手写快排 首先说一下什么是快排,比冒泡效率要高,快排的基本思路是首先找到一个基准元素,比如数组中最左边的那个位置,作为基准元素key,之后在最左边和最右边设立两个哨兵,i 和 j 之后,开始按住左哨兵(i),让右哨兵(j)往左走(j--),找到比key小的元素后,按住右哨兵(...
800 0
Java利用IO流复制照片完整示例和详细分析
import java.io.FileInputStream; import java.io.FileOutputStream; /** * 该篇博客已经Deprecated,请参见I/O流的梳理和小结 * http://blog.
837 0
217
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载