基础算法题——进制转换（类比思想）

深藏阁楼爱情的钟 2022-11-21 11:33 160阅读 0赞

#### [进制转换][Link 1] ####

题目描述  
我们可以用这样的方式来表示一个十进制数: 将每个阿拉伯数字乘以一个以该数字所处位置为指数,以 10 为底数的幂之和的形式。例如 123 可表示为 1×102\+2×101\+3×100 这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置为指数,以 2 为底数的幂之和的形式。

一般说来，任何一个正整数 R 或一个负整数 -R 都可以被选来作为一个数制系统的基数。如果是以 R 或 -R 为基数,则需要用到的数码为 0,1,…R-1。

例如当 R=7 时,所需用到的数码是 0,1,2,3,4,5,6，这与其是 RR 或 -R 无关。如果作为基数的数绝对值超过 10，则为了表示这些数码，通常使用英文字母来表示那些大于 9 的数码。例如对 16 进制数来说，用 A 表示 10,用 B 表示 11，用 C 表示 12，以此类推。

在负进制数中是用 -R −R 作为基数，例如 −15（十进制）相当于 110001 （-2进制），并且它可以被表示为 2 的幂级数的和数：  
110001=1×(−2)5\+1×(−2)4\+0×(−2) 3\+0×(−2) 2\+0×(−2) 1\+1×(−2) 0  
设计一个程序,读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数。

输入格式  
输入的每行有两个输入数据。

第一个是十进制数 n。 第二个是负进制数的基数 -R。

输出格式  
输出此负进制数及其基数，若此基数超过 10，则参照 16 进制的方式处理。

输入输出样例  
输入 \#1  
30000 -2  
输出 \#1  
30000=11011010101110000(base-2)  
输入 \#2  
\-20000 -2  
输出 \#2  
\-20000=1111011000100000(base-2)  
输入 \#3  
28800 -16  
输出 \#3  
28800=19180(base-16)  
输入 \#4  
\-25000 -16  
输出 \#4  
\-25000=7FB8(base-16)  
说明/提示  
【数据范围】  
对于 100% 的数据，−20≤R≤−2，∣n∣≤37336。

--------------------

回顾下十进制（大于等于0的实数）转换为正进制  
求 (173)10 转换为二进制  
![十进制转换为二进制][20201101113108551.png_pic_center]  
原理：被除数(n) = 商(n/jz) \* 除数(jz) + 余数  
①、n 不断 除以 jz 并取余数。  
②、最终逆序排序余数即为答案  
（最先得到的余数为最低位）

实现代码

#include<bits/stdc++.h>
    using namespace std;
    char s[25]="0123456789ABCDEFGHIJLMN";
    
    void f(int n, int jz){ 
    	if(n==0) return;
    	int m = n%jz;
    	f(n/jz, jz);
    	//倒序取余
    	printf("%c", s[m]);
    	return;
    }
    
    int main(){ 
    	int n, jz;
    	scanf("%d%d", &n, &jz);
    	printf("%d=", n);
    	if(n==0){ 
    		printf("0(base%d)", jz);
    		return 0;
    	}
    	f(n, jz);
    	printf("(base%d)", jz);
    	
    	return 0;
    }

--------------------

实现十进制（所有实数）转换为负进制  
关键：当余数为负数的时，要向 n **借位**。

#include<bits/stdc++.h>
    using namespace std;
    char s[25]="0123456789ABCDEFGHIJLMN";
    void f(int n, int jz){ 
    	if(n==0) return;
    	int m = n%jz;
    	// m 为负数时，要向 n 借位，使 m 取正数
    	if(m<0){ 
    		m -= jz;
    		n += jz;
    	}
    	f(n/jz, jz);
    	printf("%c", s[m]);
    	return;
    }
    
    int main(){ 
    	int n, jz;
    	scanf("%d%d", &n, &jz);
    	printf("%d=", n);
    	if(n==0){ 
    		printf("0(base%d)", jz);
    		return 0;
    	}
    	f(n, jz);
    	printf("(base%d)", jz);
    	
    	return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1017
[20201101113108551.png_pic_center]: /images/20221120/7f2d4e8d193641999ac324fb24b2d74b.png