这种题也是一道经典的面试题,主要考察进制转换细想,Coding质量等。
当我们把十进制转成二进制的时候,我们通过辗转相除,取余,逆置余数序列的过程得到新的进制的数。因此我们可以借助这种思想把M进制转成N进制的数。
如下是C的详细的实现方法:
void m2n(int m, char* mNum, int n, char* nNum)
{
int i = 0;
char c, *p = nNum;
//这是一个考察地方,是否能用最少乘法次数。
while (*mNum != \'\\0\')
i = i*m + *mNum++ - \'0\';
//辗转取余
while (i) {
*p++ = i % n + \'0\';
i /= n;
}
*p-- = \'\\0\';
//逆置余数序列
while (p > nNum) {
c = *p;
*p-- = *nNum;
*nNum++ = c;
}
}
观察上面的代码,存在着众多的不足。例如,要对输入参数做检查,数值的大小收到int值最大值的限制等。不过好在一点,该算法的时间复杂度是O(n)的。
但是我们霹雳无敌的赵大叔又提供了一种用Java实现的通用的进制转换方法,即使Windows的计算器也转不了的大数,这个算法也可以转。算和上面的算法相比,他的基本思想不变,还是辗转除,但是用了字符串做大数相除,很不错的创新点,赞一个。代码如下:
package test;
/**
* 功能:将一个数从M进制转换成N进制
* MValue:M进制数的字符串表示方法
* Shang:保存中间运算结果
* M:M进制
* N:N进制
*/
public class M2N {
// 在这里对输入赋值
public static String MValue = "1231412423534674574757";
public static String Shang = null;
public static int M = 10;
public static int N = 8;
public static void main(String[] args) {
String nValue = "";
Shang = MValue;
while(Shang.length() > 0) {
nValue = qiuyu(Shang) + nValue;
}
System.out.println(nValue);
}
/**
* 功能:对给定的M进制字符串对n求余。
*
* @param MTempValue
* @param m
* @param n
* @return
*/
public static String qiuyu(String MTempValue) {
Shang = "";
int temp = 0;
while (MTempValue.length() > 0) {
int t = getIntFromStr(MTempValue.substring(0, 1));
MTempValue = MTempValue.substring(1);
temp = temp * M + t;
Shang += getStrFromInt(temp / N);
temp = temp % N;
}
while(Shang.length() > 0 && Shang.charAt(0) == \'0\'){
Shang = Shang.substring(1);
}
return getStrFromInt(temp);
}
public static int getIntFromStr(String str){
return str.charAt(0) <= \'9\' && str.charAt(0) >= \'0\'?
str.charAt(0) - \'0\' : str.charAt(0) - \'a\' + 10;
}
public static String getStrFromInt(int value){
String result = null;
if (value >= 0 && value <= 9)
result = String.valueOf((char)(\'0\' + value));
else if (value > 9 && value < 36)
{
result = String.valueOf((char)(\'a\' + value - 10));
}
else
{
result = "-1";// 出错误了
}
return result;
}
}
赵大叔的算法好了不少,除了参数检查,大小写之外都很好。值得我们借鉴。
以上转自http://blogread/it/article/3302?f=wb
本人愚钝,研究了一段时间才完全弄明白里面的原理。第一个算法是转换成十进制,再辗转相除取余,最后逆置余数序列得到结果。第二个算法是直接对原数据,用目标进制n直接进行辗转相除,取商和取余。相对于第一个算法,去掉了前面整个数据转换成十进制的操作(当然计算机默认操作数是十进制,所以每取一位还是先要先转换为十进制)。
下面是本人用C语言改写的:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX_CONVERT_NUM_LEN 50
char m2n(char m, char n, char *mNum, char *nNum)
{
char *np=nNum;
char JINZHI[37] ="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
unsigned int dec;
char shang[MAX_CONVERT_NUM_LEN], tt[MAX_CONVERT_NUM_LEN];
char *sp, *tp;
char getm, temp;
if(m<2 || m>36 || n<2 || n>36)
return -1;
strcpy(shang, mNum);
sp = shang;
while(*sp != '\0'){
dec = 0;
*tt = '\0';
tp = tt;
while(*sp != '\0'){
getm = *sp > '9' ? (toupper(*sp++)-'A'+10) : ((*sp++)-'0');
if(getm < 0 || getm >= m )
return -1;
dec = dec * m + getm;
if((temp=dec/n) != 0 || *tp != '\0')
*tp++ = JINZHI[temp];
dec %= n;
}
*np++ = JINZHI[dec];
*tp = '\0';
strcpy(shang, tt);
sp = shang;
}
*np-- = '\0';
while(np>nNum){
temp =*np;
*np-- =*nNum;
*nNum++ = temp;
}
return 0;
}
int main(int argc, char **argv)
{
char *m="123004560007890000abcdEF";
char n[MAX_CONVERT_NUM_LEN];
if(strlen(m) > 0 && 0 == m2n(16, 10, m, n))
printf("%s \n",n);
else
printf("error!!!\n");
system("pause");
return 0;
}
更多推荐
m进制转换为n进制-任意进制转换算法
发布评论