m进制转换为n进制-任意进制转换算法

    这种题也是一道经典的面试题，主要考察进制转换细想，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.cn/it/article/3302?f=wb

    本人愚钝，研究了一段时间才完全弄明白里面的原理。第一个算法是转换成十进制，再辗转相除取余，最后逆置余数序列得到结果。第二个算法是直接对原数据，用目标进制n直接进行辗转相除，取商和取余。相对于第一个算法，去掉了前面整个数据转换成十进制的操作（当然计算机默认操作数是十进制，所以每取一位还是先要先转换为十进制）。

    下面是本人用C语言改写的：

#include 
#include 
#include 
#include 
#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);elseprintf("error!!!\n");system("pause");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！