保研机试备考二：进制转换

AcWing 3373. 进制转换

题目

https://www.acwing.com/problem/content/3376/

思路

将一个长度最多为 30 位数字的十进制非负整数转换为二进制数输出。
这里数字的长度最多为30位，可以说是很长了，不能简单的用long long来存，要用高精度来存，数组模拟一下即可。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
vector<int> div(vector<int> a,int b)   //高精度除法
{
    vector<int> c;
    for(int i=a.size()-1,r=0;i>=0;i--)
    {
        r=r*10+a[i];
        c.push_back(r/b);
        r%=b;
    }
    reverse(c.begin(),c.end());
    while(c.size()&&c.back()==0) c.pop_back();
    return c;
}
int main()
{
    string s;
    while(cin>>s)
    {
        vector<int> a;
        for(int i=s.size()-1;i>=0;i--)
            a.push_back(s[i]-'0');   //倒着存
        if(s=="0") cout<<0<<endl;
        else
        {
            string res;
            while(a.size())
            {
                res+=to_string(a[0]%2);  //除以2的余数，最后一位即可决定了，先算好了放进去
                a=div(a,2);   //再除以2
            }
            reverse(res.begin(),res.end());  //位置要倒一下
            cout<<res<<endl;
        }
    }
    return 0;
}

AcWing 3374. 进制转换2

题目

https://www.acwing.com/problem/content/3377/

思路

将 M 进制的数 X 转换为 N 进制的数输出。

不需要把M进制的数先转换为10进制，再由10进制转化为N进制。
直接利用高精度除法，直接转化为对应进制。
把每一步的余数记录好就可以。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{   //处理输入
    int n,m;
    string s;
    cin>>n>>m>>s;

    vector<int> a;
    for(int i=s.size()-1;i>=0;i--)
    {   //倒着存，并且把字母换成数字
        char c=s[i];
        if(c>='A') a.push_back(c-'A'+10);
        else a.push_back(c-'0');
    }

    if(s=="0") cout<<0;   //特判0
    else
    {
        string res;
        while(a.size())
        {
            int r=0;   //余数，放到外面来定义，因为下面循环完了就是最终的余数
            for(int i=a.size()-1;i>=0;i--)
            {
                a[i]+=r*n;
                r=a[i]%m;
                a[i]/=m;
            }
            while(a.size()&&a.back()==0) a.pop_back();   //去除前导0
            //数字转字母
            if(r>=10) res+=r-10+'a'; 
            else res+=r+'0';
        }
        //调换顺序输出
        reverse(res.begin(),res.end());
        cout<<res;
    }
    return 0;
}