首页 > 代码库 > 九度oj 题目1080：进制转换
九度oj 题目1080：进制转换
- 题目描述：
将M进制的数X转换为N进制的数输出。
- 输入：
输入的第一行包括两个整数：M和N(2<=M,N<=36)。
下面的一行输入一个数X，X是M进制的数，现在要求你将M进制的数X转换成N进制的数输出。
- 输出：
输出X的N进制表示的数。
- 样例输入：
16 10F
- 样例输出：
15
- 提示：
输入时字母部分为大写，输出时为小写，并且有大数据。
这题初看起来另我头疼，考虑不难但是很麻烦
一开始想的比较绕，准备先把任意进制转换成10进制，再转化成n进制，于是写出了下面的代码
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 6 using namespace std; 7 8 char mnum[1002]; 9 int nnum[1002]; 10 int tnCnt; 11 12 int tnum[1002]; 13 int tCnt; 14 15 int tm[1002]; 16 int tmCnt; 17 18 int tSum[1002]; 19 int tsCnt; 20 21 int tDiv[1002]; 22 int tdCnt; 23 24 int m, n; 25 26 int getV(char a) { 27 if(a >= ‘0‘ && a <= ‘9‘) { 28 return a - ‘0‘; 29 } 30 else if(a >= ‘a‘ && a <= ‘z‘) { 31 return a - ‘a‘ + 10; 32 } 33 else if(a >= ‘A‘ && a <= ‘Z‘) { 34 return a - ‘A‘ + 10; 35 } 36 } 37 38 char putV(int a) { 39 if(a >= 0 && a <= 9) { 40 return a + ‘0‘; 41 } 42 else { 43 return a - 10 + ‘a‘; 44 } 45 } 46 47 void multiTm() { 48 int ci = 0; 49 int j = 0; 50 for(int i = 0; i < tmCnt; i++) { 51 int ben = tm[i] * m + ci; 52 tm[j++] = ben % 10; 53 ci = ben/10; 54 } 55 if(ci != 0) { 56 tm[j++] = ci; 57 } 58 tmCnt = j; 59 } 60 61 int multi(int a[], int acnt, int b[], int t) { 62 int ci = 0; 63 int j = 0; 64 for(int i = 0; i < acnt; i++) { 65 int ben = a[i] * t + ci; 66 b[j++] = ben % 10; 67 ci = ben/10; 68 } 69 if(ci != 0) { 70 b[j++] = ci; 71 } 72 return j; 73 } 74 75 int add(int a[], int acnt, int b[], int bcnt) { 76 int p = max(acnt, bcnt); 77 int j = 0; 78 int ci = 0; 79 for(int i = 0; i < p; i++) { 80 int ben = a[i] + b[i] + ci; 81 a[j++] = ben % 10; 82 ci = ben/10; 83 } 84 if(ci != 0) { 85 a[j++] = ci; 86 } 87 return j; 88 } 89 90 int div(int t) { 91 int j = 0; 92 int ci = 0; 93 for(int i = 0; i < tdCnt; i++) { 94 int ben = ci*10 + tDiv[i]; 95 tDiv[j++] = ben/t; 96 ci = ben%t; 97 //printf("%d\n",ci); 98 } 99 int state = 0;100 int p = 0;101 for(int i = 0; i < j; i++) {102 if(state == 0 && tDiv[i] != 0) {103 state = 1;104 tDiv[p++] = tDiv[i];105 }106 else if(state == 1) {107 tDiv[p++] = tDiv[i];108 }109 }110 tdCnt = p;111 112 /*for(int i = 0; i <= tdCnt; i++) {113 printf("%d",tDiv[i]);114 }115 puts("");*/116 117 return ci;118 }119 120 int main(int argc, char const *argv[])121 {122 while(scanf("%d %d",&m,&n) != EOF) {123 scanf("%s",mnum);124 //to-ten125 int lenm = strlen(mnum);126 127 memset(tm, 0, sizeof(tm));128 tm[0] = 1;129 tmCnt = 1;130 131 memset(tnum, 0, sizeof(tnum));132 tCnt = 0;133 134 for(int i = lenm -1; i >= 0; i--) {135 int tmp = getV(mnum[i]);136 memset(tSum, 0, sizeof(tSum));137 tsCnt = 0;138 tsCnt = multi(tm, tmCnt, tSum, tmp);139 tCnt = add(tnum,tCnt,tSum,tsCnt);140 multiTm();141 }142 143 /*for(int i = tCnt-1; i >= 0; i--) {144 printf("%d",tnum[i]);145 }146 puts("");*/147 for(int i = tCnt-1; i >= 0; i--) {148 tDiv[tCnt-i-1] = tnum[i];149 }150 tdCnt = tCnt;151 int j = 0;152 memset(nnum, 0, sizeof(nnum));153 while(!(tdCnt == 0 && tDiv[0] == 0)) {154 nnum[j++] = div(n);155 }156 for(int i = j-1; i >= 0; i--) {157 printf("%c",putV(nnum[i]));158 }159 puts("");160 } 161 return 0;162 }
虽然例子能跑出来，但提交答案错误
后来一拍脑门，进制直接除n取余就好了，转化成10进制简直多此一举，于是写出下面代码
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 6 using namespace std; 7 8 char mnum[1002]; 9 10 11 int tDiv[1002];12 int ds, de;13 14 int nnum[1002];15 int nCnt;16 17 int m,n;18 19 int getV(char a) {20 if(a >= ‘0‘ && a <= ‘9‘) {21 return a - ‘0‘;22 }23 else if(a >= ‘A‘ && a <= ‘Z‘) {24 return a - ‘A‘ + 10;25 }26 else if(a >= ‘a‘ && a <= ‘z‘) {27 return a - ‘a‘ + 10;28 }29 30 }31 32 char putV(int a) {33 if(a >= 0 && a <= 9) {34 return a + ‘0‘;35 }36 else {37 return a - 10 + ‘a‘;38 }39 }40 41 int div() {42 int j = 0;43 int ci = 0;44 for(int i = 0; i < de; i++) {45 int ben = ci*m + tDiv[i];46 tDiv[j++] = ben/n;47 ci = ben%n;48 }49 int i = 0;50 while(tDiv[i] == 0) {51 i++;52 }53 ds = i;54 return ci;55 }56 57 58 int main(int argc, char const *argv[])59 {60 while(scanf("%d %d",&m,&n) != EOF) {61 scanf("%s",mnum);62 int lenm = strlen(mnum);63 64 for(int i = 0; i < lenm; i++) {65 tDiv[i] = getV(mnum[i]);66 }67 68 ds = 0, de = lenm;69 tDiv[de] = -1;70 int j = 0;71 memset(nnum, 0, sizeof(nnum));72 while(ds != de) {73 nnum[j++] = div();74 }75 for(int i = j-1; i >= 0; i--) {76 printf("%c",putV(nnum[i]));77 }78 puts("");79 }80 return 0;81 }
虽然通过，但耗时70ms
考虑有没有优化的空间，观察一下div 函数，每回都从0开始除，其实每回应该从ds除就好了。50行也应该从ds开始找，但注意j初值也为ds
另外，输出也可改一下
代码如下
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 6 using namespace std; 7 8 char mnum[1002]; 9 10 11 int tDiv[1002];12 int ds, de;13 14 int nnum[1002];15 int nCnt;16 17 char ans[1002];18 int m,n;19 20 int getV(char a) {21 if(a >= ‘0‘ && a <= ‘9‘) {22 return a - ‘0‘;23 }24 else if(a >= ‘A‘ && a <= ‘Z‘) {25 return a - ‘A‘ + 10;26 }27 else if(a >= ‘a‘ && a <= ‘z‘) {28 return a - ‘a‘ + 10;29 }30 31 }32 33 char putV(int a) {34 if(a >= 0 && a <= 9) {35 return a + ‘0‘;36 }37 else {38 return a - 10 + ‘a‘;39 }40 }41 42 int div() {43 int j = ds;44 int ci = 0;45 for(int i = ds; i < de; i++) {46 int ben = ci*m + tDiv[i];47 tDiv[j++] = ben/n;48 ci = ben%n;49 }50 int i = ds;51 while(tDiv[i] == 0) {52 i++;53 }54 ds = i;55 return ci;56 }57 58 59 int main(int argc, char const *argv[])60 {61 while(scanf("%d %d",&m,&n) != EOF) {62 scanf("%s",mnum);63 int lenm = strlen(mnum);64 65 for(int i = 0; i < lenm; i++) {66 tDiv[i] = getV(mnum[i]);67 }68 69 ds = 0, de = lenm;70 tDiv[de] = -1;71 int j = 0;72 memset(nnum, 0, sizeof(nnum));73 while(ds != de) {74 nnum[j++] = div();75 }76 int p = 0;77 for(int i = j-1; i >= 0; i--) {78 ans[p++] = putV(nnum[i]);79 }80 ans[p] = ‘\0‘;81 puts(ans);82 }83 return 0;84 }
这样，时间缩短到了30ms
但代码还有优化的空间，即数组的一位不再是一位数字，而可以是多位，这样运算次数会更少。
但比较麻烦，以后再考虑吧
九度oj 题目1080：进制转换
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。