♉ CSP_S 组真题
2000年
1. 进制转换

线上OJ:

一本通:1820:【00NOIP提高组】进制转换 (opens in a new tab)
AcWing:5505. 进制转换 (opens in a new tab)
洛谷:P1017 [NOIP2000 提高组] 进制转换 (opens in a new tab)

核心思想:

1、题中告诉我们一个关键信息: 任何一个十进制数 X 都可以表示为 以 R 为基数的幂次方的和,并且不管R > 0,还是R < 0都适用。
X=an1R(n1)+an2R(n2)+...+a2R2+a1R1+a0X = a_{n-1}R^{(n-1)}+a_{n-2}R^{(n-2)}+...+a_{2}R^2+a_{1}R^1+a_{0} 公式 ①

举例:
(求15对2为底)15(10)=123+122+121+120......1111(2)15_{(10)}=1*2^3 + 1*2^2+1*2^1+1*2^0 ...... 1111_{(2)}
(求-15对-2为底),切记,不要误以为 15(10)=1(2)3+1(2)2+1(2)1+1(2)0-15_{(10)}=1*(-2)^3 + 1*(-2)^2+1*(-2)^1+1*(-2)^0
正确答案为:
15(10)=1(2)5+1(2)4+0(2)3+0(2)2+0(2)1+1(2)0......110001(2)-15_{(10)}=1*(-2)^5 + 1*(-2)^4+0*(-2)^3+0*(-2)^2+0*(-2)^1+1*(-2)^0 ...... 110001_{(-2)}

2、由于在进行进制转换时,基础算法与R是否大于0无关。现在只要求出 公式① 中的每项系数 a 即可

常规的位权展开如下(短除法+逆序输出):
例:十进制的10=8+2,对应着二进制的 1010
10 / 2 = 5 … 0
5 / 2 = 2 … 1
2 / 2 = 1 … 0
1 / 2 = 0 … 1

💡

如果是 -15 对 -2 进行短除法,则C++执行的结果为
-15 / -2 = 7 ... -1 (因为 -15 = 7 *(-2) + (-1))。
由于在进制转换时每项系数均为正,不能为负数(注解:不可能出现类似 11(-1)1 )
所以应该把 7 (-2) + (-1) 转换 为 8(-2) + (2 + (-1))。
即,余数为负数时,应 加上底的绝对值;同时前面再多减去一个底

3、实现步骤
a. 读入 n 和 R
b. 只要 n 不为0 ,就计算 n 对 R的余数和商
b1. 如果计算出来的余数为负数,则调整为正数(余数+abs(R)),同时,调整商(商+1)
c. 逆序输出结果。 由于本题的进制 R 超过10,需要用到字母表示。所以输出时统一先转换成字符再输出
c1. 如果系数 < 10, 则 cout << (char)('0' + a[j])
c2. 如果系数 >=10, 则 cout << (char)('A' + a[j] - 10)
注意,连续输出时,需要都转换成相同的格式。不能上面cout int, 下面cout char

题解代码:

#include <bits/stdc++.h>
using namespace std;
 
int n, k;
int a[100];  // 存储余数,最后倒序输出 
char ans[100]; // 由于超过10会变成ABCD...,所以统一转换为字符再输出
 
int main() 
{
    cin >> n >> k;
 
	int i; 
	for(i = 0; n != 0; i++)
	{
		a[i] = n % k;  // a[i] 为余数(即最后总倒序输出的数值) 
		n /= k;
		
		if(a[i] < 0)   // 如果余数为负,需转为正。举例: -15 = 7 *(-2) + (-1),应转为 8*(-2) + (2 + (-1)) 
		{
			a[i] = a[i] + abs(k);
			n++;
		}	
	}		
	    
    for(int j = i - 1; j >= 0; j--)   //倒序遍历数组,输出时统一转换为 char 型字符输出 
	{
		if(a[j] < 10)  cout << (char)('0' + a[j]);  // 统一转换为字符输出 (因为超过10的只能以字符输出) 
		else   cout << (char)('A' + a[j] - 10);     // 不能一部分cout int,一部分 cout char 
	}	
 
    return 0;
}