题目描述
将一个长度最多为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;
}
网友评论