编程算法案例10
作者：championsky | 发布时间：
数制转换
1.问题描述
给定一个M进制的数x，实现对x向任意一个非M进制的数的转换。
2.问题分析
这是一个将M进制数转换为N进制数的问题，我们可以用除留余数法来解决这个问题。具体地，假设我们从M进制转换到N进制，先将M进制数转换为10进制数，然后从10进制数转换为N进制数，这样就完成了M进制数到N进制数的转换。具体的转换公式如下：
假设一个M进制数为x，需要将它转换为N进制数，转换过程如下：
-
将M进制数x转化为10进制数y，即
y = x0M^0 + x1M^1 + ... + xn*M^n
其中xi表示x在M进制下的第i位的数字，n是x的M进制下的位数。
-
将10进制数y转化为N进制数，具体方法如下：
从y的最低位开始，每次对N求余数，将得到的余数加入结果中，然后将y除以N取整，直到y变为0为止，此时得到的结果就是转化后的N进制数。
例如，将一个二进制数101101转换为八进制数，具体过程如下：
-
将二进制数101101转化为10进制数，即
y = 1 * 2^0 + 0 * 2^1 + 1 * 2^2 + 1 * 2^3 + 0 * 2^4 + 1 * 2^5
= 1 + 4 + 8 + 32
= 45 -
将10进制数45转化为八进制数，具体过程如下：
45 / 8 = 5 余 5，因此最低位为5；
5 / 8 = 0 余 5，因此第二位为5。因此，二进制数101101转换为八进制数为55。
3.算法设计
根据上述分析，我们可以使用以下算法来实现M进制数到N进制数的转换：
-
将M进制数x转换为10进制数y，具体方法为从x的最高位开始，依次计算每一位有权值得10进制数，然后将它们相加。
-
将10进制数y转换为N进制数z，具体方法为从y的最低位开始，依次计算每一位有权值的N进制数，然后将它们相加。
注意，对于M进制数和N进制数，我们可以使用字符串来表示，这样可以方便地处理每一位上的数字。
Python代码实现
def baseConversion(x: str, m: int, n: int) -> str:
def toDec(s: str, base: int) -> int:
"""将一个base进制数转换为10进制数"""
y = 0
for c in s:
y = y * base + int(c, base=base)
return y
def fromDec(y: int, base: int) -> str:
"""将一个10进制数转换为base进制数"""
s = ''
while y:
s = str(y % base) + s
y //= base
return s
return fromDec(toDec(x, m), n)该函数接受三个参数：x表示待转换的M进制数，m表示x的进制，n表示需要将x转换为的N进制数，函数返回转换后的N进制数。
在函数中，我们定义了两个辅助函数toDec和fromDec，用于将M进制数转换为10进制数以及将10进制数转换为N进制数。toDec函数从M进制数的最高位开始，累加每一位的权重，计算出对应的10进制数；fromDec函数则从10进制数的最低位开始，不断除以N并取余，将得到的余数添加到答案中，最后得到转换后的N进制数。
使用上述函数进行测试代码如下：
x = "101101"
m = 2
n = 8
print(baseConversion(x, m, n)) # 输出：55执行上述代码，将二进制数101101转换为八进制数，输出结果为55，可以看出该算法正确地实现了M进制数到N进制数的转换。
JAVA代码实现
public class BaseConversion {
/**
* 将一个base进制数转化为10进制数
*
* @param s base进制数
* @param base 进制
* @return 10进制数
*/
public static int toDec(String s, int base) {
int y = 0;
for (char c : s.toCharArray()) {
y = y * base + Character.digit(c, base);
}
return y;
}
/**
* 将一个10进制数转化为base进制数
*
* @param y 10进制数
* @param base 进制
* @return base进制数
*/
public static String fromDec(int y, int base) {
if (y == 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
while (y > 0) {
int r = y % base;
sb.append(Character.forDigit(r, base));
y /= base;
}
return sb.reverse().toString();
}
/**
* 将一个M进制数转换为N进制数
*
* @param x M进制数
* @param m M进制
* @param n N进制
* @return N进制数
*/
public static String baseConversion(String x, int m, int n) {
int dec = toDec(x, m);
return fromDec(dec, n);
}
public static void main(String[] args) {
String x = "101101";
int m = 2;
int n = 8;
System.out.println(baseConversion(x, m, n)); // 输出：55
}
}上述代码实现了三个辅助函数：toDec、fromDec和baseConversion。toDec函数用于将M进制数转换为10进制数，fromDec函数用于将10进制数转换为N进制数，baseConversion函数调用toDec和fromDec函数将M进制数转换为N进制数。在实现中，我们将M进制数和N进制数都用字符串来表示，并使用Integer.parseInt和Character.digit函数将字符转换为对应的数值。
在main函数中，我们使用实例数据进行测试，将二进制数101101转换为八进制数，输出结果为55，可以看出该算法正确地实现了M进制数到N进制数的转换。
C++代码实现
#include <iostream>
#include <string>
using namespace std;
/** 将字符转换为数值 */
int charToNum(char c, int base) {
if (c >= '0' && c <= '9') {
return (int)(c - '0');
} else if (c >= 'a' && c <= 'z') {
return (int)(c - 'a') + 10;
} else if (c >= 'A' && c <= 'Z') {
return (int)(c - 'A') + 10;
}
return -1;
}
/** 将数值转换为字符 */
char numToChar(int n, int base) {
if (n >= 0 && n <= 9) {
return (char)('0' + n);
} else if (n >= 10 && n <= 35) {
return (char)('a' + n - 10);
}
return ' ';
}
/** 将一个base进制数转化为10进制数 */
int toDec(string s, int base) {
int y = 0;
for (int i = 0; i < s.length(); i++) {
int n = charToNum(s[i], base);
if (n >= 0 && n < base) {
y = y * base + n;
} else {
return -1;
}
}
return y;
}
/** 将一个10进制数转化为base进制数 */
string fromDec(int y, int base) {
if (y == 0) {
return "0";
}
string s = "";
while (y > 0) {
int r = y % base;
char c = numToChar(r, base);
s = c + s;
y /= base;
}
return s;
}
/** 将一个M进制数转换为N进制数 */
string baseConversion(string x, int m, int n) {
int dec = toDec(x, m);
return fromDec(dec, n);
}
int main() {
string x = "101101";
int m = 2;
int n = 8;
cout << baseConversion(x, m, n) << endl; // 输出：55
return 0;
}
上述代码实现了三个辅助函数：charToNum、numToChar、toDec、fromDec和baseConversion。charToNum函数用于将字符转换为对应的数值，numToChar函数用于将数值转换为对应的字符，toDec函数用于将M进制数转换为10进制数，fromDec函数用于将10进制数转换为N进制数，baseConversion函数调用toDec和fromDec函数将M进制数转换为N进制数。
在main函数中，我们使用实例数据进行测试，将二进制数101101转换为八进制数，输出结果为55，可以看出该算法正确地实现了M进制数到N进制数的转换。