题目描述

带注释

样例

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 将M进制数转化为N进制数
 */

/**
 * @brief M进制的除法，除以N,因为要转化成N进制
 * 求出除法的结果（直接影响原数组），返回余数
 * @param num_arr 
 */
int div_N(vector<int> &num_arr, int M, int N)
{
    int last_remain = 0; //上一位除法的余数,因为每一位除以被除数时，都会加上上一位除法的余数
                         //且上一位除法的余数还要乘以M
    for (int i = 0; i < num_arr.size(); i++)
    {
        int tmp = num_arr[i];
        num_arr[i] = (last_remain * M + tmp) / N;  //除法的整数位
        last_remain = (last_remain * M + tmp) % N; //除法的余数
    }
    return last_remain;
}

/**
 * @brief 检查数字数组是否全部为0，如果全部为0,说明转换已经完成
 * 
 * @param num_arr 
 * @return true 
 * @return false 
 */
bool is_allZero(vector<int> num_arr)
{

    for (size_t i = 0; i < num_arr.size(); i++)
    {
        if (num_arr[i] != 0)
        {
            return false;
        }
    }
    return true;
}

void solve(string str, int M, int N)
{
    string result = "";
    vector<int> num_arr; //存储每一个
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] <= '9')
        {
            num_arr.push_back(str[i] - '0');
        }
        else
        {
            num_arr.push_back(str[i] - 'A' + 10);
        }

        // cout << num_arr[i];
    }

    int tmp;
    while (true)
    {
        if (is_allZero(num_arr)) //如果数组全部为0了，说明已经结束了
        {
            break;
        }
        tmp = div_N(num_arr, M, N); //获取除法的余数，加入到结果中
        // cout << "tmp:" << tmp << endl;
        if (tmp <= 9)
        {
            result += char(tmp + '0');
        }
        else
        {
            result += char(tmp - 10 + 'a');
        }
    }
    if (result == "")
    {
        cout << "0";
    }
    else
    {
        reverse(result.begin(), result.end());
        cout << result;
    }
}

int main()
{
    int M, N;
    cin >> M >> N;
    string str;
    cin >> str;
    // cout << str.length();
    solve(str, M, N);
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla