[9度OJ] 1080 进制转换

[九度OJ] 1080 进制转换

题目描述：

将M进制的数X转换为N进制的数输出。

输入：

输入的第一行包括两个整数：M和N(2<=M,N<=36)。
下面的一行输入一个数X，X是M进制的数，现在要求你将M进制的数X转换成N进制的数输出。

输出：

输出X的N进制表示的数。

样例输入：

16 10F

样例输出：

15

提示：

输入时字母部分为大写，输出时为小写，并且有大数据。

-----------------------------------华丽的分割线----------------------------------

题目分析：

题目其实就是实现2~36任意进制转换，之所以是2~36是因为字符'0'~'9','a'~'z'一共有36个，最多可以表示到36进制，当然也可以引入更多的字符来表示更大基底的进制，不过就算法的描述而言，更大的基底没有更多算法上的变化。

-----------------------------------华丽的分割线----------------------------------

算法分析：

限于数学水平和信息搜集能力，我没有找到更好的算法，处理进制转换，基本的算法就是作除法，例如：

将m进制的数s转换为n进制:

如果是30进制，294就的2/12=0,此时需要用29/12，这时候需要注意要用(2*30+9)/12，就是上一步除法的余数乘以m加上下一步的数再作除法。
从上面的过程可以看出，解决这个问题需要二步：
1 以适当方式表示出m进制数
2 手工模拟除法
-----------------------------------华丽的分割线----------------------------------
实现：
算法很明确，就是模拟除法，但是实现起来效率差别很大，九度OJ现在开放了查看别人代码的功能，每次查看别人代码要支付九度豆，我觉得这对于学习别人的优秀代码有很大好处，下面就看看同一个算法，不同的实现，效率的差别。以下由慢到快给出几个实现。
实现1：

从上面的数据变化应该会明白整个过程是如何动作的，数据首先在m[0]中积累，积累到超过分割基数时，m[]中的数据就要向右移动，变量s其实就是每次向右移动的那个数字。s的最后一个值就是向最高位存储的数值。如果s不为0说明有进位。这样m[]中的元素个数就增加，k即表示m[]中元素的个数。
故事的最后，提供一个我后来想明白思路后重新写的：
实现5：
#include <stdio.h>#include <string.h> #define XMAX 100000000000000#define LEN 1000 char itoc (int i ) { return (i>=10)?(i-10+'a'):(i+'0'); } int main (void){    int m,n,len,i,j,k,x[LEN];    char t,str[LEN];    unsigned long long s,sum,y[LEN];     while (scanf ("%d%d%s",&m,&n,str) != EOF)    {    len = 0;    while (str[len]) {         x[len] = (str[len]>'9')?(str[len]-'A'+10):(str[len]-'0');         ++len;        }         k = 1;    y[0] = 0;    for (i=0; i<len; i++)    {        s = 0;        for (j=0; j<k; j++)        {        sum = (j==0)?(y[j]*m+x[i]+s):(y[j]*m+s);        s = sum / XMAX;        y[j] = sum % XMAX;        }        if (s) y[k++] = s;    }     len = k;    k = 0;    j = len - 1;    while (j>=0)    {        s = 0;        for (i=j; i>=0; i--)        {        sum = s*XMAX + y[i];        s = sum % n;        y[i] = sum / n;        }        str[k++] = itoc(s);        if (y[j]==0 || j==0) j--;    }    while (y[0]) { str[k++] = itoc(y[0]%n); y[0] /= n; }    str[k] = '\0';    i = 0; j=k-1;    while (i<j) { t=str[i];str[i]=str[j];str[j]=t; ++i; --j; }     puts(str);    }    return 0;}/**************************************************************    Problem: 1080    User: minix    Language: C    Result: Accepted    Time:10 ms    Memory:908 kb****************************************************************/

运行时间减少到了10ms，其实就是扩大了那个分割基数以及减少了没必要的初始化还有减少了重复计算。
其实每次我一想这个题的时候都会去想，同一个问题，不管是多小的问题，例如这个任意进制转化问题，世界上最快的算法是什么，可是，我还是不太会找~~~也不知道怎么设计一个算法~~