任意进制的转换(针对大数而言)
|
在数据结构课关于栈的这一章中，我们都学过用“模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）变成本轮的被除数，如此下去，即可得到每轮的余数。 除数应该是1*10+2 = 12,所以得到的商是6，余数是0，即运算到此时的商是06，然后是第三个数位3，由于上一个数位留下的余数是0，所以此时被除数就是3，。。。如此下去 就完成第一轮的运算，这一轮完毕后，需要把得到的商变成下一轮的被除数，继续上述的运算，直到被除数为0才停止。 1 #include <stdio.h> 2 #include <string.h> 3 4 char str[1000];//输入字符串 5 int start[1000],ans[1000],res[1000]; //被除数，商，余数 6 7 //转换前后的进制 8 const int oldBase = 10; 9 const int newBase = 2; 10 11 void change() 12 {//各个数位还原为数字形式 13 int i,len = strlen(str); 14 start[0] = len; 15 for(i=1;i<= len;i++) 16 { 17 if(str[i-1] >= ‘0‘ && str[i-1] <= ‘9‘) 18 { 19 start[i] = str[i-1] - ‘0‘; 20 } 21 } 22 } 23 24 void solve() 25 { 26 memset(res,0,sizeof(res));//余数初始化为空 27 int y,i,j; 28 //模n取余法，(总体规律是先余为低位，后余为高位) 29 while(start[0] >= 1) 30 {//只要被除数仍然大于等于1，那就继续“模2取余” 31 y=0; 32 i=1; 33 ans[0]=start[0]; 34 // 35 while(i <= start[0]) 36 { 37 y = y * oldBase + start[i]; 38 ans[i++] = y/newBase; 39 y %= newBase; 40 } 41 res[++res[0]] = y;//这一轮运算得到的余数 42 i = 1; 43 //找到下一轮商的起始处 44 while((i<=ans[0]) && (ans[i]==0)) i++; 45 //清除这一轮使用的被除数 46 memset(start,sizeof(start)); 47 //本轮得到的商变为下一轮的被除数 48 for(j = i;j <= ans[0];j++) 49 start[++start[0]] = ans[j]; 50 memset(ans,sizeof(ans)); //清除这一轮的商，为下一轮运算做准备 51 } 52 } 53 54 void output() 55 {//从高位到低位逆序输出 56 int i; 57 for(i = res[0];i >= 1;--i) 58 { 59 printf("%d",res[i]); 60 } 61 printf("n"); 62 } 63 64 int main() 65 { 66 scanf("%s",str); 67 change(); 68 solve(); 69 output(); 70 return 0; 71 } 接下来让我们将次算法具体应用到题目中： 题目地址：https://ac.nowcoder.com/acm/contest/910/C 题目描述
给出一个m进制下的数a，现在请输出a在n进制下的表示。
输入描述:第一行一个整数T，代表有T组数据 输出描述:输出上述问题的答案，每个答案占一行。
示例1
输入1 10 2 3 输出11 1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=5000+100; 4 char hashch[maxn]; 5 int hashnum[maxn]; 6 void init() 7 { 8 char ch; 9 for(int i=0;i<62;i++){ 10 if(i<10) ch=i+‘0‘; 11 else if(i>=10&&i<36) ch=‘A‘+i-10; 12 else ch=‘a‘+i-36; 13 hashch[i]=ch; 14 hashnum[ch]=i; 15 } 16 } 17 string change(int m,int n,string str) 18 { 19 bool flag; 20 string ans=""; 21 int tmp,quotient,remainder; 22 while(true) 23 { 24 flag=false; 25 remainder=0; 26 string div=""; 27 int len=str.length(); 28 for(int i=0;i<len;i++){ 29 tmp=remainder*m+hashnum[str[i]]; 30 quotient=tmp/n; 31 remainder=tmp%n; 32 if(flag){ 33 div+=hashch[quotient]; 34 } 35 else{ 36 if(quotient!=0){ 37 flag=true; 38 div+=hashch[quotient]; 39 } 40 } 41 } 42 ans=hashch[remainder]+ans; 43 str=div; 44 if(flag==false) break; 45 } 46 return ans; 47 } 48 49 int main() 50 { 51 init(); 52 int t; 53 scanf("%d",&t); 54 while(t--){ 55 int m,n; 56 string str; 57 cin>>m>>n>>str; 58 string ans=change(m,n,str); 59 cout<<ans<<endl; 60 } 61 return 0; 62 } ? 参考文献： https://blog.csdn.net/SJF0115/article/details/8690581 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
