首页 > 其他 > 详细

P1017 进制转换

时间:2020-05-08 11:19:13      阅读:62      评论:0      收藏:0      [点我收藏+]

我的天,这道题简直就是噩梦,我查了好久好久的资料才看懂题意(没错你没听错看懂题意/暴风哭泣)

大致意思就是说,给你一个整数(可能是正的也可能是负的)和一个你要转换的负进制数的基数(就是你要转换为几进制,不过他是负的)。

思路:跟第一题是一样的,不过用短除法取余然后转换进制可能不可行,因为他的余数有可能是负的,所以我们就要加个判断:

if(shu[ans]<0){//判断如果这个余数<0
    shu[ans]-=m;//就让他减去一个除数,相当于我们在被除数那里借了一个除数
    n++;//既然我们在那里借了一个,所以就让他+1
}//这样所有问题就都解决啦

这个判断的作用就是拯救这一切!(我怕我表达的不够清晰,下面借鉴一位大佬的段落)

对于正数对负数取余,余数必定为正数,因为商乘以除数,负负得正,加上一个正的余数,结果就是被除数。例如:5 / -2 = -2 …… 1

而对于负数对负数取余,余数必定为负数,因为商是正数,除数是负数,相乘必定为负数,然后加上一个负的余数,结果就是被除数。例如 -13 / -2 = 6 …… -1

对于正数对负数取余,余数为正的情况,我们完全可以使用上述短除法的思想去解决,余数可直接作为结果储存并输出,因此难点就在于考虑负数对负数取余,余数为负的情况。

下面抛出两个式子:

-13 / -2 = 6 …… -1

-13 / -2 = 7 …… 1

显然,两式都满足公式 被除数=商×除数+余数,但不同的是,第二个式子的余数为1,是正数,如果余数是正数,我们就能将其作为结果储存并输出,所以现在的问题转化为如何将第一个式子等价变形为第二个式子。

我们将第一个式子的余数减去除数,这一步的目的相当于从被除数那里借来一个 -2 接着我们把商加一,相当于把借来的 -2 还了回去。

如此一来,我们就解决了负数对负数取余,余数为负数的问题,进而解决了整个负进制数转换问题。

实际上,负数对负除数取余后,商为正数。这个正数商又继续递归或循环对负除数取余,商又为负数.......如此循环往复,一次正,一次负,一次正,一次负.....正的部分可直接短除,负的部分将原式进行转换后,把余数变为正数,然后就可以又使用短除法解决。

这个真的很很很很很清晰了,能够一下子挑明关键所在。

然后我们就按照上面的思路,和平常进制转换的思路写了这个AC的代码:

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
long long n,m,ha,shu[100010],ans=0,hhh=0;
int main(){
    cin>>n>>m;
    hhh=n;//因为我们后面还需要n,但是我们又需要除他,就用一个变量把n保存下来。
    while(n!=0){//短除
        shu[ans]=n%m;//用一个数组余数存下来
        n/=m;
        if(shu[ans]<0){//这个判断很重要,如果没有他,负数的情况就会很麻烦
            shu[ans]-=m;
            n++;
        }
        ans++;
    }
    printf("%lld=",hhh);
    for(int i=ans-1;i>=0;i--){//因为我们是倒着保存的,所以要倒着输出
        if(shu[i]>=10){
            if(shu[i]==10) printf("A");
            else if(shu[i]==11) printf("B");
            else if(shu[i]==12) printf("C");
            else if(shu[i]==13) printf("D");
            else if(shu[i]==14) printf("E");
            else if(shu[i]==15) printf("F");
            else if(shu[i]==16) printf("G");
            else if(shu[i]==17) printf("H");
            else if(shu[i]==18) printf("I");
            else if(shu[i]==19) printf("J");
            else if(shu[i]==20) printf("K");//因为数据中的基数,他是可能会有-20这种情况的,所以这次不是判断到15就结束了,要判断到20.
        }
        else printf("%lld",shu[i]);
    }
    printf("(base%lld)",m);
    return 0;
}

以上就是我这道题的全部思路,如果有什么不对的地方,还请各位大佬及时向我纠正。

P1017 进制转换

原文:https://www.cnblogs.com/dgdger/p/12849043.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!