思路:跟第一题是一样的,不过用短除法取余然后转换进制可能不可行,因为他的余数有可能是负的,所以我们就要加个判断:
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; }
原文:https://www.cnblogs.com/dgdger/p/12849043.html