今天在做蓝桥杯题目的时候看到一题十六进制转八进制的题目，题目如下：
问题描述
给定n个十六进制正整数，输出它们对应的八进制数。
输入格式
输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。
输出格式
输出n行，每行为输入对应的八进制正整数。
注意
输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。
样例输入
2 39 123ABC
样例输出
71 4435274
提示
先将十六进制数转换成某进制数，再由某进制数转换成八进制。
十六进制转化为八进制最直接想到的有两种方法：
1.将十六进制转换为十进制再转换为八进制
2.将十六进制转换为二进制再转换为八进制
分析：在第一种方法中用int类型来储存十进制数的话那么最大能处理80 000 000(H)也就是 2147483648 (D)，本题要求处理大数据，那么必须用数组储存。用第一种方法就涉及到了大整数的加法，模，除法。
第二种方法相对于第一种方法而言比较容易，只用定义一个字符数组就可以储存二进制数，每一个十六进制可以转换为4位2进制数，然后每3位二进制数可以转换为一个八进制数，在本题中输入的十六进制没有前导零，所以在十六进制最高的四位最小出现“0001”若最后三位相加为0那么就不输出即可。
以下是实现代码
#include <stdio.h> #include <string.h> #include <ctype.h> #define N 100001 char str[N]; void prin(char *a,int n) { int i; for(i=n-1;i>=0;i--){ printf("%d",a[i]); } putchar('\n'); } void change(int use) { int num=0; char two[N*4]; int w[4]={1,2,4,8}; int i=0,j=0,cnt2=0,cnt8=0; //totwo while(use>=0){ num=isdigit(str[use])?str[use]-'0':str[use]-'A'+10; use--; for(i=0;i<4;i++){ two[cnt2++]=num&w[i]; } } //twoto for(i=0;i<cnt2;){ for(num=0,j=0; i<cnt2&&j<3 ;j++){ if(two[i++]) num+=w[j]; } two[cnt8++]=num; } if(!two[cnt8-1]) cnt8--; //printf for(i=cnt8-1;i>=0;i--) { printf("%d",two[i]); } putchar('\n'); } int main(void) { int n; scanf("%d",&n); if(n>=1&&n<=10){ while(n--){ scanf("%s",str); change(strlen(str)-1); } } return 0; }
对于上述方法浪费的空间太大！我利用C语言对于底层的操作，位运算可以大大减少空间复杂度以及时间复杂度
实现如下
#include <stdio.h> #include <string.h> #include <ctype.h> #define N 100001 char str[N]; int save=0; void change(int use,int state) { int num; if(use>=0){ if(state!=3){ num=isdigit(str[use])?str[use]-'0':str[use]-'A'+10; num<<=state; num|=save; save=num>>3; change(use-1,state+1); printf("%d",num%8); }else{ num=save; save>>=3; change(use,0); printf("%d",num%8); } }else{ if(save){ printf("%d",save); save=0; } } } int main(void) { int num; scanf("%d",&num); if(num>=1&&num<=10){ while(num--){ scanf("%s",str); change(strlen(str)-1,0); printf("\n"); } } return 0; }
内存使用之所以不降反升的原因是因为使用了递归
（作者水平有限，欢迎大家讨论批评）
