时间限制：1.0s   内存限制：512.0MB

问题描述

　　给定n个十六进制正整数，输出它们对应的八进制数。

输入格式

　　输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。

输出格式

　　输出n行，每行为输入对应的八进制正整数。

注意

　　输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。

样例输入

2
39
123ABC

样例输出

71
4435274

提示

　　先将十六进制数转换成某进制数，再由某进制数转换成八进制。

                                                                                                                                                                                                                                                                                           

算法分析：

这个题目，我们要看到 "每个十六进制数长度不超过100000"  这句话。注意是100000位，不是<100000;

我们这里主要思想是先将十六进制转化为二进制(每4位二进制对应1位十六进制)，然后将二进制转化为八进制（每3位二进制对应1位八进制）。

如：十六进制 A1  二进制 1010 0001  八进制 （010 100 001）241

（C语言）实现如下：

①采用gets输入时，需要处理%d在输入流中留下的回车；
②合理定义数组大小，其中十六进制位数与二进制是4倍关系，与八进制是4/3关系；
③使用strcat拼接字符串时注意，为了加快速度，需采用下文中方式，否则会超时（避免每次都从字符串首部查找’\0’）；
④对于所得二进制可能不为3的整数倍时，01,101,110,101…..，这里采用取余法将01单独处理，后面整体处理；
⑤由于采用了while(scanf(”)!=EOF)输入形式，注意每次对尾部进行截断，避免对下次计算造成影响；
⑥以下程序采用纯C语言编写。

c++ decode:true">#include <stdio.h>  
#include <string.h>  
#include <math.h>  

char Hex[10][100001]; // 十六进制  
char Oct[10][150000]; // 八进制 将列数扩大4/3倍以上  
char Bin[10][400004]; // 二进制 将列数扩大为4倍以上  

//十六进制转二进制  
void Hex2Bin(int row)  
{  
    int hexcol=0, bincol=0;  

    Bin[row][0] = '\0';   //strcat 识别'\0'  
    while (Hex[row][hexcol] != '\0')  
    {  
        switch (Hex[row][hexcol])  
        {//&Bin[row][bincol]   比直接使用Bin[row]速度快，避免从头查找'\0'  
            case '0': strcat(&Bin[row][bincol],"0000"); break;  
            case '1': strcat(&Bin[row][bincol],"0001"); break;  
            case '2': strcat(&Bin[row][bincol],"0010"); break;  
            case '3': strcat(&Bin[row][bincol],"0011"); break;  
            case '4': strcat(&Bin[row][bincol],"0100"); break;  
            case '5': strcat(&Bin[row][bincol],"0101"); break;  
            case '6': strcat(&Bin[row][bincol],"0110"); break;  
            case '7': strcat(&Bin[row][bincol],"0111"); break;  
            case '8': strcat(&Bin[row][bincol],"1000"); break;  
            case '9': strcat(&Bin[row][bincol],"1001"); break;  
            case 'A': strcat(&Bin[row][bincol],"1010"); break;  
            case 'B': strcat(&Bin[row][bincol],"1011"); break;  
            case 'C': strcat(&Bin[row][bincol],"1100"); break;  
            case 'D': strcat(&Bin[row][bincol],"1101"); break;  
            case 'E': strcat(&Bin[row][bincol],"1110"); break;  
            case 'F': strcat(&Bin[row][bincol],"1111"); break;  
        }  
        ++hexcol;     
        bincol += 4;  
    }  
//  puts(Bin[row]);  
}  

//二进制转八进制  
void Bin2Oct(int row)  
{  
    int bincol,octcol=0,mod,num,curcol=0,flag=0;  
    //curcol 表示当前扫描到二进制位置  
    //flag用来标记首部是否已经出现了非0元素  

    bincol = strlen(Bin[row]);  
    mod = bincol % 3;  // 解决01, 101,110,011...问题，  
                       //划分为2部分分别计算  
                       //01------101,110,011  
    //单独计算01  
    num = 0;  
    while (--mod >= 0)  
    {  
        if (Bin[row][curcol++] == '1')  
            num += (int)pow(2,mod);  
    }  
    //跳过首部0  
    if (num != 0)  
    {  
        Oct[row][octcol++] = '0'+num; //转数字为字符  
        flag = 1;  //标记第一个不为0位置  
    }  
    //计算101,110,011...  
    while (Bin[row][curcol] != '\0')  
    {  
        mod = 3; num = 0;  //每3位一计算，2^2=4,  2^1=2,  2^0=1  
        while (--mod >= 0)  
        {  
            if (Bin[row][curcol++] == '1')  
                num += (int)pow(2,mod);  
        }  
        //跳过首部0  
        if (num != 0 || flag == 1)  
        {  
            Oct[row][octcol++] = '0'+num; //转数字为字符  
            flag = 1;  
        }  
    }  
    //将尾部截断  
    Oct[row][octcol] = '\0';  
}  
//十六进制转八进制  
void Hex2Oct(int n)  
{  
    int row;  

    for (row = 0; row < n; ++row)  
    {  
        Hex2Bin(row);  // 16->2  
        Bin2Oct(row);  // 2->8  
    }  

}  


int main(void)  
{  
    int row,n;  

    while (scanf("%d",&n) != EOF)    
    {  
        getchar();  //消除输入流——回车误差  

        for (row = 0; row < n; ++row)  
        {  
            gets(Hex[row]);  
        }  
        //十六进制转八进制  
        Hex2Oct(n);  
        //打印  
        for (row = 0; row < n; ++row)  
        {  
            puts(Oct[row]);  
        }  
    }  

    return 0;  
}

转自:http://blog.csdn.net/qingdujun/article/details/17404005