29. 进制转换

作者: IceFrozen | 来源:发表于2019-01-18 11:42 被阅读0次
    题目描述

    将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。

    输入描述:

    多组数据,每行为一个长度不超过30位的十进制非负整数。
    (注意是10进制数字的个数可能有30个,而非30bits的整数)

    输出描述:

    每行输出对应的二进制数。

    示例1

    输入

    0
    1
    3
    8
    

    输出

    0
    1
    11
    1000
    
    思路

    大数需要用数组来存,数组的每一位存着十进制的每一位,难点在于怎么处理数组来等效于处理这个数,处理方法是:
    从数组最低位开始,把每一位余 2 的值加到高一位,然后自己除以 2,
    到数组最高位时,余 2 的值无法加到高一位了,便把这个值存到二进制数组,
    反复执行这个步骤便直到数组全部为零便可得到二进制。

    我通过一个例子来手动模拟一下就容易理解了。
    假设输入的字符串是 1 2 3 4
    把它转成数组则为 1 2 3 4
    按照上述规则,第一趟下来则为 0 6 1 7,最高位余的是 0,存到二进制数组
    第二趟下来为 0 3 0 8,最高位余的是 1, 存到二进制数组
    ...
    一直做下去直到数组全为零,二进制数组里面存的便是对应的反过来的二进制

    解法
    #include <stdio.h>
    #include <string.h>
    #include <malloc.h>
    
    void decToBin(char *str, int len) {    //十进制转二进制
        int devidend = 1;    //用来标记被除数是否为零了
        int k = 0;    //控制二进制数组的计数
        int tag = 0;    //控制二进制数组倒序输出
        int *res = (int *) malloc (sizeof(int) * len * 4);    //动态分配二进制数组,长度为十进制的四倍
        int *num = (int *) malloc (sizeof(int) * len);    //存字符串转成的十进制数组
        for (int i = 0; i < len * 4; i++)    //动态分配的是随机数,需要初始化二进制数组
            res[i] = 0;
        for (int i = 0; i < len; i++) {
            num[i] = str[i] - '0';
        }
        while (devidend) {    //被除数不为零则一直做下去
            devidend = 0;
            for (int i = 0; i < len; i++) {
                if (num[i] / 2)    //只要有一位不为零,则说明被除数不为零
                    devidend = 1;
                if (i == len - 1)    //最后一位时取余放到二进制数组
                    res[k++] = num[i] % 2;
                else     //不是最后一位时,取余乘上 10 加到高一位
                    num[i + 1] += num[i] % 2 * 10;
                num[i] /= 2;
            }
        }
        for (int tag = 0, i = len * 4 - 1; i >= 0; i--) {    //倒序输出
            if (tag)    //最终判断标志一定要放在上面,不然会输出两次
                printf("%d", res[i]);
            if (res[i] && tag == 0) {
                printf("%d",res[i]);
                tag = 1;
            }  
        }
        printf("\n");
        free(res);
        free(num);
    }
    
    int main() {
        char str[31];
        while (~scanf("%s", &str)) 
            decToBin(str, strlen(str));
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:29. 进制转换

        本文链接:https://www.haomeiwen.com/subject/visgdqtx.html