C++ 代码
每次拿出A的末位,进行%2, 并且对A整体÷2
A整体÷2: 高精度除法 r表示上次运算的余数
考虑前导0的处理:
先翻转变为后导0, 只要后面不是最后一个1,就pop_back();
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> A,int b)
{
// 上次操作留下的余数
int r = 0;
vector<int> B;
for(int i =0; i < A.size();i++)
{
// 利用上次的余数
r = r*10+A[i];
B.push_back(r/b);
r = r%b;
}
// 但是可能有前导0
// 反转后, 0 跑到后面
reverse(B.begin(),B.end());
while(B.size() > 0 && B.back() == 0) B.pop_back();
//再翻转下,返回商
reverse(B.begin(),B.end());
return B;
}
int main()
{
string s;
while(cin >> s)
{
if(s == "0")
cout << "0" << endl;
else
{
vector<int> A;
//现存低位
for(int i = 0; i < s.size();i++)
A.push_back(s[i]-'0');
vector<int> binary;
while(A.size())
{
// 每次模2 除二
int idx = A.size()-1;
int t = A[idx]%2;
binary.push_back(t);
A = div(A,2);
}
for(int i = binary.size()-1 ;i >=0 ;i--)
cout << binary[i];
cout << endl;
}
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla