题目要求

将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。

输入格式

输入包含多组测试数据。

每组测试数据占一行,包含一个长度不超过30位的十进制非负整数。

输出格式

每组数据输出一个结果,占一行,为输入对应的二进制数。

数据范围

输入最多包含100组测试数据。

示例输入:

0
1
3
8

示例输出:

0
1
11
1000

题目分析

高精度算法

代码实现

#include <iostream>
using namespace std;

string n;
string operator>>(const string& s, int a) {
    string ans;
    int t = 0;
    for (const auto& ch : s) {
        t = t * 10 + (ch - '0');
        ans += ((t >> a) + '0');
        t
    }
    while (ans.size() > 1 && *ans.begin() == '0') ans.erase(ans.begin());
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin >> n) {
        if (n != "0") {
            stack <int> st;
            while(n != "0") {
                st.push((*(n.end() - 1) - '0') & 1);
                n = n >> 1;
            }
            while(st.size()) {
                cout << st.top(); st.pop();
            }
        }  
        else cout << 0;
        cout << '\n';
    }
    return 0;
}

题目要求

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

输入格式

  • 第一行包括两个整数:M 和 N。
  • 第二行包含一个数 X,X 是 M 进制的数,现在要求你将 M 进制的数 X 转换成 N 进制的数输出。

输出格式

共一行,输出 X 的 N 进制表示。

数据范围

  • 2 ≤ N, M ≤ 36
  • X 最多包含 100 位。

在输入中,当某一位数字的值大于 10(十进制下)时,我们用大写字母 A ∼ Z,分别表示(十进制下的)数值 10 ∼ 35。

在输出中,当某一位数字的值大于 10(十进制下)时,我们用小写字母 a ∼ z,分别表示(十进制下的)数值 10 ∼ 35。

示例输入:

10 2
11

示例输出:

1011

题目分析

高精度算法 秦九韶算法 短除法 Py

有两种解决办法:

  1. M 进制转 10 进制 再转 N 进制。
  2. M 进制直接转 N 进制。

代码实现

C++
法1:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

string s;
int n, m;
string operato
    int t = 0;
    for (const auto& ch : a)
        t = (t * 10 + (ch - '0'))
    return to_string(t);
}
string operator/ (const string& a, int b) {
    string ans;
    int r = 0;
    for (auto i : a) {
        r = r * 10 + (int)(i - '0');
        ans += (char)((r / b) + '0');
        r
    }
    while (ans.size() > 1 && *ans.begin() == '0') ans.erase(ans.begin());
    return ans;
}
std::string operator*(std::string& A, std::string& B) {
    if (A == "0" || B == "0") return "0";
    std::string ans;
    std::vector <int> a, b, c;
    c.resize((int)A.length() + (int)B.length() + 2);
    for (auto i = A.rbegin(); i != A.rend(); ++i) a.push_back((int)(*i - '0'));
    for (auto i = B.rbegin(); i != B.rend(); ++i) b.push_back((int)(*i - '0'));
    for (int i = 0; i < (int)a.size(); ++i) {
        for (int j = 0; j < (int)b.size(); ++j) {
            c[i + j] += a[i] * b[j];
            c[i + j + 1] += c[i + j] / 10;
            c[i + j]
        }
    }
    for (auto i = c.rbegin(); i != c.rend(); ++i) ans += (char)(*i + '0');
    while (!(int)(*ans.begin() - '0')) ans.erase(ans.begin());
    return ans;
}
string operator+(string a, string b) {
    if (a.length() < b.length()) return b + a;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string ans;
    int t = 0;
    for (int i = 0; i < a.length(); ++i) {
        t += a[i] - '0';
        if (i < b.length()) t += b[i] - '0';
        ans.push_back(t
        t /= 10;
    }
    if (t) ans.push_back(t + '0');
    reverse(ans.begin(), ans.end());
    return ans;
}
string solve() {
    string buf = "0", ans = "";
    for (auto& ch : s) {
        string temp = to_string(m);
        buf = buf * temp;
        buf = (buf + to_string((ch >= 'A' && ch <= 'Z') ? 10 + ch - 'A' : ch - '0'));
    }
    while (buf != "0") {
        string temp = buf
        int val = stoi(temp);
        if (val > 9) ans += (char)('a' + val - 10);
        else ans += temp;
        buf = buf / n;
    }
    reverse(ans.begin(),ans.end());
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n >> s;
    cout << solve();
    return 0;
}
法2:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
char ch;
vector <int> a, b;
int operato
    int t = 0;
    for (const auto& i : a) {
        t = t * n + i;
        t
    }
    return t;
}
vector <int> operator/(vector <int>& a, int b) {
    vector <int> ans;
    int t = 0;
    for (const auto& i : a) {
        t = t * n + i;
        ans.push_back(t / b);
        t
    }
    while(ans.size() > 1 && !*ans.begin()) ans.erase(ans.begin());
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    while(cin >> ch) a.push_back((ch >= 'A' && ch <= 'Z') ? 10 + ch - 'A' : ch - '0');
    while(a.size() != 1 || a[0]) {
        b.push_back(a
        a = a / m;
    }
    reverse(b.begin(),b.end());
    for (const auto& in : b)
        cout << (char)(in > 9 ? 'a' + in - 10 : in + '0');
    return 0;
}
Py
def base_conversion(M, N, X):
    decimal_x = int(X, M)
    result = str(base10_to_baseN(decimal_x, N))
    return result

def base10_to_baseN(x, N):
    if x == 0:
        return '0'
    result = ''
    while x > 0:
        x, remainder = divmod(x, N)
        if remainder < 10:
            result = str(remainder) + result
        else:
            result = chr(ord('a') + remainder - 10) + result
    return result

M, N = map(int, input().split())
X = input().strip()

result = base_conversion(M, N, X)
print(result)
分类: Thought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status