进制转换算法

pojg上面第2734,2735是关于8和10机制互转的。

我刚开始用stack方法；

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<string.h>

class Stack
{
public:
    char a[16];
    int i;
    Stack()
    { 
        i=0;
    }
    void push(char c)
    {
        a[i++]=c;
    }
    bool isEmpty()
    {
        return i==0;
    }
    int pop()
    {
        if(isEmpty()) return -1;
        return a[--i];
    }
};

//十进制转8进制
int main()
{
    Stack s;
    
    int n;
    scanf("%d",&n);
    while(n)
    {
        s.push(n%8);
        n=n/8;
    }
    while(!s.isEmpty())
    {
        
        printf("%d",s.pop());
    }
    printf("
");

 
}

前面已经写过任意进制到十进制转换：

long b2ten(char *x,int b)
{
    int ret=0;
    int len=strlen(x);
    for(int i=0;i<len;i++)
    {
        if(x[i]-'0'>=b) return -1;
        ret*=b;
        ret+=x[i]-'0';
    }
    return (long)ret;
}

转：

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 != '')
        i = i*m + *mNum++ - '0';
     
    //辗转取余
    while (i) {
        *p++ = i % n + '0';
        i /= n;
    }
    *p-- = '';
 
    //逆置余数序列
    while (p > nNum) {
        c = *p;
        *p-- = *nNum;
        *nNum++ = c;
    }
}

（上面的转换进制范围只在《=10有效，为什么？）

观察上面的代码，存在着众多的不足。例如，要对输入参数做检查，数值的大小收到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(vlaue > 9 && value <36)
        {
            result = String.valueOf((char)('a' + value - 10));
        }
        else
        {
            result = "-1";// 出错误了
        }
        return result;
    }
}

赵大叔的算法好了不少，除了参数检查，大小写之外都很好。值得我们借鉴。

转自：http://www.cnblogs.com/pkuoliver/archive/2010/10/27/Convert-m-number-to-n-number.html

高精度转换：http://www.cnblogs.com/PJQOOO/p/4340466.html?utm_source=tuicool