本人第一篇博客,刚学算法半年的蒟蒻,用于进一步学习交流。

分~界~线~~~


 

进制转换

题目描述:

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

输入:

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

输出:

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

样例输入:

985
211
1126

样例输出:

1111011001
11010011
10001100110

 

注:每段代码变量不一致,以最后Code为标准。

分析:

每组数据输入长度不超过30位的十进制非负数。

不是30bits!不是30bits!不是30bits!

 

按照大数的一般操作,我们可以先用字符数组存储后,再进一步用整型数组存储,以便后续转为二进制。

char str[35];
int num[35];
for(int len=0;str[len];++len){
    num[len]=str[len]-'0';
}

 

 

进制转换,从十进制 -> x 进制,一般操作(应该没有其他办法了吧_小声_)是将十进制数 n 对 x 取模结果存入ans数组内( 我是用ans数组存放转换成的二进制答案的 ),然后通过 n /= x 更新 n 的值。

int i=0;
int n,x;
int ans[MAXN];

do{
    ans[i++] = n % x;
    n /= x;
}while(n);

 

问题:

如果是普通整型范围内的非负整数是能直接进行运算的(或者用python,手动滑稽本题数据均是超过30位的非负整数,就需要用到大数除以及取模操作。开始时,我能想到的只有暴力。显然,暴力不能解决问题。于是我就..打开了万能的百度......

本题特别的由十进制转二进制。在转二进制时,如何判断当前数值取模结果,主要在于当前十进制数末位奇偶状态,奇数为1,偶数为0。

int len = strlen(str);
ans = num[len-1]%2;

 

 

取模后,需要用当前数除进制数 ”2“得新数 ,按照除法运算的规则,可以明显发现,被除数当前位为奇时,借给下一位的值为10,反之为0。可以用和大整数加法类似的变量 x 来存储借位值。

int i,tmp,l=0,x=0;
for(i=l;i<len;++i){
    tmp=num[i];
    num[i]=(num[i]+x)/2;
    if(tmp&1)x=10;
    else x=0;
}
if(num[l]==0)++l;

 

 

我是选择在原值上进行修改,用 ' l ' 来记录十进制数最高位的位置,除数小于10,因此每次最高位的位数最多向右移一位,即若当前最高位的数值为0,就说明最高位已经向后移动一位。

Code:

代码如下,注释有空再加...

#include<iostream>
#include<cstdio>

using namespace std;

char str[35];
int num[35];

int ans[1005];

int main(){
    
    int i,j;
    
    int len=0,tmp;
    int x,l;
    
    while(scanf("%s",str)!=EOF){
        for(len=0;str[len];++len){
            num[len]=str[len]-'0';
        }
        j=0;
        l=0;
        while(l<len){
            ans[j++]=num[len-1]%2;
            x=0;
            for(i=l;i<len;++i){
                tmp=num[i];
                num[i]=(num[i]+x)/2;
                if(tmp&1)x=10;
                else x=0;
            }
            if(num[l]==0)++l;
        }
        for(i=j-1;i>=0;--i){
            printf("%d",ans[i]);
        }
        printf("n");
        
    }
    
    return 0;
}

 

收获:

在做大整数进制转换的时候,遇到二进制可以特殊对待。相似的是,有些问题也是如此。

十进制转二进制,末尾奇偶确定取模结果,当前位奇偶确定借位值大小。

 

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/TinDot/p/14698765.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!