算法 大数任意进制转换
博客地址：
大数进制转换
写算法题的时候经常会碰到一些大数相关的问题，比如大数乘法、大数加法等等，乘法和加法的原理基本上都比较符合正常的思维模式，因为加法和乘法的原理相对清晰，模拟数学计算步骤可以方便地分离，并转换为代码。
相对于常见的加法和乘法，进制转换出现的频率低一些，但同样是一个十分值得探讨的问题，并且难度较之加法和乘法更高。
问题抽象
输入为(M, m, n):
M: m进制整数，用字符串类型string储存
m: 大数基数m
n: 大数目的基数n
输出为N：
N: n进制整数，用字符串类型string储存
数学原理
m进制转换成n进制，通常采用的是「模n取余法」，一般数进制转换的方法：
# num为输入数
result = []
temp = num
while temp0:
reminder = temp % to_base
quotient = temp // to_base
result.append(reminder)
temp = quotient
reverse(result)
eg.
30 / 2 = 15, 0
15 / 2 = 7, 1
7 / 2 = 3, 1
3 / 2 = 1, 11 / 2 = 0, 1
第一次的商被用作第二次的除数，循环直至商为0，先余为低位，后余为高位，转换后的数为余数组的逆序。
可以想象，大数转换步骤同样如此。
问题只在于大数的整除和取余，这里直接将算法解释如下：
quotient = []
temp = 0
for i in big_num:# 从大数中取位，取至最后一位循环停止
temp *= src_base# 余数乘以原基数
temp += i# 并加上当前位
if tempto_base: # 如果该数小于目标基数，商位上0
quotient.append(0)
continue
else# 如果该数大于目标基数，上商，余数留给下一次运算
quotient.append(temp / to_base)
temp %= to_base
reminder = temp
quotient = remove_front_zero(quotient)
eg.
| 序号 | 当前位 | 运算| 商| 余数 |
| ---- | ------ | ----------------------- | ---- | ---- |
| 0| null| null| null | 0|
| 1| 1| (0 * 2 + 1) / 10 = 0, 1 | 0| 1|
| 2| 1| (1 * 2 + 1) / 10 = 0, 3 | 0| 3|
| 3| 1| (3 * 2 + 1) / 10 = 0, 7 | 0| 7|
| 4| 1| (7 * 2 + 1) / 10 = 1, 5 | 1| 5|
| 5| 0| (5 * 2 + 0) / 10 = 1, 1 | 1| 0|
故0b11110 / 10 = 0b00011 = 0b11，余数为0
将0b11用作下一次循环的运算数
| 序号 | 当前位 | 运算| 商| 余数 |
| ---- | ------ | ----------------------- | ---- | ---- |
| 0| null| null| null | 0|
| 1| 1| (0 * 2 + 1) / 10 = 0, 0 | 0| 1|
| 2| 1| (1 * 2 + 1) / 10 = 0, 3 | 0| 3|
故0b11 / 10 = 0b000 = 0，余数为3
循环结束，得到余数组`03`,逆序后得到进制转换后的数`30`
代码实现
这里给出C++的算法实现，使用了大量内置的STL，如不能使用STL库可自行实现相关类型。
/**
* Created by Leslie
* 2020-03-28
*/
#include string
#include iostream
#include vector
#include algorithm
using namespace std;
/**
* Mapping a n-base number to a int number
* @param c the n-base number
* return the int number
*/
int GetValue(char c) {
if (c = 0c = 9) {
return c - 0;
}
if (c = ac = z) {
return c - a + 10;
}
if (c = Ac = A) {
return c - A + 36;
}
return -1;
}
/**
* Convert a big num between different base.
* @param a the string of big num
* @param src_base the base of origin number,
* @param to_base
* @return the sring of big num in src_base
*/
string BaseConvert(string a, int src_base, int to_base = 10) {
if (src_base2 || src_base62 || to_base2 || to_base62) {
return reinterpret_castconst char *(1);
}
char num_alpha[] = 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ;
int temp = 0;
vectorint number, quotient, result;
string s;
// 将字母映射为数字
for (char c : a) {
number.push_back(GetValue(c));
}
auto iter = number.begin();
while (!number.empty()) {
// 得到余数和商
while (iter != number.end()) {
temp *= src_base;
temp += *iter++;
if (tempto_base) {
quotient.push_back(0);
continue;
} else {
quotient.push_back(temp / to_base);
temp %= to_base;
}
}
// 得到余数，存入result
result.push_back(temp);
// 清空商的前置0
auto i = quotient.begin();
while (*i == 0i != quotient.end()) { i++; }
if (i != quotient.begin()) {
quotient.erase(quotient.begin(), i);
}
// 将商作为下一次的运算数，重置商数组和temp
number = quotient;
quotient.clear();
iter = number.begin();
temp = 0;
}
// 逆序余数位
reverse(result.begin(), result.end());
// 将数字映射为字母
for (int i:result) {
s += num_alpha[i];
}
return s;
}
int main() {
coutBaseConvert(11110, 2, 10)endl;
coutBaseConvert(30, 10, 2)endl;
return 0;
}
(111110)2,转成十进制是多少?,进制转换算法
进制转换：111110(二进制) = 62(十进制)。
具体算法如下：
二进制转为十进制的时候，先把二进制从高位（最左边的“1”）开始按从上到下的顺序写出 ，第一位就是最后的商，其他位数如果有“1”（原来的余数），就先乘以“2”再加“1”。
所以111110=1×2+1×4+1×8+1×16+1×32=2+4+8+16+32=62。
进制转换 以下 十六进制
#includeiostream//栈+进制转换 （16）
#includecstdio
#includecstring
using namespace std;
int main()
{
int top=0,d;n
int s[10];
int n;
cinnd;
while(top0)
{
if(s[top]=10)
{
if(s[top]==10)
coutA;
if(s[top]==11)
coutB;
if(s[top]==12)
coutC;
if(s[top]==13)
coutD;
if(s[top]==14)
coutE;
if(s[top]==15)
coutF;
}
else couts[top];
top--;
}
return 0;
}
#includeiostream//栈+进制转换 （16-10版）
#includecstdio
#includecstring
using namespace std;
int main()
{
char a[10]={A,B,C,D,E,F};
int top=0,d;
int s[10];
int n;
cinnd;
while(n!=0)
{
top++;
s[top]=n%d;
n=n/d;
}
while(top0)
{
if(s[top]=10)
{
couta[s[top]-10];
}
else couts[top];
top--;
}
return 0;
}
|算法、大数任意进制转换
string 以下 十六进制 大数任意进制转换 算法 转成十进制是多少? 进制转换 进制转换算法