题目描述
给定一个整数 、将 的 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 ,直到 。
部分代码如下:
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进制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
x = int(input()) for i in range(x): print("case #%d:" %i) print(int(str(bin(int(input())))[2::][::-1], 2))