在数据结构课关于栈的这一章中,我们都学过用“模2取余法”来将一个10进制数转换为一个二进制数,进而可以推广到“模n取余法”,经其转换为n进制(n任意指定)。
确实,这是一个很基础的题目,可你是否想过如果这个10进制数是一个大数(其位数可能上千位,此时用一般数据类型肯定是会溢出的),那么这个问题又如何来求解呢?
当然,也许你会说很简单嘛,自己写一个大数类(当然至少要写一个大数除法才行),或者你用的是Java这种现代化语言,就更轻松了,直接用BigInteger这样的大数类就可以来表示一个大数,进而用书上教的方法来实现。
但是,真的需要用到大数类吗?事实上,“杀鸡焉用牛刀“,我们在纸上模拟一番上述运算后就可以发现,只要做一些小小的改进,就可以在不使用大数的情况下,也可以通过“模n
取余”的原理来实现大数的进制转换的。(当然,整体的思想仍然是“模n取余”原理!!!)。
举个简单的例子,就比如说把10进制数12转换为2进制形式,书上的方法可以用下图来表示
按照 “先余为低位,后余为高位“这条铁律,其结果为1100.
这是书上教我们的常规思路(可惜按这个的话,大数是没法考虑的,因为假如这里不是12,而是一个1000位的大数,由于是是对大数的整体进行取余运算,不使用大数类及其
除法操作,又如何得以进行呢?),可我们的目的是不使用大数类,那么现在我们就来换一个视角来看这个问题,12是一个十位数,十位上是1,个位上是2,按照我们正常的
思维来看,这个计算应该是下面这样的:
那么我们发现在第一轮运算时,十位上的1作为被除数,2作为除数,得到的商是0,余数是1(可以断言只考虑当前这一个数位的计算,余数或是0,或是1,若是1的话,则进
下一数位(这里即对个位进行运算)时,要用1乘上进制(这里是10)再加上下一个数位上的值(这里是2)),即得到运算进入个位时被除数是12,除数是2,得到的商是6,
数是0。第一轮运算的结果是商是06,余数是0.
进入第二轮运算,则上一轮的商6(这里首先要去掉前面多余的0)变成本轮的被除数,如此下去,即可得到每轮的余数。
推广开来,如果被除数是一个1000位的大数,例如“12343435154324123……342314324343”
那么我们照样可以从第一个数位开始逐位考虑,比如第一位是1(作为被除数),2是除数,得到的商是0,余数是1,然后是第二个数位2,由于上一位留下了余数1,则此时被
除数应该是1*10+2 = 12,所以得到的商是6,余数是0,即运算到此时的商是06,然后是第三个数位3,由于上一个数位留下的余数是0,所以此时被除数就是3,。。。如此下去
就完成第一轮的运算,这一轮完毕后,需要把得到的商变成下一轮的被除数,继续上述的运算,直到被除数为0才停止。
下面给出了一个示例代码,展示了如何将一个10进制的大数转换为其二进制形式,仅供参考:
- #include <stdio.h>
- #include <string.h>
-
- char str[1000];//输入字符串
- int start[1000],ans[1000],res[1000]; //被除数,商,余数
-
- //转换前后的进制
- const int oldBase = 10;
- const int newBase = 2;
-
- void change()
- {//各个数位还原为数字形式
- int i,len = strlen(str);
- start[0] = len;
- for(i=1;i<= len;i++)
- {
- if(str[i-1] >= '0' && str[i-1] <= '9')
- {
- start[i] = str[i-1] - '0';
- }
- }
- }
-
- void solve()
- {
- memset(res,0,sizeof(res));//余数初始化为空
- int y,i,j;
- //模n取余法,(总体规律是先余为低位,后余为高位)
- while(start[0] >= 1)
- {//只要被除数仍然大于等于1,那就继续“模2取余”
- y=0;
- i=1;
- ans[0]=start[0];
- //
- while(i <= start[0])
- {
- y = y * oldBase + start[i];
- ans[i++] = y/newBase;
- y %= newBase;
- }
- res[++res[0]] = y;//这一轮运算得到的余数
- i = 1;
- //找到下一轮商的起始处
- while((i<=ans[0]) && (ans[i]==0)) i++;
- //清除这一轮使用的被除数
- memset(start,0,sizeof(start));
- //本轮得到的商变为下一轮的被除数
- for(j = i;j <= ans[0];j++)
- start[++start[0]] = ans[j];
- memset(ans,0,sizeof(ans)); //清除这一轮的商,为下一轮运算做准备
- }
- }
-
- void output()
- {//从高位到低位逆序输出
- int i;
- for(i = res[0];i >= 1;--i)
- {
- printf("%d",res[i]);
- }
- printf("\n");
- }
-
- int main()
- {
- scanf("%s",str);
- change();
- solve();
- output();
- return 0;
- }
高精度进制转换模版:
- /*
- 高精度进制转换
- 把oldBase 进制的数转化为newBase 进制的数输出。
- 调用方法,输入str, oldBase newBase.
- change();
- solve();
- output();
- 也可以修改output(),使符合要求,或者存入另外一个字符数组,备用
- */
- #include<stdio.h>
- #include<string.h>
- #defien MAXSIZE 1000
- char str[MAXSIZE];//输入字符串
- int start[MAXSIZE],ans[MAXSIZE],res[MAXSIZE];//被除数,商,余数
- int oleBasw,newBase;//转换前后的进制
-
- //单个字符得到数字
- int getNum(char c)//这里进制字符是先数字,后大写字母,后小写字母的
- {
- if(c>='0'&&c<='9') return c-'0';//数字
- if(c>='A'&&c>='Z') return c-'A'+10;//大写字母
- return c-'a'+36;//小写字母
- }
- //数字得到字符
- char getChar(int i)
- {
- if(i>=0&&i<=9)return i+'0';
- if(i>=10&&i<=35)return i-'10'+'A';
- return i-36+'a';
- }
- void change()//把输入的字符串的各个数位还原为数字形式
- {
- int i;
- start[0]=strlen(str);//数组的0位存的是数组长度
- for(i=1;i<=start[0];i++)
- start[i]=getNum(str[i-1]);
- }
- void solve()
- {
- memset(res,0,sizeof(res));//余数位初始化为空
- int y,i,j;
- while(start[0]>=1)
- {
- y=0;i=1;
- ans[0]=start[0];
- while(i<=start[0])
- {
- y=y*oldBase+start[i];
- ans[i++]=y/newBase;
- y%=newBase;
- }
- res[++res[0]]=y;//这一轮得到的余数
- i=1;//找下一轮商的起始处,去掉前面的0
- while(i<=ans[0]&&ans[i]==0) i++;
- memset(start,0,sizeof(start));
- for(j=i;j<ans[0];j++)
- start[++start[0]]=ans[j];
- memset(ans,0,sizeof(ans));
- }
- }
- void output()//从高位到低位逆序输出
- {
- int i;
- for(i=res[0];i>=1;i--)
- printf("%d",getChar(res[i]));
- printf("\n");
- }
如果你对这个话题感兴趣的话,可以用这个思路来尝试解决下PKU 1220这个题目:http://acm.pku.edu.cn/JudgeOnline/problem?id=
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。